Written by: Prof. Nathan Sprague
Tracing Linked List Code
The insertAtPos method below is broken. Assuming that the figure below represents the state of memory, draw the state of memory after list.insertAtPos(1, "C") is called. How should the method be fixed?
head tail
| |
| |
v v
+--------+ +--------+ +--------+ +--------+
| null |-|--> | "A" |-|-->| "B" |-|--> | null |x|
+--------+ +--------+ +--------+ +--------+
public boolean insertAtPos(int pos, E it) {
// Return false if the position is invalid
if ((pos < 0) || (pos > listSize)) {
return false;
}
// Find the insertion node
Link<E> current = head.next();
for (int i = 0; i < pos; i++) {
current = current.next();
}
// Insert
Link<E> newLink = new Link<E>(it, current);
current.setNext(newLink);
if (tail == current) {
tail = current.next(); // New tail
}
listSize++;
return true;
}
Analyzing List Algorithms
Analyze each of the methods below according to the instructions in the Javadoc comments.
Code Listing 1:
/*
* What is the big-Theta running time of this method, assuming that list is
*
*
* an ArrayList:
*
*
*
* a LinkedList:
*
*
*
*/
public static int sumByIndex(List<Integer> list) {
int sum = 0;
for (int i = 0; i < list.size(); i++) {
sum += list.get(i); // Theta(1) for ArrayList
// Theta(i) for LinkedList
}
return sum;
}
ArrayList: $\Theta(n)$
LinkedList: $\Theta(n^2)$
The analysis for LinkedList is a little complicated. The get
operation requires $\Theta(i)$ time to access the $i$th element.
(The get method will begin at the head, and follow references
until it reaches posiiton $i$.) This means that the first time
through the loop will require that we follow 0 references, the
second 1, the third 2 etc. Overall, we need to step through
$\sum_{i=0}^{n-1}i$ references. As we saw earlier, this sum is
$\Theta(n^2)$. This same general reasoning will apply to all of
the examples below where the operation in the loop grows from 1 to
n or shrinks from n to 1 over the course of iteration.
(Actually, the fact that Java’s LinkedList class uses a
doubly-linked list means that the analysis above is slightly
wrong. The get operation follows something like $\min(i, n-i)$
references, since it starts from the tail if the index is past the
halfway point. This doesn’t change the bit-$\Theta$ running
time.)
Code Listing 2:
/*
* What is the big-Theta running time of this method, assuming that list is
*
*
* an ArrayList:
*
*
*
* a LinkedList:
*
*
*
*/
public static int sumWithIterator(List<Integer> list) {
int sum = 0;
for (int curValue : list) { // Each access Theta(1) for both List types.
sum += curValue;
}
return sum;
}
ArrayList: $\Theta(n)$
LinkedList: $\Theta(n)$
Answering this question requires us to keep in mind that for-each loops in Java make use of the iterator provided by the collection.
It is safe to assume that the iterator provided by the
LinkedList class will store a reference to the most recently
accessed node. It won’t re-start from the head each time next is
called.
Code Listing 3:
/*
* What is the big-Theta running time of this method, assuming that toList
* is initially empty, and that both lists are of type
*
*
* ArrayList:
*
*
*
* LinkedList:
*
*
*
*/
public static void copy(List<Integer> fromList,
List<Integer> toList) {
for (int item : fromList) {
toList.add(item); // ArrayList: Theta(1) (Amortized)
// LinkedList: Theta(1)
}
}
ArrayList: $\Theta(n)$
LinkedList: $\Theta(n)$
Again, this is doubly-linked, so adding at the end is a constant time operation.
Code Listing 4:
/*
* What is the big-Theta running time of this method, assuming that toList
* is initially empty, and that both lists are of type
*
*
* ArrayList:
*
*
*
* LinkedList:
*
*
*
*/
public static void copyReverseA(List<Integer> fromList,
List<Integer> toList) {
for (int item : fromList) {
toList.add(0, item); // ArrayList: Theta(n) (Where n represents
// the current size of toList)
// LinkedLst: Theta(1)
}
}
ArrayList: $\Theta(n^2)$
LinkedList: $\Theta(n)$
Code Listing 5:
/*
* What is the big-Theta running time of this method, assuming that toList
* is initially empty, and that both lists are of type
*
*
* ArrayList:
*
*
*
* LinkedList:
*
*
*
*/
public static void copyReverseB(List<Integer> fromList,
List<Integer> toList) {
int value;
for (int i = fromList.size() - 1; i >= 0; i--) {
value = fromList.get(i); // Theta(1) for ArrayList
// Theta(i) for LinkedList
toList.add(value); // Theta(1) for ArrayList (amortized)
// Theta(1) for LinkedList
}
}
ArrayList: $\Theta(n)$
LinkedList: $\Theta(n^2)$
Code Listing 6:
/*
* What is worst-case the big-Theta running time of this method, assuming
* that toList is initially empty, and that both lists are of the indicated
* type. Describe the worst case.
*
*
* ArrayList:
*
*
*
* LinkedList:
*
*
*
* What is average-case the big-Theta running time of this method, assuming
* that toList is initially empty, and that both lists are of the indicated
* type.
*
*
* ArrayList:
*
*
*
* LinkedList:
*
*
*
*/
public static void copyScramble(List<Integer> fromList,
List<Integer> toList) {
Random gen = new Random();
int randomIndex;
int value;
for (int i = 0; i < fromList.size(); i++) {
randomIndex = gen.nextInt(fromList.size());
value = fromList.remove(randomIndex);
toList.add(value);
}
}
Worst case ArrayList: $\Theta(n^2)$
The worst case happens in the (unlikely) event that every random index is 0. This means that all of the remove operations will be a the beginning and will require that all elements be shifted to the left (which requires \Theta(n) steps).
Worst case LinkedList: $\Theta(n^2)$
The worst case happens in the (unlikely) event that every random index is in the dead center of the list. Removal from either end is efficient, but removal from the middle requires the LinkedList to follow references from the head.
This would lead to a summation like $\sum_{i=0}^{n-1}\lfloor \frac{n-i}{2} \rfloor$ which is $\Theta(n^2)$
Average case ArrayList: $\Theta(n^2)$
Average case LinkedList: $\Theta(n^2)$
For both, the average case is about twice as fast as the worst case. For example, the worst case for ArrayList occurred when the element was always removed from position 0, and $n$ elements needed to be shifted. On average, this cost will be closer to $n/2$: Sometimes all of the elements need to be shifted, sometimes none, on average about half.