Data structures

In the design of many types of programs, the choice of data structures is a primary design consideration, as experience in building large systems has shown that the difficulty of implementation and the quality of the final result depends heavily on choosing the best data structure. After the data structures are chosen, then the algorithms to be used often become relatively obvious. Sometimes things work in the opposite direction - data structures are chosen because certain key tasks have algorithms that work best with particular data structures, but in either case the choice of appropriate data structures is crucial.

This insight has given rise to many formalised design methods and programming languages in which data structures, rather than algorithms, are the key organising factor. Object-oriented programming languages such as C++ and Java are one group of languages that exhibit this philosophy.

The fundamental building blocks of most data structures are arrays, records, and references.

Some examples of data structures are:

• Linear data structures
  • List
    • Array
      • Bitmaps
        • Images
        • Heightfields
    • Linked list
      • Skip list
  • Hash table
  • Stack (a.k.a LIFO Last in, first out)
  • Queue (a.k.a FIFO First in, first out)
    • Priority queue
  • Deque
  • Buffer gap
• Graph data structures
  • Adjacency list
  • Scene graph
  • Tree data structures
    • B-tree
    • Binary search trees
      • Self-balancing binary search trees
        • AVL tree
        • Red-black tree
        • Splay tree
    • Heap
      • Binary heap
      • Binomial heap
      • Fibonacci heap
      • Soft heap
    • Parse tree
    • Suffix tree
    • Trie
      • Patricia trie
• Abstract data structures
  • Associative array
• Other data structures
  • Tagged union

See also: computer science, algorithm

External link

• Fundamental Algorithm