Data Structures

Why data structures matter

A data structure is a way of organizing data in memory together with the operations it supports: adding an item, removing one, finding one, visiting all of them in order. The same thousand customer records can be kept in a plain list, a table indexed by customer number, or a tree sorted by name. All three hold the same data; they differ in which questions they answer quickly.

That difference is the point. Finding one name among a million in an unsorted list means checking names one by one; in a hash table it takes a single lookup. Choosing the structure that fits the operations your program does most is often the biggest performance decision you make — bigger than any clever trick inside a loop.

This page describes costs with the shorthand of Big O notation: O(1) means the cost stays the same however much data there is, O(log n) means it grows very slowly, and O(n) means it grows in proportion to the number of items n.

Arrays

An array is a fixed number of items of the same type, stored next to each other in one contiguous block of memory. Each item is identified by its index, its position counted from 0. Because every item has the same size, the computer finds item i with simple arithmetic — start address + i × item size — so reading or writing any item takes the same short time, O(1), however long the array is.

In C, an array's size is fixed when it is created and it can never grow. The program must track the size itself; C does not check indexes, so reading past the end silently reads whatever memory happens to be there.

#include <stdio.h>

int main(void) {
    int temperatures[5] = {18, 21, 19, 23, 20};   /* exactly 5 ints, side by side */
    int count = sizeof temperatures / sizeof temperatures[0];
    int sum = 0;

    for (int i = 0; i < count; i++) {
        sum += temperatures[i];
    }
    printf("%d readings, average %.1f\n", count, sum / (double)count);
    printf("First %d, last %d\n", temperatures[0], temperatures[count - 1]);
    return 0;
}

5 readings, average 20.2
First 18, last 20

Dynamic arrays and vectors

Most programs do not know in advance how many items they will hold. A dynamic array solves this: it is an array that grows by itself. It reserves some spare room, and when that runs out it allocates a larger block and copies the items over. C++ calls this a std::vector, Java an ArrayList; Python's list and JavaScript's Array work the same way (and, unlike a C array, can hold values of different types).

const readings = [18, 21, 19];
readings.push(23);            // add at the end: cheap
console.log(readings.length, readings[3]);

readings.splice(1, 0, 20);    // insert at index 1: later items shift up
console.log(readings);

4 23
[ 18, 20, 21, 19, 23 ]

Adding at the end is fast. Inserting or removing near the front is not: every later item has to move one place to keep the block contiguous, so the cost is O(n). For Python's version, see Lists and Tuples.

Linked lists

A linked list stores each item in a separate node: a small piece of memory holding the value and a pointer (a reference) to the next node. The nodes can be anywhere in memory; the pointers chain them together. The program only keeps a reference to the first node, the head. The last node points to nothing.

Python has no built-in linked list, but a node class of a few lines is enough to build one:

class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node          # the next node, or None at the end


def show(head):
    values = []
    node = head
    while node is not None:            # follow the pointers to the end
        values.append(node.value)
        node = node.next
    print(" -> ".join(values))


head = Node("wash", Node("dry", Node("fold")))
show(head)

# Insert "iron" after "dry": create one node, change one pointer.
dry = head.next
dry.next = Node("iron", dry.next)
show(head)

# Insert "sort" at the front: the new node becomes the head.
head = Node("sort", head)
show(head)

wash -> dry -> fold
wash -> dry -> iron -> fold
sort -> wash -> dry -> iron -> fold

This shows the trade-off with arrays. Inserting a node, once you are at the right place, takes O(1): nothing else moves. But there is no arithmetic shortcut to "item number 500" — you have to follow 500 pointers from the head, O(n). Each node also costs extra memory for its pointer. A doubly linked list adds a pointer back to the previous node, so it can be walked in both directions.

Stacks

A stack is a collection where you can only add or remove items at one end, the top, like a pile of plates. The last item added is the first one removed: LIFO, last in, first out. The two operations are push (put an item on top) and pop (take the top item off); many stacks also offer peek, which reads the top item without removing it. All of them are O(1).

Stacks appear wherever the most recent thing must be handled first:

• The undo history of an editor: every change is pushed; Undo pops the most recent one.
• The call stack that keeps track of function calls that have not returned yet.
• The browser's Back button, and checking whether brackets in code are balanced.

In Python, a list is a good stack: append() pushes and pop() pops, both at the end of the list. This bracket checker pushes every opening bracket and pops one for every closing bracket, which must match:

PAIRS = {")": "(", "]": "[", "}": "{"}


def balanced(text):
    stack = []
    for char in text:
        if char in "([{":
            stack.append(char)                    # push
        elif char in PAIRS:
            if not stack or stack.pop() != PAIRS[char]:   # pop and compare
                return False
    return not stack                              # nothing may be left open


for text in ["(a[1] + b) * {c}", "(a[1)]", "((x)"]:
    print(f"{text:18} {balanced(text)}")

(a[1] + b) * {c}   True
(a[1)]             False
((x)               False

Queues

A queue is the opposite: items join at the back and leave from the front, like people waiting at a counter. The first item added is the first removed: FIFO, first in, first out. The operations are called enqueue and dequeue. Queues keep things fair and in order: jobs waiting for a printer, requests waiting for a web server, messages between programs, and the places still to visit in a breadth-first search of a graph.

A Python list is a poor queue, because removing its first item with pop(0) shifts every other item: O(n). The standard library's collections.deque (a "double-ended queue") adds and removes at both ends in O(1):

from collections import deque

print_queue = deque()
print_queue.append("invoice.pdf")      # enqueue at the back
print_queue.append("photo.jpg")
print_queue.append("letter.docx")

while print_queue:
    job = print_queue.popleft()        # dequeue from the front
    print("Printing", job)

Printing invoice.pdf
Printing photo.jpg
Printing letter.docx

Hash tables

A hash table stores key–value pairs so that a value can be found from its key almost instantly. It is an array of buckets plus a hash function: a function that turns a key into a number. That number, taken modulo the number of buckets, says which bucket the pair goes in. To look a key up later, the table hashes it again and goes straight to that one bucket, instead of searching everything.

Here is a deliberately simple hash function — the sum of the character codes — with eight buckets:

def simple_hash(key):
    return sum(ord(char) for char in key)    # add up the character codes


BUCKETS = 8
buckets = [[] for _ in range(BUCKETS)]

for name in ["Ada", "Grace", "Linus", "Tim"]:
    index = simple_hash(name) % BUCKETS
    buckets[index].append(name)
    print(f"{name:6} hash {simple_hash(name)}  bucket {index}")

print(buckets)

Ada    hash 262  bucket 6
Grace  hash 482  bucket 2
Linus  hash 523  bucket 3
Tim    hash 298  bucket 2
[[], [], ['Grace', 'Tim'], ['Linus'], [], [], ['Ada'], []]

"Grace" and "Tim" land in the same bucket. That is a collision, and it is unavoidable: there are far more possible keys than buckets. A real hash table handles it — for example by keeping a short list per bucket, as above, or by trying the next free slot — and it uses a much better hash function that spreads keys evenly. It also grows its array when it gets too full, so buckets stay short. Together, this makes lookup, insertion and deletion O(1) on average; in the rare worst case, when many keys collide, it degrades to O(n).

Python's dict and set are hash tables, which is why keys and set members must be hashable and why x in my_set is so much faster than x in my_list. See Dictionaries and Sets for the details. JavaScript's Map and Set work the same way.

Trees

A tree is a hierarchy of nodes. One node at the top is the root. Every other node has exactly one parent above it and can have any number of children below it; a node without children is a leaf. There are no cycles: from the root there is exactly one path to each node. Folder structures, the HTML elements of a web page and an organization chart are all trees.

In a binary tree, every node has at most two children, called left and right. A binary search tree (BST) adds one rule: everything in a node's left subtree is smaller than the node, and everything in its right subtree is larger (or equal). That rule lets a search skip half of the remaining tree at every step, like looking up a word in a dictionary.

Trees are naturally recursive: each child is itself the root of a smaller tree. Both inserting and visiting are therefore short recursive functions. An in-order traversal — left subtree, then the node, then the right subtree — visits the keys of a BST in sorted order.

class TreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None


def insert(node, key):
    if node is None:                   # empty spot found: the new node goes here
        return TreeNode(key)
    if key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)
    return node


def in_order(node, keys):
    if node is not None:
        in_order(node.left, keys)      # everything smaller first
        keys.append(node.key)
        in_order(node.right, keys)     # then everything larger
    return keys


root = None
for key in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, key)

print(root.key, root.left.key, root.right.key)
print(in_order(root, []))

50 30 70
[20, 30, 40, 50, 60, 70, 80]

A search, insertion or deletion in a BST follows one path from the root, so it costs as many steps as the tree is tall. A balanced tree of a million keys is only about 20 levels tall, giving O(log n). But inserting keys that are already sorted (10, 20, 30, …) into this simple BST produces one long chain, and the cost falls back to O(n). Real libraries use self-balancing trees, such as red-black trees, that reorganize themselves to stay short.

Graphs

A graph is the most general structure: a set of vertices (also called nodes) connected by edges. Unlike a tree, a graph has no root and may contain cycles. Graphs model anything that is a network: computers and cables, cities and roads, people and friendships, web pages and links.

• In an undirected graph, an edge works both ways (a road with two-way traffic). In a directed graph, each edge has a direction (a web link, a one-way street).
• In a weighted graph, each edge carries a number such as a distance, a cost or a bandwidth. Route planners and network routing protocols look for the path with the lowest total weight.

A common way to store a graph is an adjacency list: for every vertex, the list of its neighbors. In Python that is a dictionary of lists. Combined with a queue, it gives a breadth-first search, which visits vertices in order of their distance from the start and so finds the fewest hops to each:

from collections import deque

# Undirected graph: each city lists its direct train connections (simplified).
rail = {
    "Amsterdam": ["Haarlem", "Utrecht"],
    "Haarlem": ["Amsterdam", "Leiden"],
    "Leiden": ["Haarlem", "The Hague"],
    "The Hague": ["Leiden", "Rotterdam"],
    "Utrecht": ["Amsterdam", "Rotterdam"],
    "Rotterdam": ["The Hague", "Utrecht"],
}


def hops_from(start):
    hops = {start: 0}
    queue = deque([start])
    while queue:
        city = queue.popleft()
        for neighbor in rail[city]:
            if neighbor not in hops:              # not seen yet
                hops[neighbor] = hops[city] + 1
                queue.append(neighbor)
    return hops


for city, count in hops_from("Amsterdam").items():
    print(f"{city}: {count}")

Amsterdam: 0
Haarlem: 1
Utrecht: 1
Leiden: 2
Rotterdam: 2
The Hague: 3

The hops dictionary also stops the search from going round in circles: a graph can lead back to a vertex already seen, which a tree never does. A graph can also be stored as an adjacency matrix, a grid with a cell for every pair of vertices; that is simpler for dense graphs but wastes memory when most pairs are not connected.

Choosing a structure

Start from the operations your program performs most often, then pick the structure that makes those cheap. The table gives the usual costs; "—" means the structure does not offer that operation directly.

* For a doubly linked list that keeps a pointer to its last node. "Amortized" means: occasionally slow (when the array has to grow), but constant on average over many operations — see Algorithmic Complexity.

Some rules of thumb:

• A sequence you mostly append to and read by position → a dynamic array (Python list).
• Look things up by name, ID or other key, or test membership → a hash table (dict, set).
• Handle the newest item first → a stack; handle items in arrival order → a queue (deque).
• Keep data sorted while it changes, or find ranges ("all orders between two dates") → a balanced tree.
• Model connections between things → a graph.