List of data structures
This is a list of data structures. For a wider list of terms, see list of terms relating to algorithms and data structures. For a comparison of running time a subset of this list see comparison of data structures.
Data types
Primitive types
- Boolean, true or false.
- Character
- Floating-point numbers, limited precision approximations of real number values.
- Including Single precision and Double precision IEEE 754 Floats, among others
- Fixed-point numbers
- Integer, integral or fixed-precision values.
- Reference (also called a pointer or handle), a small value referring to another object's address in memory, possibly a much larger one.
- Enumerated type, a small set of uniquely named values.
- Date Time, value referring to Date and Time
Composite types or non-primitive type
Abstract data types
- Container
- List
- Tuple
- Multimap (example Associative array)
- Set
- Multiset (bag)
- Stack
- Queue (example Priority queue)
- Double-ended queue
- Graph (example Tree, Heap)
Some properties of abstract data types:
| Structure | Order | Unique |
|---|---|---|
| List | yes | no |
| Associative array | no | yes |
| Set | no | yes |
| Stack | yes | no |
| Multimap | no | no |
| Multiset (bag) | no | no |
| Queue | yes | no |
Order means the insertion sequence counts. Unique means that duplicate elements are not allowed, based on some inbuilt or, alternatively, user-defined rule for comparing elements.
Linear data structures
A data structure is said to be linear if its elements form a sequence.
Arrays
Lists
- Doubly linked list
- Array list
- Linked list
- Association list
- Self-organizing list
- Skip list
- Unrolled linked list
- VList
- Conc-tree list
- Xor linked list
- Zipper
- Doubly connected edge list also known as half-edge
- Difference list
- Free list
Trees
Binary trees
- AA tree
- AVL tree
- Binary search tree
- Binary tree
- Cartesian tree
- Conc-tree list
- Left-child right-sibling binary tree
- Order statistic tree
- Pagoda
- Randomized binary search tree
- Red–black tree
- Rope
- Scapegoat tree
- Self-balancing binary search tree
- Splay tree
- T-tree
- Tango tree
- Threaded binary tree
- Top tree
- Treap
- WAVL tree
- Weight-balanced tree
B-trees
- B-tree
- B+ tree
- B*-tree
- B sharp tree
- Dancing tree
- 2-3 tree
- 2-3-4 tree
- Queap
- Fusion tree
- Bx-tree
- AList
Heaps
Trees
In these data structures each tree node compares a bit slice of key values.
- Tree (data structure)
- Radix tree
- Suffix tree
- Suffix array
- Compressed suffix array
- FM-index
- Generalised suffix tree
- B-tree
- Judy array
- X-fast trie
- Y-fast trie
- Merkle tree
- Ctree
Multiway trees
Space-partitioning trees
These are data structures used for space partitioning or binary space partitioning.
- Segment tree
- Interval tree
- Range tree
- Bin
- K-d tree
- Implicit k-d tree
- Min/max k-d tree
- Relaxed k-d tree
- Adaptive k-d tree
- Quadtree
- Octree
- Linear octree
- Z-order
- UB-tree
- R-tree
- R+ tree
- R* tree
- Hilbert R-tree
- X-tree
- Metric tree
- Cover tree
- M-tree
- VP-tree
- BK-tree
- Bounding interval hierarchy
- Bounding volume hierarchy
- BSP tree
- Rapidly exploring random tree
Application-specific trees
- Abstract syntax tree
- Parse tree
- Decision tree
- Alternating decision tree
- Minimax tree
- Expectiminimax tree
- Finger tree
- Expression tree
- Log-structured merge-tree
- Lexicographic Search Tree
Hash-based structures
Graphs
Many graph-based data structures are used in computer science and related fields:
Other
gollark: Sandboxing is actually pretty hard if you want to make most existing programs work about the same (but sandboxed). But Firewolf doesn't really have that excuse.
gollark: There are probably other holes.
gollark: But the unsafe bits were *removed*, instead of safe bits being *added*, so eventually `openTab` got added and it didn't get updated and so you can now execute stuff out of the sandbox on advanced computers.
gollark: Specifically, for some foolish reason they allowed webpages to access `shell`, without unsafe functions like `run`.
gollark: Sorry, blacklisting instead of whitelisting.
External links
- Tommy Benchmarks Comparison of several data structures.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.