Linked Lists vs Arrays - Learning Module

Loading content...

0/276

Criteria for Choosing Linked Lists

When Linked Lists Truly Shine

In the previous page, we established that arrays should be your default choice for most scenarios. Their cache efficiency, lower memory overhead, and simpler implementation make them the pragmatic option when you're unsure.

But there are situations — important, common situations — where linked lists are genuinely superior. Not just marginally better, but fundamentally more appropriate for the problem at hand.

This page identifies those scenarios with precision. By the end, you'll have a clear mental checklist for recognizing when a linked list is the right tool.

What You Will Learn

You will learn the specific, concrete criteria that indicate a linked list is the optimal choice. We'll examine each criterion in depth, with real-world examples and code patterns that demonstrate when linked lists provide measurable advantages over arrays.

Criterion 1: Frequent Insertion/Deletion at Known Positions

This is the primary scenario where linked lists excel. If your algorithm requires frequent insertions or deletions at positions other than the end, and you can maintain references to those positions, linked lists provide O(1) operations where arrays require O(n).

The critical requirement: known positions

Linked lists only provide O(1) insertion/deletion when you already have a reference (pointer) to the relevant node. This is fundamentally different from inserting at an arbitrary index.

"Insert after node X" → O(1) in linked list
"Insert at index 5" → O(n) in linked list (must traverse to find position)

The distinction matters enormously. Linked lists don't magically make all insertions fast — they make insertions at known locations fast.

Design for Node References

To leverage linked list insertion speed, design your algorithms to maintain node references. Store pointers to nodes alongside other data. Pass nodes between functions, not indices. This is a different programming style, but it's what makes linked list operations efficient.

Example: LRU Cache Implementation

An LRU (Least Recently Used) cache is a classic example where this criterion applies:

When an item is accessed, it must move to the front of the usage order
When capacity is exceeded, the least recently used item (at the back) must be removed
Both operations happen on every cache access — they must be O(1)

With an array: Moving an item to the front requires shifting all items between its current position and the front — O(n). This is unacceptable for a cache that might handle thousands of accesses per second.

With a doubly linked list: Removing a node and inserting at the head are both O(1). Combined with a hash map for O(1) lookup, this gives us an O(1) LRU cache.

lru-cache-pattern.pseudo

Pseudocode

// LRU Cache using Doubly Linked List + Hash Map
// Each node contains: key, value, prev pointer, next pointer
 
Access(key):
    if key in hashMap:
        node = hashMap[key]
        // Move to front in O(1):
        // 1. Remove from current position (update neighbors' pointers)
        node.prev.next = node.next
        node.next.prev = node.prev
        // 2. Insert at head
        node.next = head.next
        node.prev = head
        head.next.prev = node
        head.next = node
        return node.value
    else:
        return CACHE_MISS
 
Insert(key, value):
    if at capacity:
        // Remove from back in O(1):
        lru = tail.prev
        lru.prev.next = tail
        tail.prev = lru.prev
        delete hashMap[lru.key]
    
    // Insert at front in O(1)
    newNode = Node(key, value)
    newNode.next = head.next
    newNode.prev = head
    head.next.prev = newNode
    head.next = newNode
    hashMap[key] = newNode
 
// All operations are O(1)!

Patterns That Benefit from O(1) Insertion/Deletion

•LRU/MRU Caches — Items constantly move based on access patterns
•Undo/Redo Buffers with Branching — Historical states branch and merge
•Playlist Management — Songs are inserted, removed, and reordered frequently
•Text Editors (Gap Buffer Alternative) — Insertions at cursor position
•Event Scheduling — Events are inserted and removed in priority order
•Browser History — Pages are pushed, popped, and navigated

Criterion 2: Unknown or Unpredictable Size

Linked lists grow and shrink efficiently without reallocation. When the collection size is unpredictable — especially wenn it fluctuates significantly — linked lists avoid the worst-case behaviors of dynamic arrays.

The dynamic array problem:

Dynamic arrays cope with size uncertainty by over-allocating. When capacity is reached, they allocate a new, larger block and copy all elements. This has consequences:

Latency spikes: Reallocation and copy operations are expensive. A single append can take O(n) time.
Memory fragmentation: Old blocks are freed, leaving gaps in memory. Large allocations may fail even when total free memory is sufficient.
Doubling waste: After doubling from 512 to 1024 elements, if you only need 513, you've wasted nearly 50% of capacity.

When size unpredictability matters:

Scenarios Where Size Unpredictability Hurts Arrays

•Real-time systems — Reallocation latency spikes are unacceptable. Linked lists provide consistent per-operation time.
•Highly variable data — If collection size varies from 100 to 1,000,000 unpredictably, array capacity management becomes complex.
•Memory-constrained environments — When total memory is limited, array over-allocation can cause earlier OOM conditions.
•Long-running processes — Repeated grow/shrink cycles cause fragmentation that accumulates over time.
•Concurrent access — Reallocation requires careful synchronization; linked list growth is naturally thread-safe per node.

Example: Stream Processing Buffer

Consider a network stream processor that buffers incoming packets:

Packets arrive at variable rates (10/sec to 100,000/sec)
Processing speed varies based on packet complexity
Buffer size fluctuates dramatically based on rate differential

With an array: You must choose initial capacity. Too small → frequent reallocation during bursts. Too large → wasted memory during quiet periods. Reallocation during peak traffic causes latency when you can least afford it.

With a linked list: Each packet is a new node. No reallocation during bursts. Memory usage exactly matches current buffer size. Consistent per-packet insertion time regardless of buffer state.

The trade-off: Linked lists use more total memory per element, but that memory exactly matches needs. Arrays use less memory per element but may waste capacity.

Modern Allocator Optimizations

Modern memory allocators (jemalloc, tcmalloc) include optimizations for frequent small allocations, reducing linked list overhead. However, they cannot eliminate the fundamental per-node overhead. Profile in your specific environment before deciding.

Criterion 3: Stable References Required

This is a frequently overlooked advantage of linked lists: pointers to nodes remain valid after other modifications.

In arrays, almost any mutation can invalidate pointers and indices:

Insertion shifts elements → indices change
Deletion shifts elements → indices change
Reallocation moves elements → pointers become dangling

In linked lists, a pointer to a node remains valid regardless of what happens to other nodes. The node stays in the same memory location; only its links change.

Array Reference Instability

•Index 5 no longer refers to the same element after insertions
•Pointer to arr[3] may become dangling after reallocation
•External components holding indices must be notified of changes
•Iteration during modification is hazardous
•Concurrent access requires careful coordination

Linked List Reference Stability

•A pointer to a node remains valid indefinitely
•Node's memory address never changes
•External components can safely hold node pointers
•Careful iteration during modification is possible
•Some concurrent access patterns are naturally safe

Example: Observer Pattern with Dynamic Subscribers

Consider an event system where observers subscribe and unsubscribe dynamically:

Each subscriber holds a reference to its subscription for later cancellation
Subscribers come and go frequently
The system must efficiently dispatch events to all active subscribers

With an array: When a subscriber unsubscribes, removing it from the array shifts later elements. Any subscribers holding their indices (or pointers computed from indices) are now invalid. The system must either:

Notify all subscribers of the change (O(n) work)
Use a secondary data structure to map stable IDs to current indices
Tolerate invalid references and handle them gracefully

With a linked list: Each subscription is a node. The subscriber holds a pointer to this node. Unsubscription removes the node by updating neighbors' pointers. No other references are affected. The subscriber's pointer, though removed from the list, remains valid until explicitly freed.

Intrusive Linked Lists

For maximum efficiency, consider intrusive linked lists where the node pointers are embedded directly in the data structure. This eliminates separate node allocations and allows the data element itself to serve as its own node. Many high-performance systems (e.g., Linux kernel) use this pattern extensively.

Criterion 4: Constant-Time Merge and Split Operations

Linked lists can merge two lists or split one list into two in O(1) time. This is impossible with arrays, which require O(n) copying for such operations.

Merge operation:

Array: Allocate new array of combined size, copy all elements from both arrays. O(n + m) time and space.
Linked List: Update tail of first list to point to head of second list. O(1) time, O(1) space.

Split operation:

Array: Allocate new array, copy elements after split point. O(n) time and space.
Linked List: Update split node's pointer to null, update new list's head pointer. O(1) time, O(1) space (after finding split point).

Note: Finding the split point still requires O(n) traversal if specified by index. The O(1) benefit applies when you already have a reference to the split node.

Example: Work Stealing Scheduler

In parallel computing, work stealing is a load-balancing technique where idle processors "steal" work from busy processors:

Each processor maintains a double-ended queue (deque) of tasks
Processors add and remove tasks from their local deque
Idle processors steal tasks from other processors' deques

The stealing operation often takes half of the victim's queue:

With an array-based deque: Stealing half the queue requires copying those elements — O(n) work during a time-critical operation.

With a linked list deque: Splitting at the midpoint involves updating two pointers. The thief takes the tail half; the victim keeps the head half. O(1) after finding the midpoint.

The performance difference matters because stealing happens precisely when the system is under load. Fast stealing means better load distribution under stress.

Scenarios Requiring Fast Merge/Split

•Work stealing schedulers — Tasks are split and distributed across threads
•Partition-based sorting — QuickSort partitions and recombines lists
•Memory allocators — Free lists are split and merged based on allocation sizes
•Document editing — Rope data structures split and merge text segments
•Cache eviction — LRU segments can be split by age or priority
•Concurrent data structures — Segments can be processed independently then merged

linked-list-split.pseudo

Pseudocode

// Split a doubly linked list at a given node
// O(1) operation assuming 'splitNode' is given
 
SplitAt(list, splitNode):
    // Create new list starting at splitNode
    newList = new List()
    newList.head = splitNode
    newList.tail = list.tail
    
    // Original list ends just before splitNode
    if splitNode.prev != null:
        list.tail = splitNode.prev
        list.tail.next = null
        splitNode.prev = null
    else:
        // Split at head - original list becomes empty
        list.head = null
        list.tail = null
    
    return newList
 
// Merge two lists: O(1)
Merge(list1, list2):
    if list1.tail != null:
        list1.tail.next = list2.head
    else:
        list1.head = list2.head
    
    if list2.head != null:
        list2.head.prev = list1.tail
    
    if list2.tail != null:
        list1.tail = list2.tail
    
    // list2 is now empty/invalid
    return list1

Criterion 5: Real-Time and Latency-Sensitive Systems

In real-time systems, the worst-case execution time matters more than average-case. Dynamic arrays have excellent amortized performance, but their worst case — reallocation during append — is O(n).

For systems with strict latency bounds, this occasional O(n) spike may be unacceptable:

Audio processing: A 1ms delay causes audible glitches
Industrial control: Missed deadlines can cause physical damage
Trading systems: Microseconds matter for order execution
Gaming: Frame drops are immediately visible to users

Linked lists provide bounded worst-case time:

Worst-Case Time Complexity Comparison
Operation	Dynamic Array (Worst Case)	Linked List (Worst Case)
Append	O(n) — reallocation and copy	O(1) — allocate single node
Prepend	O(n) — shift all elements	O(1) — update head pointer
Delete at head	O(n) — shift all elements	O(1) — update head pointer
Insert at known position	O(n) — shift elements	O(1) — update pointers

Memory allocation in real-time contexts:

A common concern is that linked list operations require memory allocation, which itself can have variable latency. Real-time systems address this through:

Object pools: Pre-allocate a pool of nodes. Acquiring and releasing nodes becomes O(1) with bounded time.
Arena allocation: Allocate nodes from a pre-allocated memory region. No system calls during operation.
Static maximum sizing: If the maximum collection size is known, pre-allocate all nodes at startup.

With these techniques, linked lists provide truly bounded operation times — essential for hard real-time systems.

Example: Audio Buffer Management

A digital audio workstation manages buffers of audio samples:

Buffers are queued for processing, then returned to a free pool
Processing latency must stay under ~5ms to avoid audible artifacts
The system handles variable numbers of audio tracks

With arrays: Buffer queues might resize during peak activity, causing latency spikes precisely when the system is under stress.

With pre-pooled linked lists: Queue and dequeue operations are O(1) with bounded constant. No allocation spikes. Consistent latency regardless of load.

Real-Time Requires Holistic Design

Simply using linked lists doesn't make a system real-time. The entire design — memory management, synchronization, I/O handling — must be considered. But choosing data structures with bounded worst-case complexity is a necessary foundation.

Criterion 6: Building Other Data Structures

Linked lists often serve as the underlying implementation for other abstract data types. The choice to use a linked list isn't about using linked lists directly, but about implementing something else efficiently.

Data structures commonly implemented with linked lists:

Linked List as Implementation Foundation

•Stack — Linked list with operations at head only. O(1) push and pop without capacity limits.
•Queue — Linked list with operations at both ends. O(1) enqueue (tail) and dequeue (head).
•Deque (Double-Ended Queue) — Doubly linked list with O(1) operations at both ends.
•Hash Table Chaining — Collisions stored in linked lists per bucket. Dynamic chain length.
•Adjacency List Graphs — Each vertex's neighbors stored in a linked list. Dynamic neighbor sets.
•Free Lists in Memory Allocators — Freed blocks linked together for reuse.
•Symbol Tables — Scope chains in compilers often use linked structures.

Why linked lists for these structures:

Each of these structures benefits from linked list properties:

Stacks and Queues: Operations only at endpoints — linked lists provide O(1) there. No random access needed.
Hash Table Chaining: Chain lengths vary widely. A hash table with 10,000 buckets might have chains ranging from 0 to 100 elements. Arrays would waste space on empty/short buckets or require complex sizing.
Graph Adjacency Lists: Vertex degrees vary dramatically. A social network might have users with 10 friends and users with 10,000 friends. Linked lists accommodate this naturally.
Memory Allocators: Free blocks have inherent link structure — each block can contain a pointer to the next free block at no additional memory cost.

The abstraction principle: When using a stack or queue, you don't care whether it's implemented with a linked list or array. The implementation should be chosen based on the operations' performance requirements. For many of these structures, linked lists provide the best performance profile.

Implementation vs Interface

Users of a Stack or Queue shouldn't need to know it's implemented with a linked list. The linked list is an implementation detail hidden behind the abstract interface. This encapsulation allows the implementation to change if requirements evolve.

Quick Decision Checklist for Linked Lists

Here is a practical checklist for determining whether linked lists are appropriate for your use case. If you can answer "yes" to most of these questions, a linked list is likely the right choice.

Linked List Decision Criteria

•Operations at ends? Are most operations at the head or tail of the collection?
•Maintain node references? Can you design your algorithm to hold references to nodes rather than indices?
•Frequent mid-list changes? Do you frequently insert or delete at positions other than the end?
•Stable references needed? Do external components need to hold stable references into the collection?
•Merge/split operations? Do you need to combine or divide collections efficiently?
•Bounded worst-case? Is worst-case latency more important than average-case throughput?
•Variable size? Does the collection size fluctuate significantly and unpredictably?
•Little random access? Is random access by index rarely or never needed?
•Large elements? Are elements large enough that pointer overhead is negligible?

Strength of Recommendation Based on Criteria Match
Criteria Matched	Recommendation
0-2	Strongly prefer arrays
3-4	Arrays likely better, but profile if performance matters
5-6	Linked list likely appropriate
7-9	Strongly prefer linked lists

When in Doubt, Profile

If the criteria are borderline, implement the simpler option (usually arrays) first. Profile with realistic data sizes and access patterns. Only switch to linked lists if profiling reveals a genuine bottleneck that linked lists would solve.

Summary: When Linked Lists Win

This page has identified the specific scenarios where linked lists provide genuine advantages over arrays. Let's consolidate these criteria:

Key Takeaways

•Frequent insertion/deletion at known positions — O(1) with node reference, vs O(n) for arrays.
•Unpredictable size with stability requirements — No reallocation spikes, no over-provisioning.
•Stable references — Node pointers remain valid through other modifications.
•Fast merge and split — O(1) operations impossible with arrays.
•Real-time constraints — Bounded worst-case operation time.
•Implementing other structures — Stacks, queues, deques, hash table chains, and more.

The mental model:

Linked lists trade random access and cache efficiency for structural flexibility. When your algorithms need that flexibility — when you're constantly rearranging, inserting, deleting, merging, and splitting — linked lists pay back the overhead many times over.

What's next:

Now we'll examine the opposite perspective: the criteria for choosing arrays. Understanding both sides of the decision completes your mental framework for data structure selection.

Page Complete

You now have a clear, actionable set of criteria for identifying when linked lists are the optimal choice. These aren't arbitrary rules — they're derived from the fundamental properties of linked lists. Next, we'll complete the picture with the criteria for choosing arrays.

Criteria for Choosing Linked Lists

When Linked Lists Truly Shine

But there are situations — important, common situations — where linked lists are genuinely superior. Not just marginally better, but fundamentally more appropriate for the problem at hand.

This page identifies those scenarios with precision. By the end, you'll have a clear mental checklist for recognizing when a linked list is the right tool.

What You Will Learn

Criterion 1: Frequent Insertion/Deletion at Known Positions

The critical requirement: known positions

Linked lists only provide O(1) insertion/deletion when you already have a reference (pointer) to the relevant node. This is fundamentally different from inserting at an arbitrary index.

"Insert after node X" → O(1) in linked list
"Insert at index 5" → O(n) in linked list (must traverse to find position)

The distinction matters enormously. Linked lists don't magically make all insertions fast — they make insertions at known locations fast.

Design for Node References

Example: LRU Cache Implementation

An LRU (Least Recently Used) cache is a classic example where this criterion applies:

When an item is accessed, it must move to the front of the usage order
When capacity is exceeded, the least recently used item (at the back) must be removed
Both operations happen on every cache access — they must be O(1)

With a doubly linked list: Removing a node and inserting at the head are both O(1). Combined with a hash map for O(1) lookup, this gives us an O(1) LRU cache.

lru-cache-pattern.pseudo

Pseudocode

// LRU Cache using Doubly Linked List + Hash Map
// Each node contains: key, value, prev pointer, next pointer
 
Access(key):
    if key in hashMap:
        node = hashMap[key]
        // Move to front in O(1):
        // 1. Remove from current position (update neighbors' pointers)
        node.prev.next = node.next
        node.next.prev = node.prev
        // 2. Insert at head
        node.next = head.next
        node.prev = head
        head.next.prev = node
        head.next = node
        return node.value
    else:
        return CACHE_MISS
 
Insert(key, value):
    if at capacity:
        // Remove from back in O(1):
        lru = tail.prev
        lru.prev.next = tail
        tail.prev = lru.prev
        delete hashMap[lru.key]
    
    // Insert at front in O(1)
    newNode = Node(key, value)
    newNode.next = head.next
    newNode.prev = head
    head.next.prev = newNode
    head.next = newNode
    hashMap[key] = newNode
 
// All operations are O(1)!

Patterns That Benefit from O(1) Insertion/Deletion

•LRU/MRU Caches — Items constantly move based on access patterns
•Undo/Redo Buffers with Branching — Historical states branch and merge
•Playlist Management — Songs are inserted, removed, and reordered frequently
•Text Editors (Gap Buffer Alternative) — Insertions at cursor position
•Event Scheduling — Events are inserted and removed in priority order
•Browser History — Pages are pushed, popped, and navigated

Criterion 2: Unknown or Unpredictable Size

The dynamic array problem:

Dynamic arrays cope with size uncertainty by over-allocating. When capacity is reached, they allocate a new, larger block and copy all elements. This has consequences:

Latency spikes: Reallocation and copy operations are expensive. A single append can take O(n) time.
Memory fragmentation: Old blocks are freed, leaving gaps in memory. Large allocations may fail even when total free memory is sufficient.
Doubling waste: After doubling from 512 to 1024 elements, if you only need 513, you've wasted nearly 50% of capacity.

When size unpredictability matters:

Scenarios Where Size Unpredictability Hurts Arrays

•Real-time systems — Reallocation latency spikes are unacceptable. Linked lists provide consistent per-operation time.
•Highly variable data — If collection size varies from 100 to 1,000,000 unpredictably, array capacity management becomes complex.
•Memory-constrained environments — When total memory is limited, array over-allocation can cause earlier OOM conditions.
•Long-running processes — Repeated grow/shrink cycles cause fragmentation that accumulates over time.
•Concurrent access — Reallocation requires careful synchronization; linked list growth is naturally thread-safe per node.

Example: Stream Processing Buffer

Consider a network stream processor that buffers incoming packets:

Packets arrive at variable rates (10/sec to 100,000/sec)
Processing speed varies based on packet complexity
Buffer size fluctuates dramatically based on rate differential

With a linked list: Each packet is a new node. No reallocation during bursts. Memory usage exactly matches current buffer size. Consistent per-packet insertion time regardless of buffer state.

The trade-off: Linked lists use more total memory per element, but that memory exactly matches needs. Arrays use less memory per element but may waste capacity.

Modern Allocator Optimizations

Criterion 3: Stable References Required

This is a frequently overlooked advantage of linked lists: pointers to nodes remain valid after other modifications.

In arrays, almost any mutation can invalidate pointers and indices:

Insertion shifts elements → indices change
Deletion shifts elements → indices change
Reallocation moves elements → pointers become dangling

In linked lists, a pointer to a node remains valid regardless of what happens to other nodes. The node stays in the same memory location; only its links change.

Array Reference Instability

•Index 5 no longer refers to the same element after insertions
•Pointer to arr[3] may become dangling after reallocation
•External components holding indices must be notified of changes
•Iteration during modification is hazardous
•Concurrent access requires careful coordination

Linked List Reference Stability

•A pointer to a node remains valid indefinitely
•Node's memory address never changes
•External components can safely hold node pointers
•Careful iteration during modification is possible
•Some concurrent access patterns are naturally safe

Example: Observer Pattern with Dynamic Subscribers

Consider an event system where observers subscribe and unsubscribe dynamically:

Each subscriber holds a reference to its subscription for later cancellation
Subscribers come and go frequently
The system must efficiently dispatch events to all active subscribers

Notify all subscribers of the change (O(n) work)
Use a secondary data structure to map stable IDs to current indices
Tolerate invalid references and handle them gracefully

Intrusive Linked Lists

Criterion 4: Constant-Time Merge and Split Operations

Linked lists can merge two lists or split one list into two in O(1) time. This is impossible with arrays, which require O(n) copying for such operations.

Merge operation:

Array: Allocate new array of combined size, copy all elements from both arrays. O(n + m) time and space.
Linked List: Update tail of first list to point to head of second list. O(1) time, O(1) space.

Split operation:

Array: Allocate new array, copy elements after split point. O(n) time and space.
Linked List: Update split node's pointer to null, update new list's head pointer. O(1) time, O(1) space (after finding split point).

Note: Finding the split point still requires O(n) traversal if specified by index. The O(1) benefit applies when you already have a reference to the split node.

Example: Work Stealing Scheduler

In parallel computing, work stealing is a load-balancing technique where idle processors "steal" work from busy processors:

Each processor maintains a double-ended queue (deque) of tasks
Processors add and remove tasks from their local deque
Idle processors steal tasks from other processors' deques

The stealing operation often takes half of the victim's queue:

With an array-based deque: Stealing half the queue requires copying those elements — O(n) work during a time-critical operation.

With a linked list deque: Splitting at the midpoint involves updating two pointers. The thief takes the tail half; the victim keeps the head half. O(1) after finding the midpoint.

The performance difference matters because stealing happens precisely when the system is under load. Fast stealing means better load distribution under stress.

Scenarios Requiring Fast Merge/Split

•Work stealing schedulers — Tasks are split and distributed across threads
•Partition-based sorting — QuickSort partitions and recombines lists
•Memory allocators — Free lists are split and merged based on allocation sizes
•Document editing — Rope data structures split and merge text segments
•Cache eviction — LRU segments can be split by age or priority
•Concurrent data structures — Segments can be processed independently then merged

linked-list-split.pseudo

Pseudocode

// Split a doubly linked list at a given node
// O(1) operation assuming 'splitNode' is given
 
SplitAt(list, splitNode):
    // Create new list starting at splitNode
    newList = new List()
    newList.head = splitNode
    newList.tail = list.tail
    
    // Original list ends just before splitNode
    if splitNode.prev != null:
        list.tail = splitNode.prev
        list.tail.next = null
        splitNode.prev = null
    else:
        // Split at head - original list becomes empty
        list.head = null
        list.tail = null
    
    return newList
 
// Merge two lists: O(1)
Merge(list1, list2):
    if list1.tail != null:
        list1.tail.next = list2.head
    else:
        list1.head = list2.head
    
    if list2.head != null:
        list2.head.prev = list1.tail
    
    if list2.tail != null:
        list1.tail = list2.tail
    
    // list2 is now empty/invalid
    return list1

Criterion 5: Real-Time and Latency-Sensitive Systems

For systems with strict latency bounds, this occasional O(n) spike may be unacceptable:

Audio processing: A 1ms delay causes audible glitches
Industrial control: Missed deadlines can cause physical damage
Trading systems: Microseconds matter for order execution
Gaming: Frame drops are immediately visible to users

Linked lists provide bounded worst-case time:

Worst-Case Time Complexity Comparison
Operation	Dynamic Array (Worst Case)	Linked List (Worst Case)
Append	O(n) — reallocation and copy	O(1) — allocate single node
Prepend	O(n) — shift all elements	O(1) — update head pointer
Delete at head	O(n) — shift all elements	O(1) — update head pointer
Insert at known position	O(n) — shift elements	O(1) — update pointers

Memory allocation in real-time contexts:

A common concern is that linked list operations require memory allocation, which itself can have variable latency. Real-time systems address this through:

Object pools: Pre-allocate a pool of nodes. Acquiring and releasing nodes becomes O(1) with bounded time.
Arena allocation: Allocate nodes from a pre-allocated memory region. No system calls during operation.
Static maximum sizing: If the maximum collection size is known, pre-allocate all nodes at startup.

With these techniques, linked lists provide truly bounded operation times — essential for hard real-time systems.

Example: Audio Buffer Management

A digital audio workstation manages buffers of audio samples:

Buffers are queued for processing, then returned to a free pool
Processing latency must stay under ~5ms to avoid audible artifacts
The system handles variable numbers of audio tracks

With arrays: Buffer queues might resize during peak activity, causing latency spikes precisely when the system is under stress.

With pre-pooled linked lists: Queue and dequeue operations are O(1) with bounded constant. No allocation spikes. Consistent latency regardless of load.

Real-Time Requires Holistic Design

Criterion 6: Building Other Data Structures

Data structures commonly implemented with linked lists:

Linked List as Implementation Foundation

•Stack — Linked list with operations at head only. O(1) push and pop without capacity limits.
•Queue — Linked list with operations at both ends. O(1) enqueue (tail) and dequeue (head).
•Deque (Double-Ended Queue) — Doubly linked list with O(1) operations at both ends.
•Hash Table Chaining — Collisions stored in linked lists per bucket. Dynamic chain length.
•Adjacency List Graphs — Each vertex's neighbors stored in a linked list. Dynamic neighbor sets.
•Free Lists in Memory Allocators — Freed blocks linked together for reuse.
•Symbol Tables — Scope chains in compilers often use linked structures.

Why linked lists for these structures:

Each of these structures benefits from linked list properties:

Stacks and Queues: Operations only at endpoints — linked lists provide O(1) there. No random access needed.
Hash Table Chaining: Chain lengths vary widely. A hash table with 10,000 buckets might have chains ranging from 0 to 100 elements. Arrays would waste space on empty/short buckets or require complex sizing.
Graph Adjacency Lists: Vertex degrees vary dramatically. A social network might have users with 10 friends and users with 10,000 friends. Linked lists accommodate this naturally.
Memory Allocators: Free blocks have inherent link structure — each block can contain a pointer to the next free block at no additional memory cost.

Implementation vs Interface

Quick Decision Checklist for Linked Lists

Here is a practical checklist for determining whether linked lists are appropriate for your use case. If you can answer "yes" to most of these questions, a linked list is likely the right choice.

Linked List Decision Criteria

•Operations at ends? Are most operations at the head or tail of the collection?
•Maintain node references? Can you design your algorithm to hold references to nodes rather than indices?
•Frequent mid-list changes? Do you frequently insert or delete at positions other than the end?
•Stable references needed? Do external components need to hold stable references into the collection?
•Merge/split operations? Do you need to combine or divide collections efficiently?
•Bounded worst-case? Is worst-case latency more important than average-case throughput?
•Variable size? Does the collection size fluctuate significantly and unpredictably?
•Little random access? Is random access by index rarely or never needed?
•Large elements? Are elements large enough that pointer overhead is negligible?

Strength of Recommendation Based on Criteria Match
Criteria Matched	Recommendation
0-2	Strongly prefer arrays
3-4	Arrays likely better, but profile if performance matters
5-6	Linked list likely appropriate
7-9	Strongly prefer linked lists

When in Doubt, Profile

Summary: When Linked Lists Win

This page has identified the specific scenarios where linked lists provide genuine advantages over arrays. Let's consolidate these criteria:

Key Takeaways

•Frequent insertion/deletion at known positions — O(1) with node reference, vs O(n) for arrays.
•Unpredictable size with stability requirements — No reallocation spikes, no over-provisioning.
•Stable references — Node pointers remain valid through other modifications.
•Fast merge and split — O(1) operations impossible with arrays.
•Real-time constraints — Bounded worst-case operation time.
•Implementing other structures — Stacks, queues, deques, hash table chains, and more.

The mental model:

What's next:

Now we'll examine the opposite perspective: the criteria for choosing arrays. Understanding both sides of the decision completes your mental framework for data structure selection.

Page Complete