Data Structures
Reference notes for common and advanced data structures, complexity tradeoffs, implementation patterns, and practical selection guidance.
- 21
- 43 min
- 89
- 0
Ordered notes
Arrays
An Array is the most fundamental data structure, storing elements in contiguous memory locations. Each element can be accessed directly using an index, providing O(1) random access. Arrays form the building block for...
AVL Trees
An AVL Tree is a self balancing Binary Search Tree where the height difference between left and right subtrees of any node (called the balance factor) is at most 1. Named after inventors Adelson Velsky and Landis...
B-Trees
A B Tree is a self balancing tree data structure designed for systems that read and write large blocks of data, such as databases and file systems. Unlike binary trees, B Trees can have many children per node, making...
Binary Search Trees
A Binary Search Tree (BST) is a binary tree with an ordering property: for each node, all values in its left subtree are smaller, and all values in its right subtree are larger. This property enables efficient O(log n)...
Binary Trees
A Binary Tree is a hierarchical data structure in which each node has at most two children, referred to as the left child and right child. Binary trees form the foundation for many important data structures like BSTs,...
Bloom Filters
A Bloom Filter is a space efficient probabilistic data structure used to test whether an element is a member of a set. It can have false positives (saying an element is present when it's not) but never false negatives...
Data Structures
Data Structures A data structure is a specialized format for organizing, processing, retrieving, and storing data. Choosing the right data structure is crucial for writing efficient algorithms and building performant...
Disjoint Set (Union-Find)
A Disjoint Set (also called Union Find) is a data structure that tracks a collection of non overlapping sets. It provides near constant time operations to determine if two elements are in the same set (Find) and to...
Fenwick Trees
A Fenwick Tree (also called Binary Indexed Tree or BIT) is a data structure that efficiently supports prefix sum queries and point updates on an array. It achieves O(log n) for both operations using a clever bit...
Graphs
A Graph is a non linear data structure consisting of vertices (nodes) and edges that connect pairs of vertices. Graphs are used to represent relationships, networks, and connections between entities. They are...
Hash Sets
A Hash Set is a collection that stores unique elements with no duplicates, providing O(1) average time for add, remove, and contains operations. It's implemented using a hash table where elements serve as both keys and...
Hash Tables
A Hash Table (also called Hash Map or Dictionary) is a data structure that stores key value pairs and provides near constant time O(1) average case for insertion, deletion, and lookup operations. It uses a hash...
Heaps
A Heap is a specialized tree based data structure that satisfies the heap property: in a max heap, every parent node is greater than or equal to its children; in a min heap, every parent is less than or equal to its...
Linked Lists
A Linked List is a linear data structure where elements (nodes) are stored in non contiguous memory locations. Each node contains data and a reference (pointer) to the next node in the sequence. Unlike arrays, linked...
LRU Cache
An LRU (Least Recently Used) Cache is a data structure that stores a limited number of items and evicts the least recently used item when the cache reaches capacity. It combines a hash map for O(1) lookups with a...
Queues
A Queue is a linear data structure that follows the First In First Out (FIFO) principle. The first element added is the first one to be removed. Think of it like a line at a store: people join at the back and leave...
Red-Black Trees
A Red Black Tree is a self balancing Binary Search Tree where each node has an extra bit for color (red or black). The tree maintains balance through a set of properties that ensure no path from root to leaf is more...
Segment Trees
A Segment Tree is a binary tree data structure used for storing information about intervals (segments) of an array. It allows efficient querying of aggregate information (sum, minimum, maximum, GCD, etc.) over any...
Skip Lists
A Skip List is a probabilistic data structure that allows O(log n) search, insertion, and deletion operations within an ordered sequence. It achieves this by maintaining multiple layers of linked lists, where each...
Stacks
A Stack is a linear data structure that follows the Last In First Out (LIFO) principle. The last element added is the first one to be removed. Think of it like a stack of plates: you can only add or remove from the...
Tries
A Trie (pronounced "try", from retrieval) is a tree like data structure used to store and retrieve strings efficiently. Also called a prefix tree, each node represents a character, and paths from root to nodes...