Data Structures

A data structure is a particular way of arranging the addresses and pointers from the previous topic so that specific operations can be done efficiently, and most of the structures in this topic are really just different tradeoffs built from those same two ingredients. 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, though inserting into the middle means physically shifting every element after it over by one. A string is, underneath the name, just an array of characters using the text encoding covered earlier in this series, 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, exactly the pointer mechanism the previous topic just introduced, 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 the way an array allows. A stack restricts access to one end only, last in first out, which is the exact same logical shape as the call stack the previous topic already covered automatically managing every function call; 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, and the filesystem tree covered earlier in this series is already exactly this: each node can point to multiple children, with a binary search tree further keeping every left child smaller and every right child larger than its parent, which turns a search into a series of smaller-or-larger decisions that discards half the remaining tree at every step. A graph, already introduced formally in discrete mathematics 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 a graph models anything with arbitrary many-to-many connections rather than a strict hierarchy. Choosing the right structure for a given problem is the single decision that determines which operations stay fast and which ones become painfully slow, which is exactly the lens the next topic, algorithms, applies directly to the structures introduced here.