CS 240: Lecture 10 - Linked List

Dear students:

Last week we looked at array-based lists. They are simple and fast for many operations, but not all. This week we examine a different way of implementing list that is fast where array-based lists are slow. And vice versa.

Singly-Linked List

A singly-linked list is a chain of node objects. Each node is a pair of an item and a reference to the next item:

class Node<T> {
  public T item;
  public Node<T> next;

Usually this class is made an inner class within some larger linked list abstraction.

Computing the size of a linked list could be a linear time operation. You would be wise to store the size in an instance variable on the list instead of traversing the chain.

Getting an item at a particular index requires a traversal. So does checking if the list contains an item. These are both \(~\Theta(n)~\).

Appending an element does not require a traversal if you track the tail node. You just make new node and wire it up to the tail. This is a \(~\Theta(1)~\) operation.

Removing a given index likely requires a traversal, so this is a \(~\Theta(n)~\) operation in the worst case. However, if you have an iterator that is currently pointing a node, you can remove it without any traversal. Removing through an iterator is \(~\Theta(1)~\).

We will implement these operations together in class.

This table contrasts the complexity classes of the two list implementations:

Operation Array List Linked List
size \(\Theta(1)\) \(\Theta(1)\)
get \(\Theta(1)\) \(\Theta(n)\)
append \(\Theta(1)\) (amortized) \(\Theta(1)\)
prepend \(\Theta(n)\) \(\Theta(1)\)
remove by index \(\Theta(n)\) \(\Theta(n)\)
remove by iterator \(\Theta(n)\) \(\Theta(1)\)


You've got a few things to do before we meet again:

See you next time!


P.S. It's time for a haiku!

Notebook or binder? For hours I'm stuck wondering Just stationery