116 C Survey KH19

Data structure

A means of storing a collection of data. Computer science is in part the study of methods for effectively using a computer to solve problems, or in other words, determining exactly the problem to be solved. This process entails (1) gaining an understanding of the problem; (2) translating vague descriptions, goals, and contradictory requests, and often unstated desires, into a precisely formulated conceptual solution; and (3) implementing the solution with a computer program. This solution typically consists of two parts: algorithms and data structures.

When a list displays the relationship of adjacency between elements, it is said to be linear; otherwise it is said to be nonlinear.




Linear data structures
General type
Specific types
List (or vector)
Array
Bitmaps
Images
Heightfields
Dynamic array
Parallel array
Sparse array
Matrix
Sparse matrix
Bitboard
Linked list
Unrolled linked list
Xor linked list
Doubly linked list
VList
Line
Stack
Queue
Priority queue
Deque
Circular buffer
Associative array(a.k.a. dictionary or map)
Hash table
Self-balancing binary search tree
Skip list

Non linear data structures
General type
Specific types
Graph data structures
Adjacency list
Adjacency matrix
Disjoint-set data structure
Graph-structured stack
Scene graph
Frame
Database
Tree data structures
M-Way Tree
B-tree
2-3-4 tree
[[B+ tree]]
B*-tree
UB-tree
R-tree
[[R+ tree]]
R* tree
Binary tree
Binary heap
Binary search trees (each tree node compares entire key values)
Self-balancing binary search trees
AVL tree
Red-black tree
AA tree
Scapegoat tree
Splay tree
Top Trees
Interval tree
Treap
Trie family (each tree node compares a bitslice of key values)
Radix tree
van Emde Boas tree
Suffix tree
Directed Acyclic Word Graph (DAWG)
Heap
Binary heap
Binomial heap
Fibonacci heap
2-3 heap
Soft heap
Pairing heap
Leftist heap
Treap
Beap
Skew heap
Parse tree
Space partitioning
BSP tree
Kd-tree
Kdb-tree
Quadtree
Octree