Data Structure
A way of organizing data in memory to support efficient access and modification.
Definition
A data structure is a scheme for organizing and storing data so that specific operations, search, insert, delete, traverse, can be done efficiently. The right choice depends on which operations dominate the workload.
Abstract data types separate what a structure does, its interface, from how it does it, its implementation, so a program can swap a hash table for a balanced tree without changing its logic. This separation is a cornerstone of maintainable software.
The discipline of choosing structures is really about matching the structure's fast operations to the program's frequent operations, and about respecting how memory actually behaves. A theoretically superior structure can lose to a simpler one whose contiguous layout suits the cache and prefetcher. This tension between asymptotic analysis and hardware reality is why experienced engineers measure, rather than assume, which structure performs best for a given workload.
Fundamental types
- Arrays: fast indexed access, fixed layout.
- Linked lists: cheap insertion, sequential access.
- Stacks and queues: ordered access disciplines.
- Trees and hash tables: fast search and mapping.
Why it matters
The choice of data structure often determines an algorithm's efficiency more than the code itself. Matching the structure to the access pattern, ordered versus keyed, static versus dynamic, is a core engineering decision.
Fusion connection
Simulation codes use specialized sparse data structures to store the mostly empty matrices that arise on plasma meshes, saving both memory and time.