Jupyter at Bryn Mawr College |
|||
Public notebooks: /services/public/dblank / CS206 Data Structures / 2016-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.
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.
head
)Consider the following definition of another linked list idea.
class List {
double car;
List cdr;
List(double value) {
car = value;
}
}
List list = new List(23);
list.car
list.cdr
List cons(double value, List list) {
List retval = new List(value);
retval.cdr = list;
return retval;
}
list = cons(67, list);
list.car
list.cdr.car
import java.lang.Math;
Math.random()
What is in the Math library?
http://docs.oracle.com/javase/8/docs/api/java/lang/Math.html
for (int i=0; i < 100; i++) {
list = cons(Math.random(), list);
}
Now, let's check to see how long this list is:
int length(List list) {
if (list == null) {
return 0;
} else if (list.cdr == null) {
return 1;
} else {
return 1 + length(list.cdr);
}
}
length(null)
length(list)
for (int i=0; i < 10000; i++) {
list = cons(Math.random(), list);
}
length(list)
for (int i=0; i < 100000; i++) {
list = cons(Math.random(), list);
}
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)
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:
int length(List list) {
int count = 0;
while (list != null) {
list = list.cdr;
count++;
}
return count;
}
length(list)
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.