Linked Lists: Singly vs Doubly, vs Arrays, & When to Use

Q: When is a linked list actually better than an array?

When you frequently insert or delete at known positions without needing random access — the linked list relinks pointers in O(1) where an array would shift O(n) elements. Concrete cases: implementing a queue/deque, the recency list in an LRU cache (doubly linked + hash map), or splicing many elements mid-sequence. For almost everything else — especially anything that indexes by position or iterates hot loops — a dynamic array is faster in practice thanks to cache locality.

Q: What's the difference between singly and doubly linked lists?

A singly linked list's nodes point only forward (to next), making it compact but unable to traverse backward or delete a node without its predecessor. A doubly linked list's nodes point both ways (next and prev), costing extra memory but enabling backward traversal and O(1) deletion of any known node. Doubly linked lists are what LRU caches and many deque implementations use because of that O(1) removal.

Linked Lists

A linked list stores a sequence as a chain of nodes, each holding a value and a pointer to the next node. Unlike an array's contiguous block of memory, the nodes can live anywhere — they're stitched together by references. This gives linked lists a very different performance profile: O(1) to insert or delete at a known position (just relink pointers), but O(n) to reach the nth element (you must walk the chain).

In day-to-day programming you'll rarely build one by hand — dynamic arrays are the better default for most uses. But linked lists are foundational to understanding pointers and memory, and they're the right tool in a handful of specific cases (queues, LRU caches, frequent splicing). They're also a staple of technical interviews.

TL;DR

A linked list is nodes + next-pointers, not a contiguous block.
O(1) insert/delete at a known node; O(n) to index or search.
Arrays usually win in practice (cache locality, random access).
Use linked lists for queues, frequent splicing, or LRU caches.

Quick Example

A node points to the next; traversal walks the chain:

Singly vs Doubly Linked

Singly linked — each node points only to the next. Compact, but you can't walk backward, and deleting a node requires its predecessor.
Doubly linked — each node points to next and previous. Uses more memory but supports O(1) deletion of a known node and backward traversal — which is why LRU caches and many deques use them.

A circular variant links the last node back to the first.

Linked List vs Array

💡 In practice, arrays usually outperform linked lists even where Big-O looks equal — contiguous memory is cache-friendly, while chasing pointers across scattered nodes causes cache misses.

When to Use a Linked List

Queues / deques — O(1) add/remove at the ends (though array-backed deques often win).
LRU caches — a doubly linked list maintains recency order with O(1) moves, paired with a hash map.
Frequent splicing — inserting/removing many elements mid-sequence at known positions.
Unknown/streaming size with no random access needed.

For most other cases — especially anything needing indexing — use a dynamic array (your language's list/vector).

Best Practices

Default to a dynamic array unless you specifically need O(1) splicing at known nodes.
Use a doubly linked list when you need O(1) deletion or backward traversal (e.g. LRU).
Prefer the standard library (deque, LinkedList) over hand-rolled lists in production.
Watch for null/None at the ends — most linked-list bugs are off-by-one pointer errors.
Don't index a linked list in a loop — that's O(n) per access, O(n²) overall.

Common Mistakes

Indexing a linked list like an array

Reaching for a linked list by default

FAQ

When is a linked list actually better than an array?

When you frequently insert or delete at known positions without needing random access — the linked list relinks pointers in O(1) where an array would shift O(n) elements. Concrete cases: implementing a queue/deque, the recency list in an LRU cache (doubly linked + hash map), or splicing many elements mid-sequence. For almost everything else — especially anything that indexes by position or iterates hot loops — a dynamic array is faster in practice thanks to cache locality.

Why do arrays often outperform linked lists despite similar Big-O?

Because Big-O ignores constant factors and memory behavior. Arrays store elements contiguously, so the CPU cache loads neighbors together and iteration is fast; linked-list nodes are scattered across memory, so following each pointer risks a cache miss — often an order of magnitude slower per step. Arrays also avoid the per-node pointer overhead. So even when both are "O(n) to traverse," the array's constant factor is much smaller in real hardware.

What's the difference between singly and doubly linked lists?

A singly linked list's nodes point only forward (to next), making it compact but unable to traverse backward or delete a node without its predecessor. A doubly linked list's nodes point both ways (next and prev), costing extra memory but enabling backward traversal and O(1) deletion of any known node. Doubly linked lists are what LRU caches and many deque implementations use because of that O(1) removal.

Should I implement a linked list myself?

Rarely in production — use your language's standard library (collections.deque in Python, LinkedList/ArrayDeque in Java, std::list in C++), which is tested and optimized. Implementing one by hand is mainly valuable for learning pointer manipulation and for technical interviews, where linked-list problems (reversal, cycle detection, merging) are common. For real code, reach for the built-in that matches your access pattern.