Frontend Linear Data Structures Deep Dive: Arrays, Stacks, Queues, and Linked Lists

The Big Picture

Before diving into stacks, queues, and linked lists, it helps to know where they sit in the landscape.

Linear structures - arrays, linked lists, stacks, queues - arrange elements one after another. Each node has exactly one predecessor and one successor.

Non-linear structures - trees and graphs - are a different story for another day.

Arrays

Arrays are the workhorse of JS. They use contiguous memory and give you direct access to any element by index - no traversal needed.

Adding Elements

push - appends to the end.

Simple enough, but there's a catch: arrays are initialized with a fixed capacity. When you exceed it, JS triggers a resize: allocate a bigger block, copy everything over, free the old space. It's not free.

Linked lists don't have this problem - they allocate memory per node, dynamically.

unshift - prepends to the beginning.

Every existing element has to shift right by one to make room. The longer the array, the worse the performance. Fine for small arrays; avoid it in hot paths.

splice - the Swiss Army knife.

array.splice(startIndex, deleteCount, ...itemsToAdd)

• startIndex: where to begin
• deleteCount: how many to remove (pass 0 to insert without deleting)
• ...itemsToAdd: optional elements to insert

Key things to know: splice mutates the original array and returns the deleted elements as a new array (empty array if nothing was deleted). Like all native array methods - push, pop, unshift, shift - it's not a pure function.

const arr = [1, 2];

arr.splice(1, 0, 3);   // insert 3 at index 1
console.log(arr);      // [1, 3, 2]

arr.splice(1, 1);      // delete element at index 1
console.log(arr);      // [1, 2]

Stack

A stack is LIFO - Last In, First Out. Think of it like a stack of plates: you can only add or remove from the top.

push → [bottom ... top] ← pop

In JS, implement with a plain array:

const stack = [];

stack.push('A');
stack.push('B');
stack.push('C');

while (stack.length) {
  console.log(stack.pop()); // C, B, A
}

• push to add to the top
• pop to remove from the top
• Peek without removing: stack[stack.length - 1]

Queue

A queue is FIFO - First In, First Out. Like a checkout line: first in, first served.

push → [back ... front] → shift

const queue = [];

queue.push('Alice');
queue.push('Bob');
queue.push('Charlie');

while (queue.length) {
  console.log(queue.shift()); // Alice, Bob, Charlie
}

Heads up: shift has an O(n) cost - every element shifts left by one index after removal. For small arrays, no big deal. At scale, this becomes a bottleneck. If you're building a high-throughput queue, a linked list implementation is the right call.

Linked Lists

Why Not Just Use Arrays?

Arrays are great when you need fast random access. But inserting or deleting anywhere except the tail requires shifting elements - O(n) work.

Linked lists flip the tradeoff:

Structure

Each node holds two things:

• val: the data
• next: a pointer to the next node (null if it's the tail)

In JS, a linked list is just nested objects:

{
  val: 1,
  next: {
    val: 2,
    next: null
  }
}

To access any element, you start at head and follow next pointers until you reach your target. There's no shortcut - no index to jump to directly.

Basic Implementation

function ListNode(val) {
  this.val = val;
  this.next = null;
}

const head = new ListNode(1);
head.next = new ListNode(2);
// 1 -> 2 -> null

Insert

Find the predecessor node, point its next to the new node, then point the new node's next to the original successor. No data movement, just pointer reassignment - O(1).

Delete

Find the predecessor, skip the target by pointing next directly to the target's successor. Done - O(1).

The expensive part with linked lists isn't insert/delete - it's finding the right node, which always costs O(n).

Two JS Gotchas Worth Knowing

Array Memory Isn't Always Contiguous

JS engines optimize for uniform-type arrays. Mix types and the engine may fall back to a hash map structure internally, losing the contiguous memory layout.

const fast = [1, 2, 3, 4];           // likely contiguous
const slower = ['a', 1, { b: 2 }];   // likely hash map internally

Don't mix types in performance-sensitive arrays.

sort() Sorts Strings by Default

[10, 2, 5].sort()                    // [10, 2, 5] - ASCII order, wrong
[10, 2, 5].sort((a, b) => a - b)     // [2, 5, 10] - correct

Always pass a comparator when sorting numbers.

Quick Reference

*Amortized - occasional resize at O(n)

Common Pitfalls

• unshift is slow at scale - it shifts every element. Use sparingly.
• Array-based queues degrade - shift is O(n). For high volume, use a linked list.
• All native array methods mutate - push, pop, shift, unshift, splice all modify in place. None are pure functions.
• Don't mix array element types - you lose the contiguous memory advantage.
• Stacks and queues aren't separate data structures - they're arrays (or linked lists) with constrained access rules.
• Linked list insert/delete is fast; finding the node isn't - the O(n) cost is in traversal, not the operation itself.