What is a Linked List?

A linked list is a sequence of values where each value lives in its own node, and each node holds a pointer to the next node. The list knows about its first node (the head); from there you reach every other node by following the chain of next pointers.

Unlike an array, a linked list does not need a single contiguous block of memory. Adding an item at the head is O(1): just create a new node and point it at the current head. The trade-off is that reaching the n-th item is O(n), because we have to walk the chain one node at a time.

The five main operations on a 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.
3. Get: Return the value at a given index.
4. Remove: Delete the value at a given index.
5. Size: Return the number of values currently stored.

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