This site's Linear category holds eleven entries, and unlike most of this site's other categories, seven of them aren't variants competing for the same job — the other four, Monotonic Stack, Monotonic Deque, XOR Linked List, and Sparse Set, are set aside below: the first two because neither is a storage option at all, the third for a different reason entirely, and the fourth because it answers a different question ("is v a member") than every other entry here ("how should this sequence be stored") — see each one's own note. The remaining seven do split into real shapes: Dynamic Array and Linked List are two different storage shapes for the same sequence, already framed as a direct trade against each other in both of their own opening paragraphs. Doubly Linked List is an extension of the second. Stack, Queue, Circular Buffer, and Deque aren't a third storage shape at all — they're access-discipline wrappers that sit on top of whichever shape you'd have picked anyway. Stack's own reference implementation wraps a plain array and says directly that "a linked list with a head pointer works just as well"; Queue's says the same about "a linked list with head and tail pointers." So this guide isn't one flat table — it's a funnel of four questions, each one ruling out the structures that don't fit before the next question ever comes up.
arr[i] at an arbitrary
position, not just an end?If yes, the choice is already made: Dynamic
Array is the only one of the six that gives O(1) get/set
at an arbitrary index — its own Complexity
section states it plainly. Every other structure here pays O(n) for the same
lookup; Linked List's own Complexity section calls
random access by index "the core trade the structure makes" against getting cheap insert/remove in
exchange. Nothing below beats a dynamic array for this need, and nothing below needs to be
considered if this is the only requirement. If the answer is no — nothing ever needs to jump
straight to index 400 — keep going.
This is the fork that separates the three access-discipline wrappers from the linked-list family. If the workload ever needs to remove or insert a node it already has a direct reference to — not search for it, just unlink or relink it — array-backed storage is the wrong shape no matter how the ends are used, because removing from the middle of an array means shifting every element after it. That need points at the two remaining questions below in order.
A singly linked node only knows what comes after it. Given a direct reference to some node
n, removing n still means finding its predecessor — the node
whose next currently points at n — and the only way to find that
predecessor is to walk from the head comparing curr.next === n until it matches, per
Doubly Linked List's own explanation of the
problem it solves. Its own Pitfalls
section shows the classic workaround and exactly where it fails: the "copy trick" — copy
n.next's value into n, then splice out n.next instead —
correctly turns 1 → 2 → 3 into 1 → 3 when n is the middle
node, but returns false and leaves the chain untouched when n is the
tail, because there's no n.next left to copy from. A prev pointer removes
the problem entirely — n.prev is the predecessor, already in hand — at the cost of a
second pointer on every node, whether or not it's ever used. Need O(1) removal
by reference alone, or backward traversal from the tail: Doubly Linked List, whose own Complexity
section gives removeNode given a reference as O(1) — "the structure's
whole reason to exist." Forward-only is fine, and the predecessor is always naturally in
hand when a removal happens (a queue draining its own head, say): plain Linked List gets the same O(1)
insertFront/insertBack for one pointer per node instead of two.
If every add and remove happens at an end, the next question is which end (or ends) and in what
order. Stack and Queue are already cross-linked on this site as mirror
images of each other — queue.html's own text calls stack "its mirror image — same 'add/remove from
an end' shape, opposite ordering." Last in, first out, one end only (whatever was
pushed most recently comes back first — a call stack, an undo list, matching nested brackets): Stack. First in, first out, one end only
(whatever's been waiting longest comes back first — a print queue, a task queue): Queue, provisionally — one more question decides between
Queue and Circular Buffer below. Both pages carry the same warning about mixing them up: stack's
own Pitfalls section notes that an array's push() + shift() pair "gives
you queue behavior even though push sounds like a stack operation" — check which end
is actually being removed from, not the method name. Both ends are actively pushed to or
popped from — not just one end's discipline, but a workload that genuinely needs
pushFront/popBack or the reverse, such as a Monotonic Deque's sliding window or 0-1 BFS pushing
zero-weight edges to the front and one-weight edges to the back: Deque, whose own opening line frames it as generalizing
both of the other two — "use only pushBack/popBack and it behaves
exactly like a Stack; use pushBack/popFront and it behaves exactly like
a Queue." A workload that only ever touches one end consistently doesn't need a deque's extra
interface surface — Stack or Queue says the same thing more plainly.
Circular Buffer's own opening line frames
itself exactly this way: "a Queue with one rule change that makes a real difference: capacity is
fixed forever." Instead of growing a backing array when it fills, a ring buffer wraps its write
position back to index 0 once it runs off the end, reusing slots a pop() already
freed — nothing ever reallocates. That trade pays off as a stronger guarantee: its own Complexity section gives
push/pop/peek as O(1) worst case, not just
amortized — "the one guarantee a ring buffer gives that a growable Queue or Dynamic Array
can't quite match." Plain Queue's own Complexity section
is explicit that its O(1) is amortized "for the array-backed version" — an occasional
resize or compaction still happens, it's just rare enough to average out. Capacity is
naturally bounded and will never need to grow past it (a fixed-size sliding window, a
bounded event log, backpressure by design): Circular Buffer — but its own Pitfalls section warns the fixed-capacity
win isn't free: a naive head === tail emptiness check can't tell a completely empty
buffer from a completely full one, silently overwriting live data the caller thinks is still
there, unless the implementation tracks a count explicitly. Capacity should grow to fit
whatever arrives, no hard ceiling: plain Queue —
the simpler default, and the right one whenever "how much could there be" doesn't have a firm
answer in advance.
| Entry | Role | Time | Space | Reach for it when |
|---|---|---|---|---|
| Dynamic Array | indexed storage | get/set O(1); push/pop O(1) amortized; insert/delete at index O(n) | O(n), with slack | need indexed random access anywhere in the sequence |
| Linked List | pointer-chained storage | insertFront/insertBack O(1); find/deleteValue O(n) | O(n) + 1 pointer/node | splice given a reference, predecessor always naturally in hand |
| Doubly Linked List | + backward pointer | insertFront/insertBack O(1); removeNode(ref) O(1); findValue O(n) | O(n) + 2 pointers/node | O(1) removal by reference alone, or backward traversal |
| Stack | LIFO discipline | push/pop/peek O(1) amortized; search O(n) | O(n) | add and remove from one end only, last in first out |
| Queue | FIFO discipline | enqueue/dequeue/peek O(1) amortized; search O(n) | O(n) | add at rear, remove at front, capacity grows as needed |
| Circular Buffer | FIFO, fixed capacity | push/pop/peek O(1) worst case | O(capacity), fixed | FIFO with a capacity that's naturally bounded, never grows |
| Deque | both ends open | pushFront/pushBack/popFront/popBack/front/back O(1) amortized | O(n), with slack | both ends actively used — not just one end's discipline |
Monotonic Stack and Monotonic Deque don't answer any of the four
questions above, because neither is competing to be the sequence's storage — each is a technique
layered on top of one of the structures above for one specific job. Monotonic Stack sits on Stack: given an array, find the next larger (or smaller)
value to the right of every position, in one O(n) pass instead of an
O(n²) all-pairs check. Monotonic Deque sits on Deque: the same pop-before-push invariant applied from both
ends instead of one, answering a sliding window's maximum (or minimum) at every position in one
O(n) pass instead of an O(n·k) recompute-each-window scan. Whichever of
the seven structures above ends up holding the actual data, both of these are separate, temporary
structures built during a scan and thrown away once the answers are computed.
XOR Linked List doesn't answer any of the four questions above either, but not because it isn't a storage option — it's the same shape as Doubly Linked List, bidirectional traversal and all, at half the per-node memory. It's set aside because this guide's four-question funnel is about choosing among options actually available in a language like the one this site's demos run in, and XOR Linked List needs something JavaScript (and Java, and Python, and Go) never hands out: a real memory address to XOR. Its own Where XOR linked lists show up section is explicit about this — every reference implementation on this site's XOR Linked List page fakes an address with an array index, because there's no other way to demonstrate it here at all. If the workload genuinely runs in C or a similarly low-level environment with real addressable memory and every byte per node is budgeted for, it's a real answer to the same question Splicing in the middle above asks; anywhere else, Doubly Linked List is the only version actually on offer.
Sparse Set is set aside for a reason none of the other three exceptions share: it isn't a sequence storage option, a technique layered on one, or an alternative-environment version of one — it doesn't answer "how should this sequence be stored" at all. It answers "is v currently a member," over a fixed small-integer universe, with true O(1) insert, contains, delete, and clear, the last of which nothing else on this page offers (the seven real storage options above are all O(n) to empty at best). If the workload is "track membership over a bounded integer range, rebuilt from scratch often," Sparse Set is the answer; if it's "store an ordered sequence," it was never competing for that job in the first place.