Linked List Visualizer — Singly, Doubly, and Circular Linked Lists
A linked list is a linear data structure where each element (node) contains data and a pointer to the next node. Unlike arrays, linked lists do not store elements in contiguous memory — nodes can be anywhere in memory, connected only by pointers. This makes insertion and deletion efficient at known positions but makes random access expensive. The linked list visualizer shows each operation's pointer changes step by step.
Linked List Types
| Type | Node structure | Traversal | Insert head | Insert tail | Best for |
|---|---|---|---|---|---|
| Singly linked list | Each node has: data + next pointer | Forward only (head → tail) | O(1) | O(n) — must traverse; O(1) with tail pointer | Simple forward-iteration use cases; stacks (using head as top) |
| Doubly linked list | Each node has: prev pointer + data + next pointer | Both forward and backward | O(1) | O(1) with tail pointer | Browser history, LRU cache, text editor cursor movement |
| Circular singly linked list | Singly linked but tail points back to head | Forwards, cycles indefinitely | O(1) | O(n) | Round-robin scheduling, carousel UI, multiplayer game turns |
| Circular doubly linked list | Doubly linked; tail→head and head←tail | Both directions, cycles | O(1) | O(1) | Music playlist loop, OS process scheduling (Linux scheduler uses this) |
How to Use the Linked List Visualizer
- Open the linked list visualizer.
- Select the list type: singly linked, doubly linked, or circular.
- Use the controls to:
- Insert at head: Add a new node at the beginning
- Insert at tail: Add a new node at the end
- Insert at position: Add a node at a specific index
- Delete by value: Remove the first node matching a value
- Search: Highlight the node containing a value
- Reverse: Reverse all pointers to flip the list direction
- Each operation is animated step by step — pointer changes are shown with arrows updating in real time.
Linked List Operations: Time Complexity
| Operation | Time complexity | How it works | Notes |
|---|---|---|---|
| Insert at head | O(1) | Create new node; set new.next = current head; set head = new node | No traversal needed; new node becomes the new head |
| Insert at tail | O(1) with tail ptr; O(n) without | Create new node; set current tail.next = new node; set tail = new node | O(n) for singly linked list without explicit tail pointer |
| Insert at position k | O(k) | Traverse to node k−1; set new.next = prev.next; set prev.next = new | Must traverse to find predecessor; O(1) pointer updates once found |
| Delete head | O(1) | Set head = head.next; old head is garbage collected | Handle empty list and single-element edge cases |
| Delete by value | O(n) | Traverse until node.next.value = target; set node.next = node.next.next | Requires previous pointer in singly linked list; O(1) with prev ptr in doubly |
| Search | O(n) | Traverse from head; compare each node value to target | No random access; must check each node sequentially |
| Length/size | O(n) if not cached; O(1) if maintained | Traverse entire list counting nodes, or maintain a length variable | Maintaining length as a field trades memory for O(1) access |
Linked List vs. Array
The choice between a linked list and an array depends on the dominant operation pattern:
- Random access: Array wins (O(1) by index). Linked list loses (O(n) — must traverse from head).
- Insert/delete at known position (with pointer): Linked list wins (O(1) pointer update). Array loses (O(n) — must shift elements).
- Insert/delete at head: Linked list O(1). Array O(n) (shift all elements).
- Memory: Array uses contiguous memory (cache-friendly). Linked list has overhead (pointer per node) and poor cache locality (nodes scattered in memory).
- Size flexibility: Linked list grows/shrinks dynamically with no pre-allocation. Dynamic array doubles capacity on overflow (amortised O(1) append).
In practice, arrays (and dynamic arrays like Python lists, Java ArrayList) outperform linked lists for most use cases due to cache performance — even when linked list has better theoretical complexity, the constant factors of pointer indirection and cache misses often make arrays faster for smaller collections.
Implementing a Singly Linked List
A node consists of a data field and a pointer to the next node:
Node structure (pseudocode):
- data: the value stored
- next: pointer to the next node (null for tail)
The linked list itself maintains:
- head: pointer to the first node
- tail (optional): pointer to the last node for O(1) tail insertion
- size (optional): integer tracking the number of nodes
Reversing a Linked List
Reversing a singly linked list is a classic interview question. The iterative approach uses three pointers:
- Initialize: prev = null, current = head, next = null
- While current != null: save next = current.next; point current.next = prev; advance prev = current; advance current = next
- Set head = prev (the last node is now the new head)
Time complexity: O(n) — visits each node once. Space complexity: O(1) — only three pointer variables. The visualiser animates this pointer flip process step by step, making it clear why three variables are needed.
Floyd's Cycle Detection Algorithm
Detecting whether a linked list has a cycle (circular linked list or corrupted pointers) uses Floyd's algorithm (tortoise and hare):
- Use two pointers: slow (advances 1 step) and fast (advances 2 steps)
- If fast == null or fast.next == null: no cycle (reached end)
- If slow == fast: cycle detected
This runs in O(n) time and O(1) space. If a cycle exists, the two pointers will eventually meet inside the cycle because the fast pointer "laps" the slow pointer.
Real-World Uses of Linked Lists
- Browser history: A doubly linked list lets you go back and forward through visited pages efficiently
- Undo/Redo: Editor history stored as a linked list; undo walks backwards, redo walks forwards
- Hash table chaining: When multiple keys hash to the same bucket, collisions are stored in a linked list at that bucket
- Memory allocators: Free memory blocks are tracked with linked lists; allocation pops a block, deallocation adds it back
- File system: FAT (File Allocation Table) file systems store file clusters as linked lists on disk
- Polynomial representation: Each term stored as a node (coefficient, exponent, next)
Common Questions
Why is insertion at the head O(1) but at the tail O(n)?
To insert at the head, simply create a new node pointing to the current head, then update the head pointer — two operations regardless of list size. To insert at the tail without a tail pointer, you must traverse from head to the last node (where node.next == null) — O(n) operations. If you maintain a separate tail pointer (common in production implementations), tail insertion is also O(1).
When would you use a linked list over an array in practice?
True linked lists are most useful when: (1) you need O(1) insertions/deletions at arbitrary positions with a reference to the node, (2) the size changes very frequently and pre-allocating an array would waste memory, or (3) you need a doubly-linked structure specifically (LRU cache, text editor cursor). In most practical programming, dynamic arrays (with amortised O(1) append) are preferred due to cache performance.
What is a sentinel node?
A sentinel (dummy) node is a placeholder node at the head (and sometimes tail) of a linked list. It contains no data but simplifies edge cases: insert/delete at the head become the same as insert/delete at any other position because there is always a node before the first real node. This eliminates the need to check if the list is empty or if we are modifying the head.
Visualise Linked List Operations
Insert, delete, and reverse nodes with step-by-step pointer animations for singly linked, doubly linked, and circular lists.
Open Linked List Visualizer