Fundamental Data Structures
Fundamental data structures are the organized ways of storing and accessing data — arrays, linked lists, hash tables, trees, heaps and their relatives — that determine the efficiency of the operations built on top of them.
Definition
A data structure is a way of organizing and storing data so that the operations defined by its abstract data type can be performed efficiently; fundamental data structures are the small set of general-purpose structures from which most others are built.
Scope
This area covers the abstract data types (lists, dictionaries, priority queues, sets) and the concrete structures that implement them, together with the cost of their core operations (insert, delete, search, update) under worst-case and amortized analysis. It treats how the choice of structure shapes algorithm performance and connects to the design paradigms and graph and string algorithms that depend on these structures. It excludes the database and file-system storage structures handled in other subfields.
Sub-topics
Core questions
- Which abstract data type does an application need, and which concrete structure implements it best?
- What are the worst-case and amortized costs of each operation on a given structure?
- How do structures trade memory for time, or read speed for update speed?
- How does maintaining an invariant (sortedness, balance, the heap property) bound operation costs?
- When is a simple structure preferable to an asymptotically faster but more complex one?
Key concepts
- abstract data type
- arrays and linked lists
- stacks and queues
- hash tables
- binary search trees
- balanced trees
- heaps and priority queues
- amortized analysis
- time-space trade-offs
Key theories
- Abstract data types versus implementations
- An abstract data type specifies operations and their semantics independent of representation; multiple concrete data structures can implement the same ADT with different performance profiles, letting designers reason about correctness and cost separately.
- Amortized analysis
- Some structures (dynamic arrays, splay trees) have occasional expensive operations but cheap operations on average over a sequence; amortized analysis (aggregate, accounting, potential methods) bounds this average cost rigorously.
Clinical relevance
Fundamental data structures are the building blocks of essentially all software: hash tables back dictionaries and database indexes, balanced trees and B-trees organize file systems and databases, priority queues drive schedulers and event simulations, and the right structure choice often determines whether a system scales.
History
Foundational data structures were catalogued in Knuth's The Art of Computer Programming beginning in 1968. Self-balancing trees (AVL trees, 1962; red-black trees and B-trees in the 1970s) and advanced structures such as Fibonacci heaps and splay trees (1980s, largely due to Tarjan and collaborators) extended the field, while amortized analysis gave a rigorous account of their performance.
Key figures
- Donald Knuth
- Robert Sedgewick
- Robert Tarjan
- Rudolf Bayer
Related topics
Seminal works
- knuth1997vol1
- cormen2009
- sedgewick2011
Frequently asked questions
- How do I choose between a hash table and a balanced search tree?
- Hash tables give expected O(1) lookup and insertion but no order, while balanced search trees give O(log n) operations and keep keys sorted, supporting range queries and ordered traversal. Choose hashing for pure key lookups and a tree when ordering or range operations matter.
- What does amortized cost mean for a data structure?
- Amortized cost is the average cost per operation over a worst-case sequence of operations. A dynamic array, for instance, occasionally pays O(n) to resize but averages O(1) per append because resizes are rare relative to cheap appends.