Linked List

Nodes chained by pointers, O(1) splices.

singly_linked_list

4 nodes

head

7next

13next

4next

21next

null

Each node points to the next. Inserting is just rewiring a pointer.

tap ✕ to delete

How it works

A linked list strings nodes together, each holding a value and a pointer to the next. Nodes live anywhere in memory, so inserting or removing is just rewiring pointers — no shifting. The cost: no random access, and pointer-chasing is cache-unfriendly.

Mental models

Insertion is pointer surgery: link the new node, relink the neighbor.
No contiguous memory — you trade random access for cheap splicing.
A dummy/sentinel head node erases edge cases for empty lists.

Common pitfalls

Losing the next pointer before relinking drops the rest of the list.
Reversing in place needs three pointers: prev, curr, next.

Complexity

Access: O(n)
Search: O(n)
Insert (head): O(1)
Insert (tail): O(1)with tail pointer
Delete (known node): O(1)
Space: O(n)

Reach for it when

Frequent inserts/deletes at the ends or at a known position.
Building blocks for stacks, queues, adjacency lists, LRU caches.