Essential Data Structures for Understanding Algorithms

A data structure is not only a place to store values. It is a decision about which operations should be cheap, which rules must remain true, and how much space we are willing to use.

The same data can live in an array, a Set, a Map, a heap, or a graph. The right choice depends less on the algorithm's name and more on the question the system will repeat: access by position, test membership, extract a priority, or traverse relationships.

Choose a structure for its dominant operation and invariants, not for familiarity.

01. Data structures in 30 seconds

Before comparing costs, separate three concepts:

• Model: describes the problem. A graph represents connected entities.
• Interface or abstract data type: defines how it is used. A stack exposes LIFO discipline; a queue exposes FIFO.
• Representation: decides how it is stored. A graph may use an adjacency list or matrix; a queue may use a circular buffer.

That is why a structure does not have one universal complexity. A queue implemented with shift() does not behave like a queue with explicit head and tail indexes.

This table is a starting point, not a recipe. Data size, memory, ordering, and the frequency of each operation can change the decision.

Visual map connecting the dominant operation with the appropriate data structure

02. One decision, four costs

To evaluate a structure, ask how much access, search, insertion, and deletion cost. These are common references, not promises independent of implementation:

In JavaScript, Map and Set preserve insertion order during iteration, but that does not mean they sort their keys. Their lookup, insertion, and deletion performance commonly approaches O(1); the specification requires average sublinear access rather than a particular hashing strategy.

Memory matters too. An auxiliary index can turn many linear searches into fast lookups, but it duplicates some information and must remain synchronized.

Technical comparison of operation costs for arrays, maps, heaps, and balanced trees

03. Sequences and boundaries

An array works well when order and indexed access matter. Reading items[20] is direct; finding a value requires scanning until it is found. Inserting or deleting in the middle commonly shifts elements.

A stack restricts the sequence to one boundary. In JavaScript, push() and pop() provide a natural implementation:

const history: string[] = [];

history.push("open-project");
history.push("edit-title");

const lastAction = history.pop(); // "edit-title"

This discipline appears in undo, navigation, expression evaluation, and depth-first traversal.

A queue works at two boundaries: it appends at the back and consumes from the front. Using shift() may require reindexing elements. For a long-lived queue, we can keep explicit indexes and remove every consumed value:

class Queue<T> {
  private items = new Map<number, T>();
  private head = 0;
  private tail = 0;

  enqueue(value: T) {
    this.items.set(this.tail, value);
    this.tail += 1;
  }

  dequeue(): T | undefined {
    if (this.head === this.tail) return undefined;

    const value = this.items.get(this.head);
    this.items.delete(this.head);
    this.head += 1;

    if (this.head === this.tail) {
      this.head = 0;
      this.tail = 0;
    }

    return value;
  }

  get size() {
    return this.tail - this.head;
  }
}

In memory- or performance-sensitive systems, a circular buffer over an array avoids both shifting and the additional cost of a Map. The interface remains a queue; its representation changes.

04. Identity and membership

Scanning an array to answer “does this value exist?” many times repeats work. Set expresses membership; Map expresses a relationship between a key and a value.

type User = { id: string; name: string };

function indexUsers(users: User[]) {
  return new Map(users.map((user) => [user.id, user]));
}

const usersById = indexUsers(users); // O(n) once
const user = usersById.get("usr_42"); // expected O(1)

const selectedIds = new Set(["usr_12", "usr_42"]);
const isSelected = selectedIds.has("usr_42"); // expected O(1)

The tradeoff is clear: building the index costs O(n) and uses additional memory. It pays off when the same collection receives many queries. For one lookup over a few elements, the array may be simpler and fast enough.

With objects, Map and Set compare reference identity:

const visited = new Set<object>();
visited.add({ id: 7 });

visited.has({ id: 7 }); // false: this is another object

If two different objects represent the same entity, use a stable key such as id. If an object key should not prevent garbage collection, consider WeakMap or WeakSet, accepting that they are not iterable.

05. Priority, hierarchy, and relationships

When the question is no longer “at which position?” structures with more specific invariants become useful:

Visual comparison of heap, tree, trie, and graph invariants

A heap is not a sorted array. It only guarantees that the minimum or maximum is available at the root; the rest preserves the partial order needed to restore that property. JavaScript has no native heap, so it is commonly implemented or added through a library.

A binary search tree keeps O(log n) operations only if its height stays controlled. Inserting ordered data into a basic tree can turn it into a list and degrade operations to O(n). Balanced structures such as AVL or red-black trees prevent that case.

A trie measures lookups by L, the key length, but can use substantial memory. It is useful when prefix lookup is a product operation, not simply because the keys are strings.

For a graph, the representation depends on density. An adjacency list uses O(V + E) memory and iterates one node's neighbors in O(deg(v)):

class Graph {
  private edges = new Map<string, Set<string>>();

  connect(a: string, b: string) {
    if (!this.edges.has(a)) this.edges.set(a, new Set());
    if (!this.edges.has(b)) this.edges.set(b, new Set());

    this.edges.get(a)!.add(b);
    this.edges.get(b)!.add(a);
  }

  neighbors(node: string) {
    return this.edges.get(node) ?? new Set<string>();
  }
}

For a very dense graph, an adjacency matrix uses O(V²) memory but answers whether two nodes are connected in O(1). BFS and DFS over an adjacency list run in O(V + E) because they visit every node and edge at most a constant number of times.

06. Selection checklist

Before changing structures, answer:

1. What is the dominant operation: access, search, insertion, deletion, priority, range, or traversal?
2. What must remain true: order, uniqueness, FIFO, LIFO, balance, or connectivity?
3. How many times is the structure built, and how many times is it queried?
4. What are the realistic maximum values of n, V, and E?
5. Can you trade memory for less repeated work?
6. Do you need insertion order, key order, or no order?
7. Does your language's implementation support the complexity you expect?

Start with the simplest structure that expresses the problem. Change it when a dominant operation, an invariant, or a real measurement justifies the move. A Map does not automatically improve an array; a heap does not replace a complete sort; a graph does not need a complex class when an adjacency list is enough.

The final question is not “which structure is fastest?” It is “which structure makes the operation my system repeats cheap without hiding a more important cost?”.