Advanced Data Structures

Feb 14, 2026 - Last update: Mar 24, 2026 - 3 min read - 500 words

Edouard Misset

Full Stack Web Developer

TL;DR

Stacks and queues model LIFO/FIFO workflows, linked lists avoid costly shifts, trees represent hierarchies, graphs model networks, and tries power fast prefix lookups. You rarely need these for every app, but knowing them helps you reach for the right structure when performance or modeling starts to matter.

Introduction

While Arrays and Objects cover most day-to-day needs, understanding advanced structures unlocks the ability to solve more complex problems.

Stacks & Queues

While not native classes in JS (usually implemented with Arrays), these patterns are extremely useful.

• Stack (LIFO): Last In, First Out. Think “Undo” functionality.
• Queue (FIFO): First In, First Out. Think background job processing.

Usage with Arrays

// Stack: Undo history
const history: string[] = []
history.push('Type A')
history.push('Type B')
const lastAction = history.pop() // 'Type B'

// Queue: Task processing
const taskQueue: string[] = []
taskQueue.push('Email User')
taskQueue.push('Generate Report')
const nextTask = taskQueue.shift() // 'Email User'

Simple Class Implementation

class Stack<T> {
  private items: T[] = []

  /** Add item on top of the stack */
  push(item: T): void {
    this.items.push(item)
  }

  /** Remove and return the top item from the stack */
  pop(): T | undefined {
    if (this.items.length === 0) return
    return this.items.pop()
  }

  /** View the top item without removing it */
  peek(): T | undefined {
    return this.items[this.items.length - 1]
  }
}

class Queue<T> {
  private items: T[] = []

  /** Add item to the end of the queue */
  enqueue(item: T): void {
    this.items.push(item)
  }

  /**
   * Remove and return the item at the front of the queue
   * Note: shift() is O(n). For true O(1) operations, use a Linked List.
   */
  dequeue(): T | undefined {
    if (this.items.length === 0) return
    return this.items.shift()
  }

  /** View the front item without removing it */
  peek(): T | undefined {
    return this.items[0]
  }
}

Linked Lists

A linear collection of data elements where each element points to the next.

Singly Linked List

Each node contains data and a reference (pointer) to the next node.

Use case: An implementation of a Stack or Queue where you need constant-time O(1) insertion and deletion at the beginning, without shifting all elements like an Array would.

class ListNode<T> {
  value: T
  next: ListNode<T> | undefined = undefined

  constructor(value: T) {
    this.value = value
  }
}

class LinkedList<T> {
  head: ListNode<T> | undefined = undefined

  /** O(1) insertion at the start */
  prepend(value: T): void {
    const newNode = new ListNode(value)
    newNode.next = this.head
    this.head = newNode
  }
}

const list = new LinkedList<string>()
list.prepend('Third')
list.prepend('Second')
list.prepend('First')
// Structure: First -> Second -> Third -> undefined

Doubly Linked List

Each node has pointers to both the next and previous nodes.

Use case: Browser history (Back/Forward buttons), or a music playlist.

class DoublyNode<T> {
  value: T
  next: DoublyNode<T> | undefined = undefined
  prev: DoublyNode<T> | undefined = undefined

  constructor(value: T) {
    this.value = value
  }
}

class DoublyLinkedList<T> {
  head: DoublyNode<T> | undefined = undefined
  tail: DoublyNode<T> | undefined = undefined

  /** O(1) insertion at the end */
  append(value: T): void {
    const newNode = new DoublyNode(value)
    if (!this.tail) {
      this.head = this.tail = newNode
    } else {
      newNode.prev = this.tail
      this.tail.next = newNode
      this.tail = newNode
    }
  }

  /** O(1) insertion at the start */
  prepend(value: T): void {
    const newNode = new DoublyNode(value)
    if (!this.head) {
      this.head = this.tail = newNode
    } else {
      newNode.next = this.head
      this.head.prev = newNode
      this.head = newNode
    }
  }

  /** O(1) deletion from the end */
  removeLast(): T | undefined {
    if (!this.tail) return undefined
    const value = this.tail.value
    if (this.head === this.tail) {
      this.head = this.tail = undefined
    } else {
      this.tail = this.tail.prev
      this.tail!.next = undefined
    }
    return value
  }

  /** O(1) deletion from the start */
  removeFirst(): T | undefined {
    if (!this.head) return undefined
    const value = this.head.value
    if (this.head === this.tail) {
      this.head = this.tail = undefined
    } else {
      this.head = this.head.next
      this.head!.prev = undefined
    }
    return value
  }
}

// Usage example: Music player playlist
const playlist = new DoublyLinkedList<string>()
playlist.append('Bohemian Rhapsody')
playlist.append('Stairway to Heaven')
playlist.append('Hotel California')

// Navigate through the playlist
let currentTrack = playlist.head
console.log(currentTrack?.value) // 'Bohemian Rhapsody'

currentTrack = currentTrack?.next // Move forward
console.log(currentTrack?.value) // 'Stairway to Heaven'

currentTrack = currentTrack?.prev // Move backward
console.log(currentTrack?.value) // 'Bohemian Rhapsody'

Trees

A hierarchical structure consisting of nodes, with a single root node and children nodes.

Use case: The DOM (Document Object Model), file systems, and client-side route trees are all examples of tree structures.

class TreeNode<T> {
  value: T
  children: TreeNode<T>[] = []

  constructor(value: T) {
    this.value = value
  }

  addChild(node: TreeNode<T>): void {
    this.children.push(node)
  }
}

// Modeling a simple HTML structure
const html = new TreeNode('html')
const body = new TreeNode('body')
const div = new TreeNode('div')
const p = new TreeNode('p')

html.addChild(body)
body.addChild(div)
div.addChild(p)

Binary Search Trees (BST)

A specific type of tree where each node has at most two children (left and right). For any node, the left child is smaller and the right child is larger (or equal, depending on how duplicates are handled).

Use case: Efficient searching and sorting — O(log n) for balanced trees. Note: An unbalanced BST (e.g., inserting sorted values) degrades to O(n).

class BinaryNode<T extends number | string> {
  value: T
  left: BinaryNode<T> | undefined = undefined
  right: BinaryNode<T> | undefined = undefined

  constructor(value: T) {
    this.value = value
  }
}

class BinarySearchTree<T extends number | string> {
  root: BinaryNode<T> | undefined = undefined

  insert(value: T): void {
    const newNode = new BinaryNode(value)
    if (!this.root) {
      this.root = newNode
      return
    }
    this.insertNode(this.root, newNode)
  }

  private insertNode(node: BinaryNode<T>, newNode: BinaryNode<T>): void {
    if (newNode.value < node.value) {
      // Go Left
      if (!node.left) node.left = newNode
      else this.insertNode(node.left, newNode)
    } else {
      // Go Right
      if (!node.right) node.right = newNode
      else this.insertNode(node.right, newNode)
    }
  }

  search(value: T): boolean {
    return this.searchNode(this.root, value)
  }

  private searchNode(node: BinaryNode<T> | undefined, value: T): boolean {
    if (!node) return false
    if (value === node.value) return true
    return value < node.value
      ? this.searchNode(node.left, value)
      : this.searchNode(node.right, value)
  }
}

const bst = new BinarySearchTree<number>()
bst.insert(10)
bst.insert(5)
bst.insert(15)
//       10
//      /  \
//     5    15

bst.search(5) // true
bst.search(20) // false

Graphs

A collection of nodes (vertices) and edges that connect pairs of nodes. Graphs can be directed (Twitter followers) or undirected (Facebook friends).

Use case: Social networks, recommendation engines (“People who bought X also bought Y”), and routing algorithms (Google Maps).

class Graph<T> {
  // Adjacency List: Map<Node, Array<Neighbors>>
  adjacencyList: Map<T, T[]> = new Map()

  addVertex(vertex: T): void {
    if (this.adjacencyList.has(vertex)) return

    this.adjacencyList.set(vertex, [])
  }

  addEdge(vertex1: T, vertex2: T): void {
    // Ensure vertices exist before adding edge
    this.addVertex(vertex1)
    this.addVertex(vertex2)
    this.adjacencyList.get(vertex1)!.push(vertex2)
    this.adjacencyList.get(vertex2)!.push(vertex1) // Undirected
  }
}

const socialNetwork = new Graph<string>()
socialNetwork.addVertex('Alice')
socialNetwork.addVertex('Bob')
socialNetwork.addVertex('Charlie')

socialNetwork.addEdge('Alice', 'Bob')
socialNetwork.addEdge('Alice', 'Charlie')
// Alice is friends with Bob and Charlie

Tries (Prefix Trees)

A specialized tree used to store associative data structures. A node’s position in the tree defines the key with which it is associated.

Use case: Autocomplete / Typeahead systems. If you type “Re”, a Trie can efficiently find “React”, “Redux”, “Remix” without scanning a whole database.

class TrieNode {
  children: Map<string, TrieNode> = new Map()
  isEndOfWord: boolean = false
}

class Trie {
  root: TrieNode = new TrieNode()

  insert(word: string): void {
    let current = this.root
    for (const char of word) {
      if (!current.children.has(char)) {
        current.children.set(char, new TrieNode())
      }
      current = current.children.get(char)!
    }
    current.isEndOfWord = true
  }

  search(word: string): boolean {
    let current = this.root
    for (const char of word) {
      const child = current.children.get(char)
      if (!child) return false
      current = child
    }
    return current.isEndOfWord
  }
}

const autocomplete = new Trie()
autocomplete.insert('react')
autocomplete.insert('redux')
// Efficiently stores 'r', 'e', then branches for 'a' and 'd'

Conclusion

Advanced data structures help you model problems more naturally and push performance when arrays and objects start to strain. You do not need them for every project, but keeping them in your toolbox makes the next hard problem feel a lot smaller.

Resources

• Visualizing Data Structures with VisuAlgo
• Singly Linked List by Nicholas C. Zakas
• Doubly Linked List by Nicholas C. Zakas
• Binary Search Tree by Nicholas C. Zakas
• Other data structures by Fireship.io on YouTube

Previous: Revisit Data Structures for the JS basics.

Disclaimer

This article was drafted with the assistance of AI and reviewed/edited by the author.

Tags:

• TypeScript
• Data Structures
• Linked Lists
• Trees
• Binary Search Trees
• Graphs
• Tries

Data Structures