Data Structure Glossary

An ordered collection of elements accessed by index. Fixed size in static arrays; dynamic arrays resize automatically.

A sequence of nodes where each node contains data and a reference to the next (and optionally previous) node. Allows O(1) insertions/deletions at known positions.

A LIFO (last‑in, first‑out) collection. Primary operations are push and pop.

A FIFO (first‑in, first‑out) collection. Supports enqueue and dequeue. Variants include priority queue and deque.

Provides average O(1) lookup, insertion, and deletion by mapping keys to indices via a hash function. Handles collisions through chaining or open addressing.

A hierarchical structure where each node has at most two children (left and right). Used for search trees, expression parsing, etc.

A binary tree where left subtree nodes are less than the node and right subtree nodes are greater. Supports O(log n) average search, insert, delete.

A self‑balancing BST where the heights of two child sub‑trees differ by at most one, guaranteeing O(log n) operations.

Another self‑balancing BST with color properties that ensure the longest path is no more than twice the shortest, providing O(log n) operations.

A complete binary tree that satisfies the heap property: each parent is ≤ (min‑heap) or ≥ (max‑heap) its children. Enables O(log n) insert and extract‑max/min.

A set of vertices connected by edges. Can be directed/undirected, weighted/unweighted. Represented via adjacency lists or matrices.

A prefix tree used for efficient retrieval of strings, commonly in auto‑complete and dictionary implementations.

A probabilistic set membership structure that may yield false positives but never false negatives. Uses multiple hash functions.