Linked Lists
Beginner · 14 min read · Data Structures Basics, Linear Structures
Nodes and pointers: singly, doubly and circular lists, and when they beat arrays.
An array keeps its elements side by side in one block of memory. A linked list scatters them anywhere and links them instead: each element lives in a small object, a node, that holds the value and a reference to the next node. Think of a treasure hunt: each clue tells you where the next one is.
Picture it
How it works
A node is just a tiny class:
Types of linked list
Interview linked-list problems almost always use a singly linked list given to you as a ListNode head. There's no list object, no size and no tail; just the first node.
Operations and their cost
The pattern: linked lists are fast where you already are and slow at getting somewhere.
Building one
The core operations, from the course's tested reference implementation:
In Java
java.util.LinkedList is a doubly linked list, but it doesn't expose its nodes. That means you can't get O(1) removal of an arbitrary element. In practice ArrayList and ArrayDeque beat it for almost everything. Linked lists matter in interviews because you manipulate the references.
Patterns that use linked lists
Interview questions
- When would you choose a linked list over an array?
- Why can't a singly linked list remove a given node in O(1)?
Further reading
Key takeaways
- A linked list is nodes holding a value and a reference to the next node; the list keeps head (and often tail).
- No indexing (O(n) to reach position i), but O(1) insert or remove at a spot you already hold.
- Singly, doubly (prev pointers, O(1) removal of a known node) and circular lists.
- Dummy nodes remove the head special case; save next before rewiring.
- In Java, prefer ArrayList and ArrayDeque; linked lists matter when you manage the nodes yourself.