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:

TODO

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

See you next time!

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