Data Structures
lastmod 2025-12-02created 2014-01-119 edits
|
In computer science, a data structure is a way of storing data in a computer so that it can be used efficiently. A carefully chosen data structure allows a more efficient algorithm to be used. The problem of choosing a data structure often begins with the choice of an abstract data structure. A well-designed data structure allows operations to be performed while using as few resources, such as execution time or memory capacity, as possible.
There are many kinds of data structures, and each is tailored to its own operations and purposes. For example, B-trees are efficient for databases, and routing tables are common in networks (the internet, intranets).
When designing various programs, the choice of data structure should be considered first. This is because much experience shows that, when building large systems, the difficulty of implementation and the performance of the final product depend heavily on the data structures. Once a data structure is chosen, the algorithm to apply usually becomes relatively clear. Sometimes the order is reversed, such as when the target operation necessarily requires a specific algorithm, and that algorithm performs best with a specific data structure. In either case, choosing an appropriate data structure is essential.
This view has spurred the development of many formalized development methodologies and programming languages in which data structures, rather than algorithms, are treated as the more important factor. Most languages have some level of module concept, which allows data structures to be used in various programs through their interfaces alone while hiding their verified implementations. Object-oriented programming languages such as C/C++ and Java use objects specifically for this purpose.
Because of this importance of data structures, recent programming languages and development environments provide various standard libraries. Examples include the C++ Standard Template Library, the Java API for Java, and Microsoft .NET.
The most basic units of data structures are arrays, records, unions, and references. For example, a nullable reference can be represented as a combination of a reference and a union, and a linked list, one of the simplest data structures, can be represented with records and nullable references.
Categories
- Algorithms
- Succinct data structures - succinct data structures
- Conflict-free Replicated Data Type (CRDT; Korean: 충돌 없는 복제 데이터 타입)
Table
| Types | Collection, Container |
| Abstract | List, Associative array, Multimap, Set, Multiset, Queue, Double-ended queue, Priority queue, Double-ended priority queue, Stack |
| Arrays | Dynamic array, Hashed array tree, Sparse array, Circular buffer, Bit array, Hash table |
| Linked | Linked list, Unrolled linked list, XOR linked list, Skip list, Association list |
| Trees | B-trees, Binary search tree (self-balancing, AA, AVL, red-black, splay), Heap (binary, binomial, Fibonacci), Trie |
| Graphs | Directed graph, Directed acyclic graph, Directed acyclic word graph, Binary decision diagram, Hypergraph |
See also
Favorite site
- Wikipedia (en) Data structure
- [Recommended] List of data structures