## Jupyter at Bryn Mawr College

Public notebooks: /services/public/dblank / CS206 Data Structures / 2017-Spring / Notebooks

LinkedList's are a data structure to hold a variable amount of data. Array's are O(1) (constant time) to access an element, where LinkedList are O(n) where n is the length of the list.

When we have a Recursive Data Structure, it makes sense to have a Recursive method to go along with it.

## 1.1 Node¶

• Node instances hold the data, and a link to next Node
• They contain definitions of length(), and append()

• This is an instance to hold the start of the chain of nodes (called head)
• Makes it so that there is something when the list is empty
• also has methds length() and append(), but will call the head's version, if there is a head

# 2. Problem!¶

Consider the following definition of another linked list idea.

In [1]:
class List {
double car;
List cdr;

List(double value) {
car = value;
}
}

|  Added class List


In [3]:
List list = new List(23);

|  Added variable list of type List with initial value List@44e81672


In [4]:
list.car

|  Expression value is: 23.0
|    assigned to temporary variable $3 of type double  Out[4]: 23.0 In [5]: list.cdr  | Expression value is: null | assigned to temporary variable$4 of type List


Out[5]:
null
In [6]:
List cons(double value, List list) {
List retval = new List(value);
retval.cdr = list;
return retval;
}

|  Added method cons(double,List)


In [7]:
list = cons(67, list);

|  Variable list has been assigned the value List@5fe5c6f


In [9]:
list.car

|  Expression value is: 67.0
|    assigned to temporary variable $8 of type double  Out[9]: 67.0 In [8]: list.cdr.car  | Expression value is: 23.0 | assigned to temporary variable$7 of type double


Out[8]:
23.0

## 2.1 Now let's make some long lists!¶

In [9]:
import java.lang.Math;


In [10]:
Math.random()

|  Expression value is: 0.3753894908396601
|    assigned to temporary variable $9 of type double  Out[10]: 0.3753894908396601 In [11]: for (int i=0; i < 100; i++) { list = cons(Math.random(), list); }  Now, let's check to see how long this list is: In [12]: int length(List list) { if (list == null) { return 0; } else if (list.cdr == null) { return 1; } else { return 1 + length(list.cdr); } }  | Added method length(List)  In [13]: length(null)  | Expression value is: 0 | assigned to temporary variable$12 of type int


Out[13]:
0
In [14]:
length(list)

|  Expression value is: 102
|    assigned to temporary variable $13 of type int  Out[14]: 102 In [15]: for (int i=0; i < 10000; i++) { list = cons(Math.random(), list); }  In [16]: length(list)  | Expression value is: 10102 | assigned to temporary variable$15 of type int


Out[16]:
10102
In [17]:
for (int i=0; i < 100000; i++) {
list = cons(Math.random(), list);
}


In [ ]:
length(list)

|  java.lang.StackOverflowError thrown
|        at length (#23:7)
|        at length (#23:7)
|        at length (#23:7)
|        at length (#23:7)
|        at length (#23:7)

## 2.2 What happened?¶

When Java calls a function, the current place for the return value is put on a "stack" so that it knows what to do with it when the answer is computed.

A stack is a data structure that we will explore. Basically, it is like a stack of plates in the dinning hall: first one in is the last one out.

We will explore a stack soon, but for now we need to realize that using recursion in Java can have this bad side-effect.

So, let's write length without recursion:

In [20]:
int length(List list) {
int count = 0;
while (list != null) {
list = list.cdr;
count++;
}
return count;
}

|  Modified method length(List)
|    Update overwrote method length(List)


In [21]:
length(list)

|  Expression value is: 110102
|    assigned to temporary variable \$20 of type int


Out[21]:
110102

# 3. Summary¶

Recursive data structures in Java are fine.

Recursive processing in Java is not so fine.

Because Java doesn't handle recursive processing very well, we will avoid it for potentially large problems. Recursive processing is a beautify, wonderful tool, but doesn't play well with Java.