Data Structure

Linked List

A chain of nodes where each node points to the next. There's no index to jump to, so reaching the nth item means walking n steps — but inserting or removing a node you're already at is just a couple of pointer changes, with nothing to shift.

AccessO(n)
Insert at headO(1)
SearchO(n)
MemoryScattered

Try It — Animated Flow

head
3
8
15
null
Each node holds a value and a pointer to the next node; the last one points to null. Pick an operation and press Run.
Step 1 / 1
Pointer / current
Comparing
Swapping / removing
Newly inserted
Settled

Java Implementation

Real-Life Usage

Music playlists
Each song points to the next. Adding or removing a song in the middle rewires two pointers instead of shifting the whole list.
LRU caches
A doubly linked list keeps entries in recently-used order while a hash map jumps straight to any node, so both lookup and reordering are O(1).
Undo/redo and browser history
Doubly linked lists (with a prev pointer too) let you step backward and forward through states.
Memory allocators
Operating systems keep free blocks of memory in a “free list”: a linked list of the chunks that are available.

Trade-offs

Reach for a linked list when
  • You insert or remove at the front, or at a node you already hold
  • The size changes a lot and you don't want to resize and copy an array
  • You're building other structures: queues, LRU caches, graph adjacency lists
Avoid it when
  • You need items by index (an array does that in O(1))
  • You loop over lots of items: scattered nodes are slow for the CPU cache
  • Memory is tight: every node carries an extra pointer