# 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)\) |

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