Linked Lists, Stacks, Queues (with JavaScript examples)

TL;DR: Linear data structures like linked lists, stacks, and queues form the backbone of many algorithms and system designs. While JavaScript’s built-in Arrays can emulate some behaviors, custom implementations of these structures provide O(1) insertion/deletion where arrays would be inefficient. In this post, you’ll learn:

• Linked Lists: how to build a singly linked list, insert/delete nodes, and traverse efficiently.
• Stacks: LIFO structures for undo/redo, parsing, and expression evaluation, implemented via linked lists or arrays.
• Queues: FIFO structures for task scheduling, breadth-first search, and event handling. Every concept comes with concise JavaScript examples to illustrate real‐world usage and performance considerations.

Looking for coding exercises? Check out my challenges page for hands-on problems to test your understanding of these structures.

Why Linear Data Structures Matter

Modern JavaScript applications—whether in the browser or on Node.js—often require efficient ways to insert, delete, and process data. While the built‐in Array type in JavaScript covers a lot of use cases, linked lists, stacks, and queues excel when:

• Frequent Insertions/Deletions at Arbitrary Positions: Arrays incur O(n) shifts; linked lists enable O(1) if you have a reference.
• Controlled Access Patterns: Stacks (LIFO) and queues (FIFO) enforce discipline, reducing bugs in algorithms like parsing or task scheduling.
• Memory Predictability: Custom structures let you manage node allocation and deallocation explicitly, which can help with performance tuning in memory‐sensitive contexts.

Below, we’ll explore each structure, discuss its use cases, and provide idiomatic JavaScript implementations.

1. Linked Lists

A linked list is a chain of nodes where each node holds a value and a reference (pointer) to the next node. The most common variant is the singly linked list. Unlike arrays, inserting or removing a node (when you have a reference to its predecessor) is O(1), because no shifting of elements is needed.

1.1. Node and LinkedList Classes

// Define a node containing data and a pointer to the next node
class ListNode {
  constructor(value) {
    this.value = value
    this.next = null
  }
}

// Singly Linked List with head, tail, and length tracking
class LinkedList {
  constructor() {
    this.head = null
    this.tail = null
    this.length = 0
  }

  // Add a node to the end (tail) of the list
  append(value) {
    const newNode = new ListNode(value)
    if (!this.head) {
      this.head = newNode
      this.tail = newNode
    } else {
      this.tail.next = newNode
      this.tail = newNode
    }
    this.length++
    return this
  }

  // Add a node to the beginning (head) of the list
  prepend(value) {
    const newNode = new ListNode(value)
    if (!this.head) {
      this.head = newNode
      this.tail = newNode
    } else {
      newNode.next = this.head
      this.head = newNode
    }
    this.length++
    return this
  }

  // Remove the first node and return its value
  removeHead() {
    if (!this.head) return null
    const removed = this.head
    this.head = this.head.next
    if (!this.head) this.tail = null
    this.length--
    return removed.value
  }

  // Remove the last node (requires traversal) and return its value
  removeTail() {
    if (!this.head) return null
    if (this.head === this.tail) {
      const value = this.head.value
      this.head = null
      this.tail = null
      this.length = 0
      return value
    }
    let current = this.head
    while (current.next !== this.tail) {
      current = current.next
    }
    const value = this.tail.value
    current.next = null
    this.tail = current
    this.length--
    return value
  }

  // Traverse and print all node values
  traverse() {
    let current = this.head
    while (current) {
      console.log(current.value)
      current = current.next
    }
  }

  // Find a node by value (returns the node or null)
  find(value) {
    let current = this.head
    while (current) {
      if (current.value === value) return current
      current = current.next
    }
    return null
  }
}

1.2. Usage Example

const list = new LinkedList()
list.append(10).append(20).prepend(5)
// List: 5 → 10 → 20

console.log('Head:', list.head.value) // 5
console.log('Tail:', list.tail.value) // 20

list.traverse()
// Output:
// 5
// 10
// 20

console.log('Removed head:', list.removeHead()) // 5
console.log('New head:', list.head.value) // 10

console.log('Removed tail:', list.removeTail()) // 20
console.log('New tail:', list.tail.value) // 10

When to Use Linked Lists

• Dynamic Insertion/Deletion: Real‐time systems where list size changes frequently (e.g., a job queue where jobs get reprioritized).
• Intermediate Data Layers: Implementing more complex structures like adjacency lists for graphs.
• Memory‐Conscious Contexts: When you want to avoid large contiguous memory blocks (e.g., in some low‐memory IoT environments using Node.js on embedded devices).

2. Stacks

A stack is a Last‐In‐First‐Out (LIFO) structure. Think of stacking plates: you push plates onto the top and pop them off from the top. Stacks are used in:

• Recursion and call stacks (behind the scenes in JS engines).
• Undo/Redo functionality in editors.
• Expression evaluation (converting infix to postfix, or evaluating postfix notation).
• Depth‐First Search (DFS) in graph algorithms.

2.1. Array‐Based Stack

class ArrayStack {
  constructor() {
    this.items = []
  }

  // Push element onto the top
  push(value) {
    this.items.push(value)
  }

  // Pop element from the top
  pop() {
    return this.items.pop() || null
  }

  // Peek at the top element without removing
  peek() {
    return this.items[this.items.length - 1] || null
  }

  // Check if empty
  isEmpty() {
    return this.items.length === 0
  }

  size() {
    return this.items.length
  }
}

// Usage:
const stack = new ArrayStack()
stack.push(1)
stack.push(2)
console.log(stack.peek()) // 2
console.log(stack.pop()) // 2
console.log(stack.size()) // 1

2.2. Linked-List-Based Stack

A linked-list‐based stack avoids resizing overhead of arrays and guarantees O(1) push/pop.

class LinkedListStack {
  constructor() {
    this.top = null // points to the head node
    this.length = 0
  }

  // Push: insert at head
  push(value) {
    const newNode = new ListNode(value)
    if (this.top) newNode.next = this.top
    this.top = newNode
    this.length++
  }

  // Pop: remove from head
  pop() {
    if (!this.top) return null
    const removed = this.top
    this.top = this.top.next
    this.length--
    return removed.value
  }

  peek() {
    return this.top ? this.top.value : null
  }

  isEmpty() {
    return this.length === 0
  }
}

// Usage:
const llStack = new LinkedListStack()
llStack.push('A')
llStack.push('B')
console.log(llStack.peek()) // 'B'
console.log(llStack.pop()) // 'B'
console.log(llStack.pop()) // 'A'
console.log(llStack.pop()) // null

3. Queues

A queue is a First‐In‐First‐Out (FIFO) structure: think of waiting in line. The first element enqueued is the first dequeued. Common uses include:

• Task scheduling (e.g., event loops, microtask queues).
• Breadth‐First Search (BFS) in trees/graphs.
• Rate limiting or buffering I/O requests.

3.1. Array‐Based Queue (Circular Buffer)

A naïve array‐based queue (using push and shift) is O(n) on shift. To achieve amortized O(1), implement a circular buffer or use two stacks. Here’s a simple circular‐buffer approach:

class CircularQueue {
  constructor(capacity = 100) {
    this.items = new Array(capacity)
    this.head = 0
    this.tail = 0
    this.size = 0
    this.capacity = capacity
  }

  // Enqueue: add at tail
  enqueue(value) {
    if (this.size === this.capacity) {
      throw new Error('Queue is full')
    }
    this.items[this.tail] = value
    this.tail = (this.tail + 1) % this.capacity
    this.size++
  }

  // Dequeue: remove from head
  dequeue() {
    if (this.size === 0) return null
    const value = this.items[this.head]
    this.head = (this.head + 1) % this.capacity
    this.size--
    return value
  }

  peek() {
    return this.size === 0 ? null : this.items[this.head]
  }

  isEmpty() {
    return this.size === 0
  }

  isFull() {
    return this.size === this.capacity
  }
}

// Usage:
const queue = new CircularQueue(5)
queue.enqueue(10)
queue.enqueue(20)
console.log(queue.peek()) // 10
console.log(queue.dequeue()) // 10
console.log(queue.dequeue()) // 20
console.log(queue.dequeue()) // null

3.2. Two‐Stack Queue (Amortized O(1))

By using two stacks, you can implement a queue where each element moves at most twice, achieving amortized O(1) for both enqueue and dequeue.

class TwoStackQueue {
  constructor() {
    this.inStack = []
    this.outStack = []
  }

  // Push onto inStack
  enqueue(value) {
    this.inStack.push(value)
  }

  // Pop from outStack; if empty, pour all inStack into outStack
  dequeue() {
    if (this.outStack.length === 0) {
      while (this.inStack.length > 0) {
        this.outStack.push(this.inStack.pop())
      }
    }
    return this.outStack.pop() || null
  }

  peek() {
    if (this.outStack.length > 0) {
      return this.outStack[this.outStack.length - 1]
    }
    return this.inStack.length > 0 ? this.inStack[0] : null
  }

  isEmpty() {
    return this.inStack.length === 0 && this.outStack.length === 0
  }
}

// Usage:
const tsQueue = new TwoStackQueue()
tsQueue.enqueue('x')
tsQueue.enqueue('y')
console.log(tsQueue.peek()) // 'x'
console.log(tsQueue.dequeue()) // 'x'
console.log(tsQueue.dequeue()) // 'y'

4. Comparing and Use Cases

1. Linked Lists vs. Arrays

   • Arrays excel at random access (O(1)) but cost O(n) for insert/delete at arbitrary positions.
   • Linked lists guarantee O(1) insertion/deletion at head or tail (if tail pointer is maintained), but O(n) to search or access by index.

2. Stack Use Cases

   • Call Stack Emulation: Language runtimes use LIFO for function calls.
   • Expression Evaluation: Converting infix expressions to postfix or evaluating postfix expressions.
   • Backtracking: Solving puzzles (e.g., Sudoku) where you need to revert to a previous state.

3. Queue Use Cases

   • Task Scheduling: Event loops in browsers/Node.js maintain a microtask/macrotask queue.
   • BFS Traversal: Visiting all nodes in a tree or graph level by level.
   • Rate Limiting: Buffering API calls to avoid overloading a server.

5. Best Practices & Tips

1. Choose the Right Implementation

   • For small‐to‐medium datasets where occasional shifting is acceptable, JavaScript’s Array can serve as a stack (push/pop) or a simple queue (push/shift)—but be aware of O(n) cost on shift.
   • For large or performance‐critical systems, implement a linked list or circular buffer where insert/delete costs matter.

2. Keep Node Logic Simple

   • In a linked list, each ListNode should hold only value and next. Avoid adding metadata unless necessary (e.g., doubly linked lists need prev).
   • Modularize common operations (e.g., a prepend and append method) to reduce code duplication and bugs.

3. Handle Edge Cases Explicitly

   • Always check for empty structures before pop/dequeue to avoid returning undefined or causing null‐reference errors.
   • When removing the last node in a linked list (or the only element in a stack/queue), reset both head/tail or top pointers to null to prevent memory leaks.

4. Monitor Memory Usage

   • For extremely large queues (e.g., task/event buffering), consider periodically trimming or batching operations so that you don’t hold on to thousands of queued items unbounded.
   • When implementing custom structures in Node.js, track and release references (e.g., set removed node’s next to null) to help V8’s garbage collector.

5. Leverage Existing Libraries When Appropriate

   • Immutable.js or Mori provide persistent (immutable) linked list and stack data structures that can simplify state management in React/Redux applications.
   • Deque libraries (double‐ended queues) give you O(1) insert/delete at both ends if your use case requires more flexibility than a simple queue.

Final Thoughts

Understanding linked lists, stacks, and queues is essential for writing efficient JavaScript code, especially when you need precise control over insertion/deletion time complexity and memory patterns. By:

• Implementing a linked list, you gain O(1) insertion/deletion without costly array shifts.
• Using a stack, you ensure LIFO order—ideal for parsing, backtracking, and managing function call contexts.
• Adopting a queue, you enforce FIFO order—critical for scheduling tasks, event handling, and BFS.

While modern JavaScript engines and high‐level libraries handle many data‐structure concerns for you, mastering these fundamentals empowers you to choose the right tool for each problem, optimize performance, and write robust, maintainable code. If you’re ready to put these concepts into practice, explore additional exercises on my challenges page!