Linked List
debt(d7/e3/b3/t5)
Closest to 'only careful code review or runtime testing' (d7). The detection_hints list only Blackfire (a profiler) and note 'automated: no'. The misuse pattern — using array_shift()/array_unshift() on large arrays instead of SplDoublyLinkedList — won't be caught by a linter or compiler; it requires profiling under load or careful code review to notice the O(n) performance penalty.
Closest to 'simple parameterised fix' (e3). The quick_fix points to swapping PHP arrays for SplDoublyLinkedList/SplQueue. This is more than a single-line patch — callers must be updated to use the Spl API (push/pop/unshift instead of array functions) — but it's contained within one component or data-access layer, not a cross-cutting refactor.
Closest to 'localised tax' (b3). The choice applies to specific collections within web or CLI contexts. Once the correct structure is chosen, the rest of the codebase is unaffected. The debt is felt only in the component that handles the data structure, not system-wide.
Closest to 'notable trap' (t5). The misconception field states developers wrongly assume linked lists are always slower than arrays, when in fact they are O(1) for mid-list insertions/deletions vs O(n) for arrays. Conversely, common_mistakes show developers also misuse PHP arrays (treating them as linked lists) and forget pointer bookkeeping. These are documented, well-known gotchas that most developers learn after the fact, consistent with a t5 score.
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