CS 240: Lecture 9 – Linked Lists
Dear students:
We are in the middle of a discussion of linear structures and the complexities of their operations. We started with an array-based list, and now we move on to a linked list. Today we’ll examine how the two approaches to lists differ.
Muddiest Points
But first, I will address a sample of your muddiest points.
Differentiating the difference between big omega and big theta keeps tripping me up. It is not confusing anymore but I still mix them up on occasion.
I think that in class we addressed the muddiest point I had last week, and that was the importance of amortized analysis. Especially with the examples, I now realize that although the worst case scenario is very important and might mean more to some than the best case and average case (a la Murphy’s law), it’s important to be aware of how often your worst case even occurs compared to the other cases. If you make your reasoning based off of the worst case alone, you fail to look at the bigger picture.
Determining which other time complexity classes a function can be classified as based on a based on a single Big O or Big Omega statement. Such as if a function is Ω(n), is it also Ω(n^2) or Ω(1)? and vice versa with big O.
I think the muddiest point from what was covered this week was understanding exactly what was the most important point. I still find understanding the difference between worst case/upper bound and the best case/lower bound at times difficult, because they require analysis techniques that I feel I am still not good at. For instance if we are doing a binary search, would the best case match (it being the middle of the array) be a lower bound of Omega(1). Furthermore, would the worst case, searching through half the array (n/2), simply be an upper bound of O(n)?
I think the muddiest point is that we didn’t go over enough examples/didn’t have enough time unfortunately. We never got to see an example where nlogn was used or even logn. If there is a direct example or a way you could explain it to show when the time complexity would be logn would be very nice.
Tracing Linked List Code
Consider the following code for the singly-linked list class from OpenDSA:
class LList implements List {
private Link head; // Pointer to list header
private Link tail; // Pointer to last element
private Link curr; // Access to current element
private int listSize; // Size of list
// Constructors
LList(int size) { this(); } // Constructor -- Ignore size
LList() { clear(); }
// Remove all elements
public void clear() {
curr = tail = new Link(null); // Create trailer
head = new Link(tail); // Create header
listSize = 0;
}
public Object remove() throws NoSuchElementException {
if (curr == tail) // Nothing to remove
throw new NoSuchElementException("remove() in LList has current of " + curr + " and size of "
+ listSize + " that is not a a valid element");
Object it = curr.element(); // Remember value
curr.setElement(curr.next().element()); // Pull forward the next element
if (curr.next() == tail) tail = curr; // Removed last, move tail
curr.setNext(curr.next().next()); // Point around unneeded link
listSize--; // Decrement element count
return it; // Return value
}
// ...
class Link<E> { // Singly linked list node class
private E e; // Value for this node
private Link<E> n; // Point to next node in list
// Constructors
Link(E it, Link<E> inn) { e = it; n = inn; }
Link(Link<E> inn) { e = null; n = inn; }
E element() { return e; } // Return the value
E setElement(E it) { return e = it; } // Set element value
Link<E> next() { return n; } // Return next link
Link<E> setNext(Link<E> inn) { return n = inn; } // Set next link
}
}
Using this code, complete the following diagramming and code-tracing exercises:
- Draw a linked diagram of a freshly constructed list. Mark
head,tail, andcurr. - Draw a linked diagram of a list containing the strings
"A","B", and"C"and which is currently positioned at"B". What happens whenremoveis called? Update the diagram as you trace through the method’s code. Do not erase any values or links. Just cross them out. - Draw a linked diagram of a list containing the strings
"A","B","C", and"D". and which is currently positioned at"C". What happens whenlist.hasPredecessor("D")is called? Update the diagram as you trace through the method’s code.public boolean hasPredecessor(E target) { Link<E> cursor = head.next(); while (cursor != curr) { if (cursor.element().equals(target)) { return true; } cursor = cursor.next(); } return false; }
Analyzing List Algorithms
Analyze each of the methods below as described.
- What is the $\Theta$ running time of this method if this list is an
ArrayList? ALinkedList?public static int sumByIndex(List<Integer> list) { int sum = 0; for (int i = 0; i < list.size(); i++) { sum += list.get(i); } return sum; }
- What is the $\Theta$ running time of this method if this list is an
ArrayList? ALinkedList?public static int sumWithIterator(List<Integer> xs) { int sum = 0; for (int x : xs) { sum += x; } return sum; }
- What is the $\Theta$ running time of this method if
toListis initially empty and both lists are of typeArrayList?LinkedList?public static void copy(List<Integer> fromList, List<Integer> toList) { for (int item : fromList) { toList.add(item); } }
- What is the $\Theta$ running time of this method if
toListis initially empty and both lists are of typeArrayList?LinkedList?public static void copyReverseA(List<Integer> fromList, List<Integer> toList) { for (int item : fromList) { toList.add(0, item); } }
- What is the $\Theta$ running time of this method if
toListis initially empty and both lists are of typeArrayList?LinkedList?public static void copyReverseB(List<Integer> fromList, List<Integer> toList) { for (int i = fromList.size() - 1; i >= 0; i--) { int value = fromList.get(i); toList.add(value); } }
- What is the worst-case $\Theta$ running time of this method if
toListis initially empty and both lists are of typeArrayList?LinkedList? What is the average-case $\Theta$ running time of this method iftoListis initially empty and both lists are of typeArrayList?LinkedList?public static void copyScramble(List<Integer> fromList, List<Integer> toList) { Random gen = new Random(); for (int i = 0; i < fromList.size(); i++) { int randomIndex = gen.nextInt(fromList.size()); int value = fromList.remove(randomIndex); toList.add(value); } }
TODO
- Read 7.08-7.09 in OpenDSA.
- Submit the dynamic arrays lab before 11 PM tonight.
- Keep working on PA1. Because of a peculiar grading setup, you must submit the same ZIP twice on Autolab.
See you next time.
Sincerely,
P.S. It’s time for a haiku!
Notebook or binder?
I stand there for hours choosing
Just stationery