Skip to content
Tutorials Center
My learning

Topics

Lesson 137 of 156 Β· Data Structures and Algorithms

Data Structures in JavaScript

Build stacks, queues, linked lists, binary search trees and graphs with JavaScript classes, and learn when a built-in Array, Map or Set is the better choice.

A data structure is a way of arranging data so that the operations you need are easy and fast. An array is great when you read items by position. A Map is great when you look things up by key. Choose the wrong shape and a program that should take a millisecond takes a minute, or your code fills up with clumsy workarounds.

JavaScript gives you a few powerful built-ins, and most of the time they are all you need. Some problems, though, have a natural shape of their own: an undo history, a waiting line, a family tree, a map of roads between cities. In this lesson you will build the classic structures (stack, queue, linked list, tree and graph) with classes, see what each one is good at, and learn how to pick between them and the built-ins.

Start with the built-ins

Before you write a class, check whether a built-in already fits. Here is what each one does quickly, and what it does slowly. "Fast" means the time stays about the same no matter how big the collection gets; "slow" means it grows with the number of items. The next lesson calls these O(1) and O(n).

Structure Fast Slow
Array Read/write by index, push, pop shift, unshift, splice in the middle, includes/indexOf
Object Read/write by a string key Counting keys, keys that aren't strings
Map get, set, has, delete by any key, size Finding an entry by its value
Set add, has, delete, size Reading "the third item"

Two habits come out of this table. If you call includes() inside a loop on a big array, switch to a Set. If you keep looking items up by ID, put them in a Map keyed by that ID. The rest of this lesson covers what to do when none of these is quite the right shape.

Stacks: last in, first out

A stack works like a pile of plates. You add to the top and take from the top, so the last item in is the first one out (LIFO). Stacks power undo buttons, the browser's back button, the call stack that runs your functions, and any task where you must "go back" to the most recent unfinished thing.

A JavaScript array is already a perfect stack: push() adds to the end and pop() removes from the end, both fast. Wrapping it in a class gives the idea a name and hides the methods you shouldn't use:

JS A stack that checks brackets

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The #items field is private, so nobody can reach in and splice() the middle of the stack. A stack that only allows push, pop and peek is easier to reason about than a raw array that allows anything.

Queues: first in, first out

A queue is a waiting line: items join at the back and leave from the front, so the first in is the first out (FIFO). Print jobs, messages waiting to be sent, and the "breadth-first" search you will see later all use queues.

The obvious version is an array with push() and shift(). It works, but shift() has to move every remaining item one place to the left. With a few dozen items nobody notices. With a hundred thousand, each shift() is slow. A better queue never moves items; it remembers where the front is:

JS A queue without shift()

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Your timings will vary. Modern engines optimize shift() on some arrays, so the gap may be small in one browser and large in another. The class gives you predictable speed either way.

Need both ends? A deque (double-ended queue) adds and removes at both the front and the back. You can extend the class above with a #head that also moves backwards. For small collections, an array with unshift() and pop() is perfectly fine.

Linked lists

In an array, items sit side by side in numbered slots. In a linked list, each item lives in its own small object called a node, and each node points to the next one. The list itself only remembers the first node (the head) and, often, the last (the tail).

That shape makes some things cheap and others expensive:

  • Adding or removing at the front is fast: just change a pointer. No items move.
  • Reading item number 500 is slow: you have to walk from the head, node by node.

In everyday JavaScript you will rarely need a linked list, because arrays are heavily optimized. But they appear in interviews, in browser and engine internals, and in structures such as LRU caches. Building one is also the best way to get comfortable with references between objects.

JS A singly linked list

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The *[Symbol.iterator]() method is a generator that makes the list work with for...of and spread. Logging playlist.head shows the chain of nested next objects: that nesting is the list.

A doubly linked list gives every node a prev pointer as well, so you can walk backwards and remove a node you already hold in constant time. That is the structure behind most LRU caches.

Stacks and queues built on linked lists

The array-backed stack and queue above are fine for most programs. But a linked list is also the textbook way to build both, and it shows why the structures are cheap: a stack only touches the head, and a queue only touches the head and the tail, so nothing ever has to move.

  • Stack: push adds a new node in front of the head, and pop unlinks the head. Both are O(1).
  • Queue: enqueue links a new node after the tail, and dequeue unlinks the head. Keeping a tail pointer is what makes enqueue O(1); without it you would walk the whole chain.
JS A stack and a queue made of nodes

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The line if (!this.#head) this.#tail = null is the classic bug spot. If you forget it, #tail keeps pointing at a node that is no longer in the queue, and the next enqueue attaches the new item to that dead node, so it is lost.

A circular queue with a fixed size

Sometimes you want a queue that never grows: the last 50 log lines, a buffer of audio samples, a fixed number of waiting jobs. A circular queue (ring buffer) stores items in a fixed-size array and moves two positions around it instead of moving items. When an index reaches the end of the array, % capacity wraps it back to 0.

JS A ring buffer queue

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Look at the last line of output: the raw slots are 5, 6, 3, 4, but the queue's logical order is 3, 4, 5, 6, because the oldest item sits at index 2 and the queue wraps around the end. Every operation is O(1) and no memory is allocated after the constructor. The price is a hard limit; when full, you either refuse new items (as here) or overwrite the oldest one, which is how a "keep the last N" buffer works.

Inserting and deleting inside a list

The LinkedList above can add at the front and the back and remove by value. Real tasks need more: put an item at a given position, remove by position, or delete a node when all you hold is the node itself. All of them boil down to one idea: walk to the node before the change, then rewire one or two next pointers.

JS insertAt, removeAt, deleteNode and reverse

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Three details deserve attention:

  1. Order of rewiring matters. In insertAt, the new node is created with before.next as its own next before before.next is changed. Do it the other way round and you lose the rest of the list.
  2. Index 0 is a special case, because there is no node before the head; the head pointer itself changes.
  3. deleteNode is a trick, not a true deletion: it overwrites the node with its successor's value. It works when other code only holds the node you want to remove, but it cannot remove the last node, and any outside reference to the successor node now points at an orphan. Prefer removeAt when you can.

reverse() is a favorite interview question. It needs only three variables (previous, current, next), runs in O(n) time and uses O(1) extra memory because it flips the pointers in place.

Trees

A tree is a set of nodes where each node has children, and every node except the top one (the root) has exactly one parent. You already work with trees all the time: the DOM is a tree of elements, a folder on disk is a tree of files, and nested JSON is a tree of values. Walking a tree is a natural fit for recursion.

A binary search tree (BST) is a special tree where each node has at most two children and follows one rule: everything in the left subtree is smaller than the node, and everything in the right subtree is larger. That rule means a search can skip half of the remaining tree at every step, like looking up a word in a dictionary.

JS A binary search tree

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Notice the last three lines. When values arrive in random order, the tree stays bushy and a search takes only a few steps. When they arrive already sorted, every node hangs off the right of the previous one, and the tree degrades into a slow linked list. Real-world trees, such as the red-black trees inside databases, rebalance themselves to avoid this. That is a big topic of its own; just remember that a plain BST is only fast when it is balanced.

Walking any tree

Most trees you meet in JavaScript are not binary. A menu, a comment thread or a file tree is usually an object with a children array. The same recursive idea works:

JavaScript
function countFiles(folder) {
  let total = folder.files?.length ?? 0;
  for (const child of folder.children ?? []) {
    total += countFiles(child);
  }
  return total;
}

This is a depth-first walk: it goes all the way down one branch before moving to the next. For very deep trees (thousands of levels), switch to a loop with your own stack to avoid a "Maximum call stack size exceeded" error.

Graphs

A graph is the most general structure: a set of nodes (also called vertices) connected by edges, with no root and no rule against loops. Road maps, social networks, links between web pages and task dependencies are all graphs. Edges can be one-way (directed, like "follows" on a social site) or two-way (undirected, like a road you can drive both ways).

The usual way to store a graph in JavaScript is an adjacency list: a Map from each node to a Set of its neighbors. Adding an edge and checking whether two nodes are connected are both fast.

To find the shortest route (fewest edges) between two nodes, use breadth-first search (BFS). It explores all neighbors one step away, then all nodes two steps away, and so on, using a queue so the nearest nodes are always handled first:

JS A graph with breadth-first search

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The cameFrom map does two jobs. It remembers which nodes were already seen, so the search never loops forever around a cycle, and it records how each node was reached, so the path can be rebuilt backwards from the goal.

If edges have different costs (minutes, kilometers), BFS is no longer enough: you need Dijkstra's algorithm, which uses a priority queue (usually a structure called a binary heap) to always expand the cheapest route next. JavaScript has no built-in heap, so you would write one or use a library.

Choosing a structure

When you face a new problem, ask what you will do most often, then pick the structure that makes that operation fast:

You mostly need to… Use
Keep items in order and read them by position Array
Look up values by a key or ID Map (or an object for fixed string keys)
Check "have I seen this?" or remove duplicates Set
Undo, go back, match brackets, track nested work Stack (array with push/pop)
Process items in arrival order Queue (head-index class, or an array for small sizes)
Insert and remove at the front very often Linked list or deque
Represent nesting (menus, folders, the DOM) Tree of objects with children
Model connections and find routes Graph as a Map of Sets
Always grab the smallest or most urgent item Priority queue (binary heap)

Measure before you optimize. For a few hundred items, almost any structure is fast enough, and clear code matters more. Reach for a custom structure when a profiler, or a quick console.time(), shows that the data structure really is the bottleneck.

Check your understanding

Quick check Β· 5 questions

of 5 answered You scored / 5 Β· perfect!

  1. 1. Your editor needs an undo feature that reverses the most recent change first. Which structure fits?

    Undo follows last in, first out: the newest change is reversed first. That is exactly what a stack's push and pop give you.
  2. 2. Why can array.shift() be slow as a queue's dequeue operation on a very large array?

    Removing index 0 means every other item gets a new index. A queue that just moves a head pointer avoids that work.
  3. 3. In a binary search tree, what does an in-order traversal (left, node, right) produce?

    Everything left of a node is smaller and everything right is larger, so visiting left subtree, node, right subtree yields ascending order.
  4. 4. What is the main reason breadth-first search uses a queue?

    FIFO order means all nodes one step away are processed before any node two steps away, so the first time BFS reaches the goal it has found the shortest path in edges.
  5. 5. You call list.includes(id) inside a loop over 50,000 orders, and it is slow. What is the usual fix?

    Set.has() takes about the same time regardless of size, while includes() scans the array each time.

Summary

  • A data structure arranges data so the operations you use most are fast. Start with Array, Map and Set.
  • A stack is last in, first out (push/pop); a queue is first in, first out. For large queues, track a head index instead of calling shift().
  • A linked list stores items in nodes that point to the next node: cheap inserts at the front, slow access by position.
  • A linked stack only changes the head; a linked queue keeps a head and a tail so both ends are O(1). A circular queue reuses a fixed array with % capacity.
  • To insert or remove by position, walk to the node before the change and rewire next; handle index 0 (the head) separately.
  • A tree has a root and children; a binary search tree keeps smaller values left and larger values right, and is only fast when balanced.
  • A graph connects nodes with edges; store it as a Map of Sets and use breadth-first search to find the shortest path.
  • Pick the structure that makes your most frequent operation fast, and measure before optimizing.

Next: Searching and Sorting Algorithms β€” binary search, four classic sorts and Big-O notation.