Skip to content
Lydia Hallie theavocoder
Newsletter
Algorithms / Data structures

Data Structures

Find out how to implement data structures such as linked lists, graphs, hash tables, and trees in JavaScript.

Read the runtime guide first Start with Objects

Why data structures change the answer

A data structure is a way of organizing values so that the operations you care about become cheaper. The right structure can turn a slow search into a fast lookup, or make an insertion expensive when you needed it to be cheap. Big O is how we compare those tradeoffs.

Linked lists

A linked list stores each value in a node that also points to the next node. Inserting or removing a node at a known position is cheap because no large block of memory has to shift. Finding a node by position is linear, because you have to walk the chain.

In JavaScript, an object with a value and a next property is enough to build one. The related language ideas are objects, references, and the prototype chain.

Hash tables

A hash table maps keys to values through a hash function. Lookups, inserts, and deletes are constant time on average. Collisions and resizing are the details that decide how close the real behavior gets to that average.

JavaScript objects and Map are the everyday tools for this pattern. The lesson on Objects is the right starting point.

Trees

A tree is a hierarchy of nodes with a single root. Binary search trees keep smaller values on one side and larger values on the other, which makes an ordered search logarithmic when the tree stays balanced. An unbalanced tree can degrade into a linked list.

Recursion and closures show up constantly in tree code. The lesson on Closures and the Call stack lesson are useful companions.

Graphs

A graph is a set of nodes connected by edges. It can represent a network, a map, a dependency tree, or a social relationship. Breadth first search and depth first search are the two fundamental traversals, and both are linear in the size of the graph.

Graphs are usually stored as an adjacency list: an object or Map where each key is a node and each value is the list of its neighbors.

Where to go next

Read Constant time and Linear time to connect the structures above to the notation. Then move to Sorting Algorithms to see the same tradeoffs in action.

References and further reading