Definition
A data structure is a principled way of organizing information in memory so that specific operations — searching, inserting, deleting, traversing — can be performed efficiently. The choice of structure is inseparable from the choice of algorithm: the two co-determine how fast and how clearly a program does its job.
Every data structure makes a trade-off. An array offers instant access by index but slow insertion in the middle. A linked list makes insertion cheap but random access expensive. A hash table turns lookups into near-constant time at the cost of predictable ordering. A tree encodes hierarchy and makes range queries natural. Understanding these trade-offs is what separates programs that work from programs that scale.
At a deeper level, data structures are a form of applied abstraction — the programmer decides which operations must be fast, which relationships among elements matter, and then selects or designs a container whose internal organization reflects those priorities. A well-chosen structure can reduce a problem that seemed intractable to something straightforward; a poorly chosen one can make even a simple operation painfully slow.
Why it matters
How it works
Linear structures — sequences and stacks
The simplest data structures organize elements in a single sequence. An array stores elements at contiguous memory addresses, making index-based access instantaneous but insertion into the middle slow because elements must shift. A linked list stores each element in a node that also holds a pointer to the next node; insertion anywhere is cheap once you hold the preceding pointer, but finding any element requires walking the chain from the start.
Stacks and queues are restricted sequences that enforce a specific access discipline. A stack (last-in, first-out) models call stacks in programming languages and undo histories in editors. A queue (first-in, first-out) models task scheduling and message passing. Both can be implemented on top of arrays or linked lists; the choice of discipline is what gives them semantic power.
Non-linear structures — trees, graphs, and hash tables
Trees organize elements hierarchically. A binary search tree keeps a sorted ordering that makes lookup, insertion, and deletion all logarithmic in the number of elements. Self-balancing trees (AVL trees, red-black trees) maintain that logarithmic guarantee by rebalancing after mutations. Heaps are tree-shaped structures optimized for always knowing the minimum or maximum element quickly, making them the foundation of priority queues.
Graphs generalize trees by allowing arbitrary connections between nodes, not just parent-child relationships. They model road networks, social connections, dependency graphs, and state machines. A hash table maps keys to values through a hash function that computes an array index from the key. Well-designed hash tables deliver average constant-time lookup — the single most economically valuable performance property in everyday programming.