Singly Linked List

• Sequence of nodes
  • Element
  • Link to the next node
• head pointer to the first node of list
• tail pointer to the last node of list
• Explicitly connecting entries

Implementation

• size(): Returns the number of elements in the list
• isEmpty(): Returns true if the list is empty, and false otherwise
• first(): Returns (but does not remove) the first element in the list
• last(): Returns (but does not remove) the last element in the list
• addFirst(): Adds a new element to the front of the list
• addLast(): Adds a new element to the end of the list
• removeFirst(): Removes and returns the first element of the list

⇒ removeLast()?

Removing at the tail

• Need a pointer to the node just before tail...
• Since the list can only be traversed forward via next, we cannot directly reach the node before tail.
• Can we somehow traverse backward via...?

Doubly Linked List

• Sequence of nodes
  • Element
  • Link to the next node
  • Link to the previous node