Data Structures Overview

A data structure is simply a particular way of arranging the addresses from the previous topic so that a specific set of operations — adding an item, finding one, removing one — can be done efficiently, and choosing the wrong one for the job is one of the most common root causes of a slow program. An array is the simplest structure: a single contiguous block of memory holding same-sized elements back to back, so any element can be reached instantly by computing its address directly from its index (`base_address + index * element_size`), but inserting into the middle means physically shifting every element after it. A string is, underneath the name, just an array of characters, which is why string operations inherit an array's exact same tradeoffs. A linked list trades that instant indexing away for cheap insertion: each node holds a value plus a pointer to the next node, so inserting a new node anywhere just means rewriting two pointers, but finding the 500th element means walking all 500 pointer hops one at a time, since there's no way to compute a middle node's address directly. A stack restricts access to one end only — last in, first out — and is the exact same logical shape as the call stack this series' memory-and-execution topic already introduced; a queue restricts access the other way — first in, first out — modeling a real waiting line, used anywhere work needs to be processed in the order it arrived. A hash table solves the linked list's slow-search problem by running each key through a hash function that converts it into an array index, giving average-case instant lookup, insertion, and deletion all at once — the catch is that two different keys can hash to the same index (a collision), which every real hash table implementation has to handle explicitly, usually by chaining a small linked list at each occupied slot. A tree generalizes the linked list from one chain into a branching hierarchy — each node can point to multiple children — and a binary search tree keeps every left child smaller and every right child larger than its parent, which turns a search into a series of smaller/larger decisions that discards half the remaining tree at every step. A graph, already introduced in this series' discrete-mathematics topic as nodes and edges, is the most general structure of all — a tree is simply a graph with no cycles and exactly one path between any two nodes — and graphs model anything with arbitrary many-to-many connections: a city's road network, a social network's friendships, or the dependency graph a build system walks to compile a project in the right order. A contact manager (array or hash table of names to phone numbers), a task organizer (queue or priority structure for pending work), and a word-frequency counter (hash table mapping each distinct word to its running count) are the three structures this entire topic trains a programmer to reach for first.

Every algorithm this series covers next operates on one of these shapes specifically — sorting rearranges an array in place, searching exploits an array's index or a tree's ordering, and graph traversal walks the nodes-and-edges structure this topic just finished generalizing from a tree — so the structure chosen here directly determines which algorithms are even available to use on the data afterward.