P600Data Structures

Annex B · 21 notes

Reference notes for common and advanced data structures, complexity tradeoffs, implementation patterns, and practical selection guidance.

21
notes: 43
minutes: 89
references: 0
diagrams

ls data-structures/ --order=reading

No. 2ArraysAn 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...2 min
No. 3AVL TreesAn 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...2 min
No. 4B-TreesA 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...2 min
No. 5Binary Search TreesA 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)...2 min
No. 6Binary TreesA 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,...2 min
No. 7Bloom FiltersA 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...2 min
No. 8Data StructuresData 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...2 min
No. 9Disjoint 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...2 min
No. 10Fenwick TreesA 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...2 min
No. 11GraphsA 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...2 min
No. 12Hash SetsA 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...2 min
No. 13Hash TablesA 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...3 min
No. 14HeapsA 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...2 min
No. 15Linked ListsA 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...2 min
No. 16LRU CacheAn 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...2 min
No. 17QueuesA 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...2 min
No. 18Red-Black TreesA 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...2 min
No. 19Segment TreesA 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...2 min
No. 20Skip ListsA 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...2 min
No. 21StacksA 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...2 min
No. 22TriesA 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...2 min