Arrays are great at two things: instant access by index (O(1)) and iterating sequentially. But they have a weakness: inserting or deleting at the beginning costs O(n) - every element has to shift.
Imagine a line of people at a movie theater. If someone cuts to the front, everyone behind has to take a step back. That's the array's "shift" problem.
Now imagine each person just holds the hand of the person behind them. To insert at the front, you just tell the new person "hold onto the current front person" - nobody moves. That's a linked list.
A linked list sacrifices random access (no more arr[42]) for O(1) insertions and deletions anywhere - provided you already have a reference to the right spot.
| Operation | Array | Linked List |
|---|---|---|
| Access by index | O(1) | O(n) |
| Insert at beginning | O(n) | O(1) |
| Insert at end | O(1)* | O(n)** |
| Delete at beginning | O(n) | O(1) |
| Search by value | O(n) | O(n) |
A linked list is made of nodes. Each node contains a value and a pointer to the next node. The list is "linked" because each node points to the next one in sequence.
The first node is called the head. The last node points to null (nothing).
There are two flavors:
The key difference from arrays: to find element #5, you can't jump there - you have to start at the head and follow pointers 5 times. That's O(n) access by index.
| Operation | Singly Linked | Doubly Linked |
|---|---|---|
| Access head | O(1) | O(1) |
| Access tail | O(n) | O(1) |
| Access by index | O(n) | O(n) |
| Insert at head | O(1) | O(1) |
| Insert at tail | O(n) | O(1) |
| Delete by value | O(n) | O(n) |
head = entry point to the list
tail = last node in the list
node = contains a value and a pointer (nxt)
nxt = stores the memory address of the next node
arrow = shows which node nxt points to
null = marks the end of the list
public class ListNode {
public int val;
public ListNode next;
public ListNode(int val = 0, ListNode next = null) {
this.val = val;
this.next = next;
}
}
// C# also has built-in LinkedList<T> (doubly linked)
var list = new LinkedList<string>();
list.AddFirst("c");
list.AddLast("d");
list.AddBefore(list.First, "b");
// But for interviews, you'll usually implement the node classA doubly linked list node stores two pointers: prv (previous) and nxt (next), allowing traversal in both directions.
The trade-off: more memory per node (an extra pointer), but O(1) access to both previous and next nodes.
When to use doubly:
When to stick with singly:
prv = pointer to the previous node
nxt = pointer to the next node
head.prv → null, tail.nxt → null
doubly linked: can traverse in both directions
public class ListNode {
public int val;
public ListNode prv;
public ListNode nxt;
public ListNode(int val = 0, ListNode prv = null, ListNode nxt = null) {
this.val = val;
this.prv = prv;
this.nxt = nxt;
}
}
// Insert at head - O(1)
ListNode InsertAtHead(ListNode head, int val) {
var newNode = new ListNode(val, null, head);
if (head != null) head.prv = newNode;
return newNode;
}Reversal is the most common linked list operation - and it's a great exercise in pointer manipulation.
The idea: walk through the list, and for each node, make it point to the previous node instead of the next node. By the time you reach the end, the list is reversed.
You need to track three nodes: prev, current, and next (so you don't lose the rest of the list when you flip the pointer).
each node.nxt is flipped to point to the previous node
the old tail becomes the new head
// Reverse a singly linked list - O(n), O(1) space
ListNode ReverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next; // save next
curr.next = prev; // reverse pointer
prev = curr; // move prev forward
curr = next; // move curr forward
}
return prev; // new head
}Two pointers traverse the list at different speeds - the slow pointer moves 1 step, the fast pointer moves 2 steps.
This is useful for:
Find the middle node: When fast reaches the end, slow is at the middle. (Fast moves twice as fast, so it covers the full distance while slow covers half.)
Find the nth node from the end: Move fast n steps ahead, then advance both pointers together. When fast hits the end, slow is at the nth-from-last node.
These patterns work because of the relative speed difference - no extra data structures needed.
slow moves 1 node per iteration, fast moves 2 nodes
when fast reaches the end, slow is at the middle node
green outline = fast pointer, orange outline = slow pointer
// Find middle node - O(n), O(1) space
ListNode FindMiddle(ListNode head) {
ListNode slow = head, fast = head;
while (fast?.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}A cycle happens when a node's next pointer points back to an earlier node instead of null - creating an infinite loop.
Floyd's algorithm (tortoise & hare): Use the same fast/slow pointer technique. Slow moves 1 step, fast moves 2 steps. If they ever point to the same node, there's a cycle. If fast reaches the end (null), there isn't.
The intuition: on a circular track, a faster runner will eventually lap a slower runner. In a straight line, the faster runner just reaches the finish line first.
Floyd's algorithm: slow and fast pointers start at head
if slow and fast meet, a cycle exists (no null terminator)
// Detect cycle - O(n), O(1) space
bool HasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast?.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}Losing the head of the list If you move your head pointer without saving it first, you lose the entire list. Always keep a separate reference, or use a dummy node.
Null dereference on .next Always check that both the node and its .next are non-null before accessing .next.next. This is the most common linked list bug.
Forgetting to "save next" during reversal
In reversal: you must save curr.next before overwriting it. Without ListNode next = curr.next, you lose the rest of the list.
Assuming O(1) index access
list[5] on a linked list is O(n) - you have to walk 5 pointers. Arrays are for random access; linked lists are for sequential access with cheap insertions/deletions.
Starting fast/slow pointers incorrectly in cycle detection Both pointers should start at head, not head.next. Starting fast at head.next can miss cycles in edge cases.
Linked lists introduced you to the idea that data doesn't have to be stored in contiguous memory. Nodes can be anywhere, connected by pointers.
Now we'll look at two structures that build on this idea but add restrictions on how you can interact with them: Stacks & Queues.
A stack is like a stack of plates - you can only add or remove from the top (Last In, First Out). A queue is like a line at a store - the first person in line is the first person served (First In, First Out).
These restrictions might seem limiting, but they simplify reasoning about certain problems enormously.
Next up: Stacks & Queues