Arrays, Linked Lists, Stacks and Queues Visualized

The most useful question about a data structure is not “what is its definition?” It is “which operation does its layout make cheap?” Arrays, linked lists, stacks, and queues all store a sequence, but they make different promises about where work happens.

One sequence, different constraints

An array gives positions names: index 0, index 1, and so on. A linked list gives each value a link to the next node. A stack restricts access to one end, and a queue restricts insertion and removal to opposite ends. Stacks and queues describe an access discipline, not a required physical representation.

The table is a guide, not a substitute for the operation. “Insert is $O(1)$ in a linked list” hides the cost of finding the insertion point. $O(1)$ also describes growth with input size, not a guarantee that every runtime or allocation is equally fast.

Arrays: locations make reads cheap

Conceptually, an array stores elements in contiguous slots. If the first slot has an address and each element has a known width, index $i$ is computed by an offset. That is why values[i] is $O(1)$: no earlier value must be visited.

const scores = [82, 91, 76, 88];
const third = scores[2]; // 76

scores.splice(1, 0, 95); // elements at 1..end move right
scores.splice(2, 1);     // later elements move left

An insertion at the end is different. Dynamic arrays reserve spare capacity; when there is room, append writes one slot. Occasionally the backing storage grows and all elements are copied. Across many appends, that expensive copy is spread out, so append is amortized $O(1)$.

JavaScript arrays are high-level runtime objects, not a promise of a raw C-style array layout. Engines can optimize them differently as values and shapes change. The array model still explains why indexed access and middle shifts are the useful conceptual costs.

Arrays are usually the default in application code. They are simple, compact, friendly to CPU caches when values are laid out densely, and support iteration well.

Linked lists: links make local rewiring cheap

A singly linked list stores a value and a reference to the next node. A doubly linked list also stores a previous reference. There is no formula that jumps to “node 37”; traversal starts at the head and follows links.

type Node<T> = { value: T; next: Node<T> | null };

function insertAfter<T>(node: Node<T>, value: T): void {
  node.next = { value, next: node.next };
}

function removeAfter<T>(node: Node<T>): void {
  if (node.next) node.next = node.next.next;
}

The rewiring in insertAfter is O(1), but only after the node is known. Searching from the head for that node remains O(n). Nodes also carry reference overhead and can be dispersed in memory, so pointer chasing tends to have worse locality than a compact array. This is why ordinary product code uses linked lists less often than introductory courses suggest.

Stacks: last in, first out

A stack exposes push, pop, and peek at the top. The last item pushed is the first removed. Function calls use the same broad discipline: the most recent call must return before its caller can finish. DFS, undo histories, parsing nested syntax, and backtracking all fit LIFO behavior.

const undo: string[] = [];
undo.push("rename");
const lastAction = undo.pop();

An array is often an excellent stack implementation because its end operations are amortized O(1). A linked list can implement one too; the abstraction does not choose the storage.

Queues: first in, first out

A queue exposes enqueue at the back and dequeue at the front. BFS uses a queue because it must process every discovered node at the current distance before moving farther away. Schedulers and producer/consumer pipelines use the same ordering idea.

Repeatedly removing index 0 from a simple array can require shifting remaining elements depending on the runtime. A practical queue often tracks head and tail positions in a circular buffer, reusing slots as the ends wrap around.

Common mistakes and choices

• A linked-list insert is not magically O(1) when the position still needs an O(n) search.
• A stack or queue can be backed by an array, a linked structure, or a specialized deque.
• An array’s O(1) access does not mean all array operations are O(1).
• Choose an array first when you need iteration, indexing, and compact storage. Choose a queue for fair arrival order and a stack for nested or reversible work.

Connections

Hash tables use arrays of buckets. Recursion uses a call stack. BFS uses queues while iterative DFS uses stacks. These structures are small building blocks, but their operational constraints explain much larger algorithms.

Summary

Layout determines cost. Arrays buy direct access; linked lists buy local rewiring once a node is known; stacks and queues make one ordering rule explicit. Use the visualizer to compare the hidden work—shifts, traversal, and end operations—rather than memorizing a table alone.