Data Structures: Arrays, Linked Lists, Stacks, Queues & Trees Guide
Data structures are the building blocks of algorithms. Choosing the right structure for your data can mean the difference between an efficient program and one that struggles with basic operations. This guide covers the essential data structures every programmer should know, their time complexities, practical applications, and how to select the right one for your problem.
Arrays: Contiguous Memory, Constant-Time Access
Arrays store elements in contiguous memory locations, providing O(1) access time by index. The compiler computes the memory address as base_address + index * element_size, making random access as fast as a single memory lookup.
Static vs Dynamic Arrays
Static arrays have fixed capacity defined at compile time. Dynamic arrays (ArrayList in Java, vector in C++, list in Python) resize automatically when full. Resizing allocates a new, usually double-sized, array and copies existing elements — an O(n) operation. However, because resizing happens infrequently, the amortized cost of appending remains O(1).
Dynamic array resizing strategies vary. Python’s list uses approximately 1.125x growth factor, trading more frequent resizes for lower memory waste. C++’s vector uses 2x growth, favoring fewer copies at the cost of up to 50% unused capacity.
Use Cases
Arrays excel when you need fast random access and know the size in advance. Matrix operations, buffer implementations, caching layers, and contiguous memory pools all benefit from array-based storage. The L1 cache friendliness of arrays makes them significantly faster than pointer-based structures for sequential access patterns — modern CPUs prefetch consecutive memory efficiently.
Limitations
Insertion and deletion at arbitrary positions are O(n) because elements must shift. Arrays are impractical for applications requiring frequent insertions in the middle of long sequences.
Linked Lists: Dynamic Insertion, Sequential Access
Linked lists consist of nodes where each node holds data and a reference to the next node. This structure enables O(1) insertion and deletion at known positions but sacrifices random access.
Singly Linked Lists
Each node points only to the next node. Traversal is one-directional. Searching is O(n) — you must follow each pointer sequentially. Insertion at the head is O(1); insertion at the tail requires O(n) traversal or a separate tail pointer.
Doubly Linked Lists
Each node points to both the next and previous nodes, enabling bidirectional traversal and O(1) deletion given a node reference. The trade-off is one additional pointer per node (8 bytes on 64-bit systems). The doubly linked list forms the foundation of Java’s LinkedList and C++’s std::list.
Circular Linked Lists
The tail node points back to the head, forming a circle. Circular lists are useful for round-robin scheduling, where the scheduler cycles through processes indefinitely.
Use Cases
Linked lists shine when you need frequent insertions and deletions at arbitrary positions. They are ideal for implementing queues and stacks without contiguous memory requirements. The Linux kernel uses intrusive linked lists embedded directly in data structures for process management, avoiding separate allocation overhead.
Stacks: Last-In-First-Out (LIFO)
Stacks follow LIFO ordering — the last element pushed is the first popped. All operations (push, pop, peek) are O(1). Stacks can be implemented with either arrays (bounded capacity, cache-friendly) or linked lists (dynamic sizing, per-node overhead).
Applications
The call stack in every programming language uses stack semantics — function calls push frames, returns pop them. Undo operations in editors push each state change onto a stack. Expression evaluation converts infix notation to postfix using the Shunting-Yard algorithm, which relies heavily on stacks. Depth-first search (DFS) of trees and graphs uses an explicit or implicit stack.
Balanced parentheses checking is a classic stack problem: push opening brackets, pop and compare on closing brackets. If the stack is empty at any pop or non-empty at the end, the expression is unbalanced.
Queues: First-In-First-Out (FIFO)
Queues follow FIFO ordering — elements are added at the rear and removed from the front. Simple queues are implemented with singly linked lists (head for dequeue, tail for enqueue) or circular arrays (wrapping indices to reuse space).
Priority Queues
Priority queues dequeue elements by priority rather than insertion order. They are typically implemented with binary heaps, which provide O(log n) insertion and O(log n) extraction of the highest-priority element. Python’s heapq module, Java’s PriorityQueue, and C++’s std::priority_queue all use heap-based implementations.
Priority queues power Dijkstra’s shortest path algorithm, A* search, Huffman coding, and operating system task scheduling. The Linux Completely Fair Scheduler uses red-black trees for priority management, while real-time systems often use fixed-priority preemptive scheduling with multiple queues.
Deques
Double-ended queues (deques) support O(1) insertion and removal at both ends. They are useful for sliding window maximum problems, palindrome checking, and implementing work-stealing algorithms in parallel processing. Python’s collections.deque is implemented as a doubly-linked block array for efficient memory usage.
Hash Tables: Key-Value Storage
Hash tables store key-value pairs and provide average O(1) lookup. A hash function maps keys to bucket indices. Collisions — when two keys hash to the same bucket — are resolved through chaining (linked lists per bucket) or open addressing (probing for the next empty slot).
Load Factor and Resizing
The load factor (elements divided by table size) controls performance. Java’s HashMap resizes at 0.75 load factor by default. Python’s dict uses approximately 2/3 load factor. Lower load factors reduce collisions at the cost of memory. Google’s SwissTable and Abseil flat_hash_map use SIMD operations for faster probing.
Use Cases
Databases use hash indexes for equality lookups. Compilers use symbol tables implemented as hash maps. Caching systems like Redis store key-value pairs in hash tables. Counting word frequencies, detecting duplicates, and implementing sets all rely on hash tables.
Trees: Hierarchical Organization
Trees organize data in parent-child relationships. Binary trees (at most two children per node) are the most common variant. Tree traversals — in-order (left, root, right), pre-order (root, left, right), post-order (left, right, root) — support different access patterns.
Binary Search Trees
BSTs maintain the invariant that for every node, values in the left subtree are smaller and values in the right subtree are larger. Operations are O(h) where h is tree height. In the worst case, h = n (degenerate tree). Self-balancing trees like AVL and Red-Black maintain O(log n) height through rotation operations.
Heaps
Heaps are complete binary trees satisfying the heap property: in a max-heap, every parent is greater than or equal to its children. Build-Heap runs in O(n) time using Floyd’s algorithm. Heaps implement priority queues and power Heap Sort.
Graphs
Graphs extend trees by allowing arbitrary connections between nodes. They are typically represented as adjacency matrices or adjacency lists. Graph algorithms like BFS, DFS, Dijkstra, and Floyd-Warshall solve problems in networking, routing, and social network analysis.
Choosing the Right Data Structure
Selecting the right data structure depends on your access patterns. If you need fast index-based access, use an array. If you need frequent insertions and deletions, use a linked list. If you need key-value lookups, use a hash table. If you need ordered traversal, use a BST. If you need priority-based extraction, use a heap.
FAQ
Which data structure provides the fastest lookup? Hash tables provide average O(1) lookup, making them fastest for equality-based lookup. For ordered data, balanced BSTs provide O(log n) lookup with the benefit of maintaining sorted order. Arrays provide O(1) access by index but O(n) search for values.
When should I use a linked list instead of an array? Use linked lists when you need frequent insertions and deletions at arbitrary positions, when the maximum size is unknown, or when you need guaranteed O(1) insertion at the ends. Use arrays when random access or cache-friendly sequential access is the priority.
What is the difference between a stack and a queue? Stacks operate in LIFO order — the last element added is the first removed. Queues operate in FIFO order — the first element added is the first removed. Use a stack for depth-first traversal and undo operations. Use a queue for breadth-first traversal and task scheduling.
How do hash tables handle collisions? Two primary strategies exist. Chaining stores a linked list (or balanced tree) at each bucket — simple but pointer-heavy. Open addressing probes for the next empty slot — memory-efficient but sensitive to load factor and deletion complexity. Java’s HashMap uses chaining with tree-based buckets for high-collision scenarios.
What is the advantage of a balanced BST over a hash table? Balanced BSTs maintain sorted order automatically, support range queries (find all values between X and Y), and provide predictable O(log n) worst-case performance. Hash tables have faster average-case lookup but no ordering guarantee and potential O(n) degradation with poor hash functions.
What data structure should I use for an LRU cache? Combine a doubly linked list with a hash map. The linked list maintains access order (most recently used at the head, least recently used at the tail). The hash map provides O(1) lookup from key to list node. Get operations move the accessed node to the head. Put operations add to the head and evict from the tail if capacity is exceeded.
Memory Considerations for Data Structures
Cache behavior significantly impacts real-world performance. Arrays maximize cache utilization through spatial locality — consecutive elements occupy adjacent memory. Accessing arr[0] loads a cache line (typically 64 bytes) containing arr[0] through arr[15] (for 4-byte integers). Sequential access hits the cache nearly every time.
Linked lists have poor cache performance because each node may be allocated anywhere in memory. Traversing a linked list of 1 million nodes causes up to 1 million cache misses. At 100 nanoseconds per cache miss, that is 100 milliseconds — versus 5 milliseconds for an array traversal.
Hash tables with open addressing have better cache performance than chaining because entries are stored contiguously. Python’s dict and Google’s SwissTable exploit this by storing all entries in a flat array.