# 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:

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)$$

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

See you next time!

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

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