Linked List

Also Known As

TL;DR

Explanation

Unlike arrays, linked lists do not store elements contiguously in memory. Singly linked lists have one pointer (next); doubly linked lists have two (next and prev); circular lists loop back to the head. The trade-off: O(1) insert/delete at a known node, but O(n) access by index. PHP's SplDoublyLinkedList implements this. Linked lists underlie many higher-level structures: stacks, queues, and LRU caches.

Diagram

flowchart LR
    subgraph Singly_Linked[Singly Linked]
        H[Head] --> N1["data=A<br/>next →"] --> N2["data=B<br/>next →"] --> N3[data=C<br/>next=null]
    end
    subgraph Doubly_Linked[Doubly Linked]
        D1["← prev<br/>data=A<br/>next →"] <--> D2["← prev<br/>data=B<br/>next →"] <--> D3["← prev<br/>data=C<br/>next=null"]
    end
    subgraph Complexity
        OPS[Insert at known node O 1<br/>Delete at known node O 1<br/>Access by index O n]
    end
style H fill:#6e40c9,color:#fff
style N3 fill:#238636,color:#fff

Common Misconception

Why It Matters

Common Mistakes

• Using array_shift() on large arrays in PHP — O(n) reindex; use SplQueue (doubly linked) for O(1) dequeue.
• Not tracking the tail pointer — appending to a singly linked list is O(n) without it.
• Forgetting to update both next and prev pointers in a doubly linked list — creates broken links.
• Using a linked list where random access is needed — O(n) traversal makes it the wrong choice.

Code Examples

// Array used as queue — O(n) shift on large datasets:
$queue = [];
for ($i = 0; $i < 100000; $i++) array_push($queue, $i);
$next = array_shift($queue); // Reindexes 99,999 elements — O(n)

// SplQueue (doubly linked) — O(1) enqueue and dequeue:
$queue = new SplQueue();
for ($i = 0; $i < 100000; $i++) $queue->enqueue($i);
$next = $queue->dequeue(); // O(1) — no reindex

References

• ↗ https://www.php.net/manual/en/class.spldoublylinkedlist.php

Tags

Related Terms