Data Structures

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)
- Array, Vector (elements, or pointers to them, stored contiguously)
- Tuple (simple, small array that cannot be resized)
- LinkedList (SingleLinkedList, DoubleLinkedList)
  - UnrolledLinkedList?
  - ConsCell (since the element at any position in the list -- the "car" -- can also be a ConsCell, these can also form BinaryTrees)
  - Stack (aka LIFO: LastInFirstOut)
  - Queue (aka FIFO: FirstInFirstOut)
    - DoubleEndedQueue( Often written as deque and pronounced "deck")
    - PriorityQueue
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)
      - BinaryTree
      - k-ary tree
      - BalancedTree (guarantee that the length of the longest path from root to any leaf is bounded by some function of the length of the shortest such path).
        
        RedBlackTree
        BeeTree and BeeStarTree? (unless you are writing a filesystem driver or RDBMS, you probably won't ever need to use these)
        HeapDataStructure (a way of representing a BalancedTree as an array; this does not refer to the dynamic memory pool called TheHeap)
        LeftistTree (another way of representing a BalancedTree as an array)
      - TernarySearchTree
      - StringTrie (SuffixTrie?)
- DirectedGraph (graph in which the edges are ordered pairs)
  - DirectedAcyclicGraph (directed graph with no cycles)
- 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)
  - WeightedDirectedGraph
  - WeightedDirectedAcyclicGraph
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: