Data Structures

AVL TreetreesAn AVL tree (Adelson-Velsky & Landis, 1962 — the original self-balancing BST) keeps every node's subtree… ArraylinearAn array is a contiguous block of memory holding a fixed-size sequence of equally-sized elements, indexed by… B TreetreesA B-tree is a self-balancing search tree where each node holds many keys and has many children — designed to… Binary Search TreetreesA binary search tree (BST) is a binary tree where every node's left subtree contains smaller keys and right… Cartesian TreetreesA Cartesian tree is a binary tree built from a sequence: every node is greater (or smaller, for a min-heap… Doubly Linked ListlinearA doubly-linked list adds a prev pointer to each node, enabling O(1) insertion and removal anywhere — given a… Hash Tabledata structuresA hash table maps keys to values via a hash function that converts each key to an array index. KD TreetreesA KD-tree (k-dimensional tree) is a binary tree that partitions k-dimensional space by alternating splitting… QueuelinearA queue is a FIFO (first-in, first-out) container with enqueue (add to back) and dequeue (remove from front). Red Black TreetreesA red-black tree is a self-balancing BST where each node is colored red or black and a small set of color… Singly Linked ListlinearA singly-linked list is a chain of nodes, each holding a value and a pointer to the next node. Skip ListlinearA skip list is a probabilistic ordered structure: a base linked list with multiple "express lane" forwarding… Splay TreetreesA splay tree is a self-adjusting BST: every access (search, insert, delete) moves the touched node to the… StacklinearA stack is a LIFO (last-in, first-out) container with two operations: push (add to top) and pop (remove from… Linear StructuresSectionArrays, linked lists, stacks, queues and skip lists. TreesSectionSearch trees and their balanced variants: BST, AVL, red-black, splay, B-tree, Cartesian and KD trees.

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

‹ Algorithms