Understanding data structures is integral to participate in competitive programming, as you will be faced with making decisions on what data structure to utilize to most efficiently solve the problem you are given.
It’s important to learn basic data structures inside out, otherwise understanding higher level structures will be difficult.
Beginner
- Array: A collection of items of the same variable type that are stored sequentially in memory. It’s one of the most popular and simple data structures and often used to implement other data structures.
- Linked List: A linear sequence of nodes that are linked together. Each node contains a value and a pointer to the next node in the list.
- Stack: A linear data structure that follows the principle of Last In First Out (LIFO).
- Queue: Similar to Stack in that they both are linear data structures with dynamic size. However, queues are FIFO (first-in, first-out) data structures.
- Deque (Double Ended Queue): An extension of Queue, elements can be added to or removed from either the front (head) or back (tail).
- Priority Queue: An extension of queue, each element is associated with a priority value, element with high priority is served before an element with low priority.
- Set: An abstract data type that can store unique values, without any particular order.
- Hash Table: A data structure that can map keys to values, uses a hash function to compute an index into an array of buckets from which the desired value can be found.
Intermediate
- Heap: A specialized tree-based data structure that has largest root node in Max-Heap or smallest root node in Min-Heap.
- Huffman Tree (Huffman Coding Tree): A full binary tree in which each leaf of the tree corresponds to a letter in the given alphabet. The goal is to construct a tree with the minimum external path weight.
- Disjoint Set (Union Find): A data structure that stores a collection of disjoint sets, supports union and find operation on subsets.
- Trie: A tree data structure used for locating specific keys from within a set. These keys are most often strings, with links between nodes defined not by the entire key, but by individual characters.
- Binary Search Tree: A rooted binary tree data structure whose internal nodes each store a key greater than all the keys in the node’s left subtree and less than those in its right subtree.
Proficient
- Segment Tree: A data structure that allows answering range queries over an array effectively, while still being flexible enough to allow modifying the array.
- Fenwick Tree (Binary Indexed Tree): A data structure that can efficiently update elements and calculate prefix sums in a table of numbers.
- Suffix Array: A sorted array of all suffixes of a string, used in full text indices, data compression algorithms, and the field of bibliometrics.
- Sparse Table: A data structure that allows answering range queries, especialy range minimum queries in an array.
- Range Tree: An ordered tree data structure to hold a list of points. It permits all points within a given range to be efficiently retrieved, and is typically implemented in two or higher dimensions.
Expert
- AVL Tree: A self-balancing binary search tree in which each node maintains extra information called a balance factor whose value is either -1, 0 or +1.
- Suffix Automaton: A powerful data structure that allows solving many string-related problems like searching for all occurrences of one string in another or counting the amount of different substrings of a given string.
- Suffix Tree: A compressed trie containing all the suffixes of the given text as their keys and positions in the text as their values.
- Treap (Cartesian Tree): A data structure which combines binary tree and binary heap (hence the name: Tree + Heap = Treap).
- K-d Tree: A space-partitioning data structure for organizing points in a k-dimensional space.
- Forest: An undirected graph in which any two vertices are connected by at most one path. Equivalently, a forest is an undirected acyclic graph, all of whose connected components are trees; in other words, the graph consists of a disjoint union of trees.
- Splay Tree: An efficient implementation of a balanced binary search tree that takes advantage of locality in the keys used in incoming lookup requests.
- Palindromic Tree: A tree based data structure that is specifically used to tackle problems involving palindromes of a string and its substrings.
- Rope: A data structure composed of smaller strings that is used to efficiently store and manipulate a very long string.
- Radix Tree: A data structure that represents a space-optimized trie (prefix tree) in which each node that is the only child is merged with its parent.
- Red Black Tree: A self-balancing binary search tree. Each node stores an extra bit representing “color”, used to ensure that the tree remains balanced during insertions and deletions.