What is a Doubly Linked List?

A doubly linked list is a sequence of nodes where each node carries a value and two pointers: prev to the previous node, and next to the next node. The list itself keeps track of both ends, the head (first node) and the tail (last node).

The two pointers per node and the extra tail reference buy us a lot. Adding to the end is now O(1) (jump straight to tail instead of walking the chain), and removing the last node is also O(1) (because we can reach the second-to-last node from tail.prev). The trade-off is more memory per node, plus more pointers to keep in sync on every insert and remove.

The five main operations on a doubly linked list are:

1. AddFirst: Add a value at the front of the list.
2. AddLast: Add a value at the end of the list (O(1)!).
3. Get: Return the value at a given index.
4. RemoveLast: Delete the last node (O(1)!).
5. Size: Return the number of nodes currently stored.

Let's create a Node class first, then build the DoublyLinkedList on top of it!