A linked list stores data in nodes scattered across memory, connected by pointers. Each node holds two things: a value and a reference to the next node. The last node points to None, signaling the end of the list. This structure is fundamentally different from an array, and understanding that difference is the key to knowing when each one is the right tool.

The Node Structure

Every linked list starts with a node definition. In Python, it looks like this:

1class ListNode:
2    def __init__(self, val=0, next=None):
3        self.val = val
4        self.next = next

That is it - two fields. val holds the data, and next holds a pointer to the following node. A linked list is just a chain of these objects, where the first node is called the head.

To build a list 1 -> 2 -> 3, you create three nodes and wire them together:

head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)

No Random Access

Arrays let you jump to any element in O(1) because elements sit in contiguous memory - the address of element k is base + k * element_size. Linked lists have no such luxury. Nodes are scattered across the heap, and the only way to reach node k is to start at the head and follow k pointers. That makes access O(n) in the worst case.

This sounds like a pure downside, but it is the tradeoff that unlocks linked lists' real strength.

Why Linked Lists Matter

Inserting or deleting a node at a known position takes O(1) - you rewire one or two pointers and you are done. In an array, inserting at position k requires shifting all elements from k onward to make room, which is O(n). Deleting is the same story - every element after the removed one shifts left.

This makes linked lists ideal when your workload involves frequent insertions and deletions, especially at the front or middle of the sequence. Operating systems use linked lists for process scheduling queues. LRU caches combine a linked list with a hash map. Memory allocators maintain free lists of available blocks.

Traversal Pattern

The fundamental operation on a linked list is traversal - visiting every node from head to tail. The pattern is always the same:

1def traverse(head):
2    curr = head
3    while curr:
4        # process curr.val
5        curr = curr.next

You start at head, process the current node, then advance to curr.next. When curr becomes None, you have visited every node. This pattern is the backbone of nearly every linked list algorithm: searching, counting, finding the maximum, printing - they all follow this template.

When to Reach for a Linked List

Use a linked list when you need frequent insertions or deletions at known positions and do not need index-based access. Use an array when you need random access by index, cache-friendly iteration, or binary search. In practice, arrays dominate because cache locality matters enormously on modern hardware - CPUs prefetch contiguous memory, making array iteration much faster than pointer-chasing through a linked list even when the asymptotic complexity is the same.

The reason linked lists appear so often in interviews is not because they are the best data structure - it is because they are the best data structure for testing pointer manipulation skills.