Linked List

The main advantage of a linked list is that you can add and remove elements at any position in $O(1)$. The caveat is that you need to have a reference to a node at the position in which you want to perform the addition/removal, otherwise the operation is $O(n)$, because you will need to iterate starting from the head until you get to the desired position.

A normal (dynamic) array requires $O(n)$ for adding and removing from an arbitrary position.

Linked lists have the advantage of not having fixed sizes.

While dynamic arrays can be resized, under the hood they still are allocated a fixed size - it’s just that when this size is exceeded, the array is resized, which is expensive.

The main disadvantage of a linked list is that there is no random access. While an array has $O(1)$ indexing, a linked list could require $O(n)$ to access an element at a given position.

Linked lists have more overhead than arrays - every element needs to have extra storage for the pointers.

We call the start of a linked list the head and the end of a linked list the tail.

Sentinel nodes sit at the start and end of linked lists and are used to make operations and the code needed to execute those operations cleaner. The idea is that, even when there are no nodes in a linked list, you still keep pointers to a head and tail. The real head of the linked list is head.next and the real tail is tail.prev. The sentinel nodes themselves are not part of the linked list. The sentinel nodes also allow us to easily add and remove from the front or back of the linked list.

Sometimes, it’s better to traverse using a “dummy” pointer and to keep head at the head. Using the dummy pointer allows us to traverse the linked list without losing a reference to the head.

Common patterns:

Fast and slow pointers

Most linked list problems don’t have tricks, you just need a strong understanding of how to move pointers around. The best way to train this skill is to practice.