How data is organized, represented in programs. The difference of
DataStructures used in programs may be significant in run-time performance, memory usage. These patterns are useful in their own right, but in modern systems they are usually implemented by vendor-supplied libraries and runtimes.
CeePlusPlus programmers should usually use the container classes of the
StandardTemplateLibrary, for example. A reasonable theoretical understanding is still required to understand the applications and trade-offs of each data structure, even though you're unlikely to implement one yourself in production code.
Includes (in order from simple to complex)
- Trivial
- Cell (stores exactly one element)
- EmptyCell? (stores exactly zero elements)
- Sequential (Indexed according to some sequential type, such as an int or enum; insertion/deletion in the middle causes subsequent elements to have a new index)
- Reflexive (contain elements, but elements don't have any indices associated with them)
- Set (cannot contain multiple elements that are equal/identical)
- MultiSet or Bag (can contain multiple such elements)
- Associative (maintain key/value pairs; designed for efficient search/retrieval based on keys)
- Map
- DictionaryDataStructure (has only one value per key)
- Record, Struct (optimized associative structure with fixed set of keys and often with type constraints). These aren't often considered data structures by people, as in many languages they have different syntax to access (foo.bar vs foo["bar"] in C++), but they are.
- AssociationList (how to turn a linked list into a dictionary)
- MultiMap? (can have multiple value per key)
- HashTable (common and efficient implementation of associative data structures if you do not care about ordered-traversal; otherwise a BalancedTree is typically used UnderTheHood? instead; usually has only one value per key)
- JudyArray
- Graph (a set of vertices and a set of pairs of vertices called edges)
- UndirectedGraph
- Tree (graph in which two vertices are connected by exactly one path)
- UnrootedTree?
- RootedTree? (tree with a special vertex called the root)
- DirectedGraph (graph in which the edges are ordered pairs)
- WeightedGraph? (graph in which each edge has a "weight")
- (unfortunately, this very page is organized as a RootedTree?, so we cannot do these items justice since they can only have one parent each)
- SkipList
- Relational tables? (RelationalDatabase, MinimalTable)
- Multi-dimensional
- Matrices (both 2-dimensional mathematical variety, and higher-rank matrices)
- SparseMatrices?
and many more.
DataStructures are often combined and used with algorithms. For more information and definitions:
http://www.nist.gov/dads/
DataStructures can utilize the following mechanisms:
See also
CategoryAlgorithm,
CategoryDataStructure,
CollectionHierarchies.