Linked List

A sequence of nodes where each node stores a value and a pointer to the next node. Unlike arrays, the nodes are not stored contiguously in memory — they can live anywhere.

Structure of a Node

Each node holds two things:

[ value | pointer → ]

In a doubly linked list, each node also has a pointer going backwards:

[ ← pointer | value | pointer → ]

The list keeps track of two special nodes: - HEAD — the first node - TAIL — the last node

HEAD                                        TAIL
 ↓                                           ↓
[1] ↔ [2] ↔ [3] ↔ [4] ↔ [5]

Memory Layout

This is the key difference from arrays. Nodes are scattered across memory — each node just remembers the address of the next one.

Memory:
[0x16]  node 1  →  points to 1x16
[1x16]  node 2  →  points to 2x16
[2x16]  node 3  →  points to ...
        (other data in between, not used)

Because of this, you cannot jump directly to index 3 like with an array. You have to follow the chain of pointers from the head.

Big O of Operations

Why O(1) in the best case?

If you're accessing, inserting, or deleting at the HEAD or TAIL, you already have a direct pointer to those nodes — no traversal needed.

Add to head → just update HEAD pointer    → O(1)
Add to tail → just update TAIL pointer    → O(1)

Why O(n) in the worst case?

If the target is in the middle, you must start at the head and follow pointers one by one until you reach it.

Find node 4 → start at 1 → 2 → 3 → 4    → O(n)

Linked List vs Array

• Arrays are better when you need to read by index frequently — direct memory address access.
• Linked Lists are better when you need to insert or delete at the ends frequently — no need to copy or shift elements.

Key Takeaways

• A linked list is made of nodes that point to each other, scattered in memory.
• It always tracks the HEAD and the TAIL for O(1) access at the edges.
• There is no index — to reach any node, you traverse from the head.
• The trade-off vs arrays: slower reads, faster insertions/deletions at the edges.