Jupyter at Bryn Mawr College
Public notebooks: /services/public/dblank / CS206 Data Structures / 2017-Spring / Notebooks

1. LinkedList Summary

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.

For more information on Big-O notation, see page 80 of your textbook.

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()

1.2 LinkedList

  • 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























What is in the Math library?


http://docs.oracle.com/javase/8/docs/api/java/lang/Math.html













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.