Data Structures Guide with Complexity Cheat Sheet

Data structures organize and store data so it can be used efficiently. Choosing the right data structure is often the difference between a fast program and an unusable one. As computer scientist Niklaus Wirth wrote in his 1976 classic Algorithms plus Data Structures equals Programs, the two are inseparable — the choice of data structure fundamentally shapes the algorithms that can be applied and the performance characteristics of the resulting program.

The practical impact of data structure choice is enormous. A hash table lookup takes nanoseconds while searching an unsorted list of a million elements could take milliseconds — a difference of several orders of magnitude. Google’s 2024 research on large-scale production systems found that optimizing data structure selection reduced query latency by up to 40 percent in tier-one services, highlighting how fundamental this skill is for software engineering at any scale.

Why Data Structures Matter

The performance characteristics of common operations vary dramatically across data structures. An array provides O(1) access by index but O(n) insertion at arbitrary positions because all subsequent elements must be shifted. A linked list provides O(1) insertion at known positions through simple pointer updates but O(n) access by index requiring traversal from the head. A hash table provides O(1) average lookup through direct key-to-address mapping but no ordering guarantees and potential O(n) worst-case from collisions. A balanced binary search tree provides O(log n) for all core operations while maintaining sorted order, at the cost of higher constant factors and more complex implementation.

Understanding these trade-offs allows you to select the structure that matches your application’s dominant access patterns. If your application primarily looks up records by a unique identifier, a hash table provides the fastest access. If you frequently iterate through data in sorted order, a balanced BST or sorted array is more appropriate. If you need fast access by position and cache-friendly iteration, an array is the clear choice.

Array

A contiguous block of memory storing elements of the same type. Arrays provide O(1) access by index through direct memory address computation and cache-friendly iteration where the CPU prefetcher loads adjacent elements ahead of the current access. In Python, lists are dynamic arrays that handle resizing automatically through geometric growth, typically doubling in capacity when full. Best for fast access by index and sequential iteration where the size is known or grows predictably.

Linked List

Nodes connected by pointers, each containing data and a reference to the next node. Singly linked lists provide forward-only traversal with minimal memory overhead of one pointer per node. Doubly linked lists provide forward and backward traversal at the cost of an extra pointer per node. Best for frequent insertions and deletions at known positions where O(1) pointer updates outweigh the cost of traversal and poor cache locality.

Stack

Last-In, First-Out structure where elements are added and removed from the top only. Stacks are elegantly implemented using dynamic arrays since all operations happen at the end, providing O(1) amortized push and O(1) pop operations with excellent cache locality. Use cases include function call stacks for managing return addresses and local variables during nested function calls, undo operations in editors that push actions as they occur and pop to revert, expression evaluation in compilers for converting infix to postfix notation, and depth-first search traversal where the stack manages the exploration frontier.

Queue

First-In, First-Out structure where elements are added to the back and removed from the front. Efficient queue implementations use circular buffers with front and back pointers that wrap around when reaching the end, achieving O(1) operations at both ends without shifting elements. Use cases include breadth-first search traversal in graphs and trees, task scheduling in operating systems and thread pools, print spooling where documents are processed in submission order, IO buffering between producers and consumers, and request management in web servers.

Hash Table

Key-value pairs with O(1) average access achieved through hash functions that map keys to array indices with uniform distribution. Collisions are resolved through chaining with linked lists or balanced trees for large buckets, or through open addressing with probe sequences like linear probing, quadratic probing, or double hashing. Use cases include database indexing for fast record lookup, caching frequently accessed data in memory, set membership testing for deduplication and existence checks, and dictionary or map implementations in virtually every programming language.

Binary Tree

Each node has up to two children, forming the foundation for more specialized tree structures. Binary Search Trees maintain the ordering property that all values in the left subtree are less than the node and all values in the right subtree are greater. Balanced BSTs such as AVL and Red-Black trees maintain O(log n) operations through rotation operations that preserve balance after insertions and deletions. Use cases include maintaining sorted data with fast search, implementing ordered maps and sets in standard libraries, and expression parsing in compilers and calculators.

Heap

A complete binary tree where the parent is always greater than its children in a max-heap or smaller in a min-heap. Heaps are stored as arrays for efficiency with parent and child positions computed through simple arithmetic on array indices, eliminating pointer overhead. Use cases include priority queues where the highest or lowest priority element must be retrieved next, Dijkstra’s shortest path algorithm which extracts the minimum-distance vertex at each iteration, heap sort for guaranteed O(n log n) sorting, and median maintenance through the two-heap technique using a max-heap for the lower half and a min-heap for the upper half.

Graph

Nodes connected by edges which can be directed or undirected, weighted or unweighted. Graphs model the most general relationships and can represent social networks where people are nodes and friendships are edges, transportation networks where locations are nodes and routes are weighted edges, communication networks where devices are nodes and connections are edges, and dependency graphs where tasks are nodes and prerequisites are directed edges.

Choosing the Right Structure

The right data structure depends on your dominant operations. If fast access by index is critical and insertions are infrequent, use an array. If fast insertions and deletions at known positions are critical, use a linked list. For LIFO order use a stack, for FIFO order use a queue, for fast key-value lookup use a hash table, for sorted data with fast search use a balanced BST, for fast minimum or maximum access use a heap, and for modeling relationships between entities use a graph.

Spatial Data Structures

Beyond one-dimensional data, spatial data structures organize multi-dimensional data for efficient range queries and nearest neighbor searches. Quadtrees recursively partition 2D space into four quadrants until each region contains few enough points. They are used in image compression, collision detection in games, and spatial indexing in geographic information systems. Octrees extend the same concept to 3D space with eight children per node, used in 3D graphics rendering and volumetric data analysis.

R-trees group nearby objects with bounding rectangles, organizing them into a balanced hierarchy optimized for disk-based storage. They are the standard spatial index in relational databases for geographic queries, supporting efficient range searches and nearest neighbor lookups. K-d trees partition k-dimensional space with axis-aligned splitting planes, providing efficient nearest neighbor search in high-dimensional spaces for applications like color quantization and particle simulation.

Bloom filters provide space-efficient probabilistic membership tests, useful for caching and spell checking where false positives are acceptable but false negatives are not. They use multiple hash functions to set bits in a bit array, and membership queries check whether all corresponding bits are set. Bloom filters are widely used in distributed databases to reduce disk lookups, in web browsers for malicious URL checking, and in network routers for fast packet classification.

Advanced Data Structures

Beyond the fundamental structures covered above, several advanced data structures address specialized needs. Bloom filters provide space-efficient probabilistic membership tests, useful for caching and spell checking where false positives are acceptable but false negatives are not. Skip lists offer an alternative to balanced BSTs with simpler implementation and good performance through probabilistic balancing. Disjoint set union structures efficiently manage equivalence relations and connected components in graphs. Segment trees and Fenwick trees support range queries and point updates on arrays in O(log n) time.

These advanced structures are less commonly needed in day-to-day programming but become essential when solving specific classes of problems efficiently. Understanding that they exist and knowing their performance characteristics allows you to recognize when a problem calls for them rather than forcing a suboptimal solution with fundamental structures.

Frequently Asked Questions

What is the most commonly used data structure? The dynamic array is the most commonly used across all programming languages. Hash tables are the second most common.

How do I choose between a hash table and a tree? Use a hash table for fast lookups by key when order does not matter. Use a balanced BST for ordered iteration and range queries.

What is a deque and when should I use it? A deque supports O(1) add and remove at both ends. Use for sliding window algorithms and palindrome checking.

Why do balanced trees matter? An unbalanced BST can degenerate into a linked list with O(n) operations. Balanced trees maintain O(log n) through rotations.

Which data structure should I use for caching? Hash tables for O(1) lookups. For LRU caches, combine a hash table with a doubly linked list.

Arrays and Linked Lists Guide — Trees and Graphs Guide — Hash Tables Guide