Data Structures

Data Structures

In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.

Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks. For example, B-trees are particularly well-suited for implementation of databases, while compiler implementations usually use hash tables to look up identifiers.

Data structures provide a means to manage large amounts of data efficiently, such as large databases and internet indexing services. Usually, efficient data structures are a key to designing efficient algorithms. Some formal design methods and programming languages emphasize data structures, rather than algorithms, as the key organizing factor in software design. Storing and retrieving can be carried out on data stored in both main memory and in secondary memory.

Topics covered:

• Linked data structure
• Succinct data structure
• Implicit data structure
• Compressed data structure
• Search data structure
• Persistent data structure
• Concurrent data structure
• Abstract data types
• List (abstract data type)
• Stack (abstract data type)
• Queue (abstract data type)
• Double-ended queue
• Priority queue
• Associative array
• Bidirectional map
• Multimap
• Set (abstract data type)
• Tree (data structure)
• Array data structure
• Row-major order
• Dope vector
• Iliffe vector
• Dynamic array
• Hashed array tree
• Gap buffer
• Circular buffer
• Sparse array
• Bit array
• Bitboard
• Parallel array
• Lookup table
• Lists
• Linked list
• XOR linked list
• Unrolled linked list
• VList
• Skip list
• Self-organizing list
• Binary tree
• Binary search tree
• Self-balancing binary search tree
• Tree rotation
• Weight-balanced tree
• Threaded binary tree
• AVL tree
• Red-black tree
• AA tree
• Scapegoat tree
• Splay tree
• T-tree
• Rope (computer science)
• Top Tree
• Tango tree
• Van Emde Boas tree
• Cartesian tree
• Treap
• B-trees
• B+ tree
• Dancing tree
• 2-3 tree
• 2-3-4 tree
• Queaps
• Fusion tree
• Bx-tree
• Heaps
• Heap (data structure)
• Binary heap
• Binomial heap
• Fibonacci heap
• 2-3 heap
• Pairing heap
• Beap
• Leftist tree
• Skew heap
• Soft heap
• D-ary heap
• Tries
• Trie
• Radix tree
• Suffix tree
• Suffix array
• Compressed suffix array
• FM-index
• Generalized suffix tree
• B-trie
• Judy array
• Directed acyclic word graph
• Multiway trees
• Ternary search tree
• And–or tree
• (a,b)-tree
• Link/cut tree
• SPQR tree
• Spaghetti stack
• Disjoint-set data structure
• Space-partitioning trees
• Space partitioning
• Binary space partitioning
• Segment tree
• Interval tree
• Range tree
• Bin (computational geometry)
• K-d tree
• Implicit k-d tree
• Min/max kd-tree
• Adaptive k-d tree
• Quadtree
• Octree
• Linear octrees
• Z-order curve
• UB-tree
• R-tree
• R+ tree
• R* tree
• Hilbert R-tree
• X-tree
• Metric tree
• Vp-tree
• BK-tree
• Hashes
• Hash table
• Hash function
• Open addressing
• Lazy deletion
• Linear probing
• Quadratic probing
• Double hashing
• Cuckoo hashing
• Coalesced hashing
• Perfect hash function
• Universal hashing
• Linear hashing
• Extendible hashing
• 2-choice hashing
• Pearson hashing
• Fowler–Noll–Vo hash function
• Bitstate hashing
• Bloom filter
• Locality preserving hashing
• Zobrist hashing
• Rolling hash
• Hash list
• Hash tree
• Prefix hash tree
• Hash trie
• Hash array mapped trie
• Distributed hash table
• Consistent hashing
• Stable hashing
• Koorde
• Graphs
• Adjacency list
• Adjacency matrix
• And-inverter graph
• Binary decision diagram
• Binary moment diagram
• Zero-suppressed decision diagram
• Propositional directed acyclic graph
• Graph-structured stack
• Scene graph
• Big O notation
• Amortized analysis
• Locality of reference
• Standard Template Library

You can download this EBook for FREE from Google Play Store at