Data structures: choose how information is organized

A visual field guide to the structures behind everyday programs—how they store information, what operations they make convenient, and how to select one that fits a problem.

Why data structures matter

A data structure is a way to organize and store data so a program can use it. A contact list, undo history, browser cache, and road map all organize information differently because they support different operations.

Every structure makes some operations convenient and others costly. An array offers direct access by position; a linked list connects items in sequence; a hash table maps keys to values; a tree represents levels or sorted relationships; a graph models arbitrary connections. Choosing a structure is part of designing the solution.

• Data: what items or records must be represented?
• Operations: which actions are frequent—lookup, insertion, deletion, ordering, or traversal?
• Constraints: how much memory, time, and implementation complexity can you accept?
• Invariants: what must remain true, such as sorted order or parent-child links?

Arrays and dynamic arrays

An array stores elements in indexed positions. In a typical array implementation, elements occupy a contiguous region of memory, so the address of an element can be calculated from its index. This makes reading or replacing an element by index an O(1) operation.

values = [12, 7, 19, 4]
values[2] = 20
// values is now [12, 7, 20, 4]

Finding a value without knowing its index usually requires scanning: in an unsorted array, a linear search takes O(n) time in the worst case. Inserting into the middle also takes O(n), because later items may need to shift.

Fixed-size arrays and dynamic arrays

A fixed-size array has a capacity chosen when it is created. A dynamic array provides a growable sequence by keeping both a length and a capacity. When full, it allocates a larger region and copies the existing elements. Appending is usually amortized O(1), even though a particular resize takes O(n).

Amortized analysis averages the cost across a sequence of operations. It does not mean every append is constant time; it means occasional expensive resizes are spread across many inexpensive appends under the usual growth strategy.

Array operation	Typical cost	Reason
Read or replace by index	O(1)	Address is computed directly
Search an unsorted array	O(n)	May inspect every item
Insert or delete at the front	O(n)	Other elements shift
Append to a dynamic array	Amortized O(1)	Most appends use spare capacity
Resize a dynamic array	O(n) for that operation	Existing values are copied

Arrays are a strong default for ordered data, especially when iteration and indexed access are common. Contiguous storage can also make sequential traversal efficient on real hardware because nearby values are often cached together.

Linked lists

A linked list stores each item in a node that refers to another node. In a singly linked list, each node points forward; in a doubly linked list, it points both forward and backward. The list may also keep a head pointer, a tail pointer, or both.

Node:
    value
    next

head -> [red | next] -> [blue | next] -> [green | null]

To reach the item at position 20, a linked list must follow the links from the beginning, so indexed access is O(n). Inserting or removing an item can be O(1) once the relevant node is known, but finding that node may still take O(n).

When lists help—and when they do not

• Useful when the program frequently inserts or removes near a known node.
• Useful when a collection is naturally traversed one link at a time.
• Less useful for frequent random access or binary search.
• Each node needs link storage, and nodes may be spread across memory.

A common misconception is that linked lists make every insertion faster. The operation must first locate the insertion point; if the program only has an index, that search can dominate the cost. The structure is a good fit when its access pattern matches the task.

Stacks and queues: order operations by access rule

A stack follows last in, first out (LIFO): the most recently added item is removed first. A stack supports push, pop, and often peek. Function calls, undo history, and expression parsing are common examples.

push("open file")
push("edit text")
pop()  // returns "edit text"

A queue follows first in, first out (FIFO): the earliest added item is removed first. A queue supports adding at the back and removing from the front. Print jobs and tasks waiting to be processed fit this pattern.

Abstract structure	Order	Typical operations	Example use
Stack	LIFO	Push, pop, peek	Undo actions; depth-first traversal
Queue	FIFO	Enqueue, dequeue, front	Work scheduling; breadth-first traversal
Deque	Both ends	Add/remove at either end	Sliding windows; flexible work queues
Priority queue	Highest or lowest priority first	Insert, inspect/remove priority	Event simulation; shortest-path algorithms

These are abstract data types: descriptions of allowed operations and their meaning, independent of how those operations are implemented. A queue can be built with a circular array or linked nodes, for example. The contract is FIFO even though the representation differs.

Hash tables and sets

A hash table stores key-value pairs. A hash function converts a key into a number used to choose a storage location. Under well-behaved assumptions, lookup, insertion, and removal are typically O(1) on average. In the worst case, many keys can collide and performance can degrade.

A collision occurs when different keys map to the same location. Implementations resolve collisions with strategies such as chaining (keeping a collection at each slot) or open addressing (searching for another available slot). Table resizing and load factor—the ratio of stored items to available slots—affect performance.

phone_by_name["Mina"] = "555-0142"
phone_by_name["Mina"]  // "555-0142"

visited = {"north", "east"}
"north" in visited  // true

A set stores distinct values and is useful for membership checks and removing duplicates. Hash-based sets and maps often provide fast average lookup, but they do not automatically keep items in sorted order. Some languages provide ordered map variants with different cost and ordering guarantees.

Keys need stable equality and hashing

Keys must be compared consistently. If a key changes in a way that changes its hash after insertion, a table may no longer be able to find it in the expected location. Hash values are not unique identifiers and should not be treated as secure hashes; cryptographic hashing is a different problem with different requirements.

Trees and heaps

A tree models a hierarchy. It has a root, parent-child relationships, and subtrees; a tree with n nodes has n - 1 edges when it is connected and acyclic. File systems, document structures, and expression syntax are often naturally tree-shaped.

Binary search trees

A binary search tree (BST) is a binary tree with an ordering rule: values in the left subtree are less than a node's value, and values in the right subtree are greater, subject to the implementation's duplicate policy. Search, insertion, and removal take O(h), where h is the tree height. A balanced tree keeps h near log n; a highly skewed tree can have height near n.

        8
       / \
      3   12
     / \    \
    1   6    15

An in-order traversal of a BST visits values in sorted order. Self-balancing variants such as AVL trees and red-black trees use rotations to keep height logarithmic while preserving the ordering rule.

Heaps and priority queues

A binary heap is a complete binary tree that obeys a heap-order rule: in a min-heap, each parent is no greater than its children. The root gives the minimum value quickly. Insertion and removal of the root take O(log n); building a heap from an array can be done in O(n).

A heap is not fully sorted: it only guarantees parent-child priority order. Use it when repeatedly selecting the next highest- or lowest-priority item, not when you need arbitrary sorted traversal.

Graphs: represent many-to-many relationships

A graph consists of vertices (also called nodes) and edges that connect them. Edges can be directed, undirected, weighted, or unweighted. This flexible model represents roads, friendships, web links, build dependencies, and communication networks.

Adjacency lists and matrices

An adjacency list stores the neighbors of each vertex and uses O(V + E) space. It is often a good choice for sparse graphs. An adjacency matrix stores whether each pair of vertices is connected and uses O(V²) space; checking for a particular edge is O(1), so it can suit dense graphs or frequent edge queries.

adjacency_list = {
    "A": [("B", 3), ("C", 2)],
    "B": [("A", 3), ("C", 1)],
    "C": [("A", 2), ("B", 1), ("D", 4)],
    "D": [("C", 4)]
}

Graph traversal algorithms answer reachability questions. Breadth-first search uses a queue to explore by distance in edges; depth-first search follows a branch before backtracking, often using recursion or an explicit stack. For weighted shortest paths with nonnegative edge weights, Dijkstra's algorithm is a common option; negative weights require a different method.

Choose and combine structures

Do not choose based on a structure's reputation or a single complexity number. List the operations your program performs, how often it performs them, the size and shape of the data, and any ordering or consistency guarantees it needs.

1. Describe the data and its relationships.
2. List required operations and identify the frequent or expensive ones.
3. Check expected data size, update patterns, and memory limits.
4. Compare candidate structures using their documented guarantees.
5. Choose the clearest option that meets the requirements, then measure if performance matters.

Programs often combine structures. A social network might use a hash table to find a person by ID and an adjacency list to store that person's connections. A task scheduler might use a hash table for task lookup and a heap to choose the next task by priority.

Need	Possible choice	Trade-off to remember
Frequent indexed access	Array or dynamic array	Middle insertion and deletion can shift values
Frequent membership by key	Hash set or hash map	Average-case behavior; keys and order constraints matter
Sorted lookup with updates	Balanced search tree	More complex; keeps keys ordered
Repeated minimum/maximum selection	Heap / priority queue	Only the next priority is readily available
Reachability between entities	Graph with adjacency list or matrix	Choice depends on graph density and query patterns

Correctness, cost, and testing

Each structure has rules that operations must preserve. In an array, valid indexes must refer to existing elements. In a linked list, each link must point to a valid node or the list's end marker. In a BST, values must remain on the correct side of each ancestor. These rules are called invariants.

Test behavior at boundaries

• Test an empty structure and a one-element structure.
• Test inserting a duplicate or missing key according to the contract.
• For lists, test updates at the head and tail as well as in the middle.
• For trees, test sorted input, which can expose an unbalanced implementation.
• For graphs, test disconnected vertices, self-loops, and repeated edges if allowed.

Complexity tables are summaries, not substitutes for understanding the operation. For example, BST search is O(h), not unconditionally O(log n); the height depends on balance. Hash-table lookup is typically average O(1), not a worst-case guarantee for every table and input.

A compact glossary

Abstract data type

A description of operations and behavior independent of implementation.

Invariant

A condition that must remain true for a structure to be valid.

Collision

When two different hash-table keys map to the same location.

Amortized cost

An average per operation across a sequence that may include occasional expensive work.

Traversal

A systematic process for visiting elements or vertices in a structure.

Sparse graph

A graph with relatively few edges compared with the number of possible edges.

Questions for further study

1. Why is reading the middle item of an array easy but finding the middle node of a linked list not?
2. Which structure would you use for browser back and forward history? Explain how its operations match the behavior.
3. What happens to an unbalanced BST when values arrive in sorted order?
4. Compare adjacency-list and adjacency-matrix space for a graph with 1,000 vertices and 2,000 edges.
5. Design a structure combination for a library catalog that supports lookup by ID and listing titles alphabetically.

References and further reading

These texts and courses provide formal analysis, implementation details, and additional examples.

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 4th edition. MIT Press, 2022. Publisher information.
2. Open Data Structures. Pat Morin, author. Open Data Structures: An Introduction. Free book and source.
3. Paul E. Black, ed. Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. Reference index.
4. Princeton University. Algorithms, Part I, online course materials. Course page.

Try it yourself

1. For a playlist, list the operations you expect and choose a structure that makes the most common actions convenient.
2. Trace a stack as you push A, B, then pop twice. What order comes out?
3. Draw a graph of five places and roads between them. Write its adjacency list and adjacency matrix.
4. Give an example where a hash table is not the best choice because the output must be sorted.
5. State the invariant for a queue and describe a test that would catch a violation.

Remember: choose a structure to support the operations your program actually needs, then check its costs and invariants.