Linked List

Nodes linked by pointers.

A linked list is a chain of little boxes (nodes). Each box stores a value and an arrow pointing to the next box. Unlike an array, the boxes don't have to sit next to each other in memory — they're connected by the arrows.

• Head — reference to the first node; the list ends when a node's next is null.
• Insert/remove at front is O(1) — just re-point arrows.
• No random access — to reach the 5th item you must walk from the head.

Variants and complexity.

• Singly linked — each node points forward only.
• Doubly linked — nodes point both ways; O(1) removal given a node, easy reverse traversal.
• Circular — the tail points back to the head; useful for round-robin.

Access / search      O(n)
Insert/delete front  O(1)
Insert/delete given a node ref  O(1)  (doubly)
Insert/delete at tail  O(1) with a tail pointer

Trade-offs and techniques.

• Cache locality — nodes scattered in memory cause cache misses, so linked lists are often slower than arrays despite equal Big-O.
• Memory overhead — each node stores extra pointer(s) plus allocator overhead.
• Classic techniques — fast/slow pointers (cycle detection, find middle), in-place reversal, dummy/sentinel head nodes to simplify edge cases.
• Uses — building blocks for stacks/queues, adjacency lists, LRU caches (with a hash map), and free lists in allocators.