Data Structures

The containers everything else is built from — arrays and lists, hash tables, and the tree families that keep themselves balanced.

Pages in this Section

• AVL Tree — An AVL tree (Adelson-Velsky & Landis, 1962 — the original self-balancing BST) keeps every node's subtree heights within 1 of each other. It is more rigidly balanced than a red-black…
• Array — An array is a contiguous block of memory holding a fixed-size sequence of equally-sized elements, indexed by position. Python's list is a dynamic array (ArrayList in other languages) — O(1)…
• B Tree — A B-tree is a self-balancing search tree where each node holds many keys and has many children — designed to minimize disk reads. It's the structure behind virtually every relational…
• Binary Search Tree — A binary search tree (BST) is a binary tree where every node's left subtree contains smaller keys and right subtree contains larger keys. Average O(log n) operations on random input — but a…
• Cartesian Tree — A Cartesian tree is a binary tree built from a sequence: every node is greater (or smaller, for a min-heap variant) than its descendants in heap order, while the in-order traversal recovers…
• Doubly Linked List — A doubly-linked list adds a prev pointer to each node, enabling O(1) insertion and removal anywhere — given a node reference. collections.deque in Python is implemented as a doubly-linked…
• Hash Table — A hash table maps keys to values via a hash function that converts each key to an array index. Average O(1) for insert, lookup, and delete; worst case O(n) when too many keys collide.…
• KD Tree — A KD-tree (k-dimensional tree) is a binary tree that partitions k-dimensional space by alternating splitting axes. It enables fast nearest-neighbor and range queries in low dimensions — the…
• Queue — A queue is a FIFO (first-in, first-out) container with enqueue (add to back) and dequeue (remove from front). Use collections.deque in Python — O(1) at both ends. A list as a queue is O(n)…
• Red Black Tree — A red-black tree is a self-balancing BST where each node is colored red or black and a small set of color invariants keep the tree height ≤ 2 log(n+1). Used in C++ std::map/std::set, Java…
• Singly Linked List — A singly-linked list is a chain of nodes, each holding a value and a pointer to the next node. Insert/delete at the head is O(1); access by index is O(n) because you must walk from the head.
• Skip List — A skip list is a probabilistic ordered structure: a base linked list with multiple "express lane" forwarding pointers above it. Each node is randomly promoted to higher levels, giving O(log…
• Splay Tree — A splay tree is a self-adjusting BST: every access (search, insert, delete) moves the touched node to the root through a sequence of rotations called "splaying." It has no balance…
• Stack — A stack is a LIFO (last-in, first-out) container with two operations: push (add to top) and pop (remove from top). Backed by an array or linked list; Python uses a list for stacks idiomatically.

‹ Algorithms