Real-World Use

The structures in this guide sit underneath almost every program. Knowing how the standard libraries implement them explains many performance surprises and a few classic bugs.

Inside the standard libraries

• CPython `list` is a dynamic array of pointers to objects. It over-allocates by a modest fraction on growth, so appends are amortized O(1) while wasting less memory than doubling.
• CPython `dict` uses open addressing rather than chaining, with a compact layout that has kept insertion order since Python 3.6; the order is a language guarantee from 3.7. set is also a hash table with open addressing.
• `collections.deque` is a doubly linked list of fixed-size blocks (64 items each in CPython), which is why both ends are O(1) but indexing the middle is O(n).
• C++ `std::vector` grows geometrically; the factor is implementation-defined (libstdc++ and libc++ double, MSVC grows by 1.5). std::deque stores fixed-size chunks plus a map of chunk pointers, and std::unordered_map uses separate chaining with a default maximum load factor of 1.0.
• Java `ArrayList` grows by about 1.5 times. HashMap uses a power-of-two bucket array, a default load factor of 0.75, and converts a bucket's chain into a red-black tree once it holds more than 8 entries and the table has at least 64 buckets.
• JavaScript `Map` and `Set` are hash tables that iterate in insertion order.

Where they show up

A good example of combining them is an LRU cache: a hash map finds an entry in O(1) and a doubly linked list keeps entries in recency order so the oldest can be evicted in O(1). Python's OrderedDict is exactly that pair:

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = OrderedDict()

    def get(self, key):
        if key not in self.data:
            return None
        self.data.move_to_end(key)          # mark as most recently used
        return self.data[key]

    def put(self, key, value):
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)   # evict the least recently used

cache = LRUCache(2)
cache.put("a", 1); cache.put("b", 2); cache.get("a"); cache.put("c", 3)
print(list(cache.data))  # ['a', 'c'] -- 'b' was evicted

Pitfalls

• Removing from the front of an array. list.pop(0), ArrayList.remove(0) and Array.prototype.shift move every remaining element. Use a deque or a ring buffer for queues.
• Mutable or inconsistent keys. A key's hash must not change while it is in a table. Python refuses lists as dictionary keys for this reason. In Java, a class used as a key must override equals and hashCode together and should not mutate the fields they use.
• Relying on iteration order. dict, Map and LinkedHashMap preserve insertion order, but HashMap, HashSet, std::unordered_map and Python set do not. Code that happens to work on one input can break on another.
• Invalidated references. When a std::vector reallocates, every pointer, reference and iterator into it becomes invalid. Call reserve up front or store indices.
• Hash flooding. Attackers can send keys that all collide, turning O(1) lookups into O(n). Use the language's randomized hashing (Python does this for strings by default) and limit the number of keys accepted from untrusted input.
• Modifying while iterating. Adding or removing keys while looping over a dictionary raises RuntimeError in Python and ConcurrentModificationException in Java.

The Java pitfall in code: without hashCode, two equal keys land in different buckets and lookups fail. A record generates both methods consistently.

import java.util.HashMap;

public class KeyDemo {
    static final class BadPoint {
        final int x, y;
        BadPoint(int x, int y) { this.x = x; this.y = y; }
        @Override public boolean equals(Object o) {
            return o instanceof BadPoint p && p.x == x && p.y == y;
        }
        // hashCode is missing: equal points get different hash codes
    }

    record Point(int x, int y) {}  // equals and hashCode generated together

    public static void main(String[] args) {
        var bad = new HashMap<BadPoint, String>();
        bad.put(new BadPoint(1, 2), "found");
        var good = new HashMap<Point, String>();
        good.put(new Point(1, 2), "found");
        System.out.println(bad.get(new BadPoint(1, 2)) + " " + good.get(new Point(1, 2)));  // almost always: null found
    }
}

And the C++ one: a pointer taken before a reallocation must not be used afterwards.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{1, 2, 3};
    v.reserve(100);              // capacity fixed in advance: no reallocation below
    int* first = &v[0];
    for (int i = 0; i < 50; ++i) v.push_back(i);
    std::cout << *first << ' ' << v.size() << ' ' << v.capacity() << '\n';  // 1 53 100
    // without reserve, push_back may reallocate and 'first' would dangle
}

Summary

Standard containers are carefully tuned versions of the structures in this guide: dynamic arrays with geometric growth, deques built from blocks, and hash tables with bounded load factors. Use them, choose them by the operations you need, and watch for the common traps: front removal from arrays, unstable keys, assumed ordering, dangling references and untrusted keys.

Further reading

• collections: Container datatypes
• Python Wiki: TimeComplexity
• cppreference: Containers library
• The Java Tutorials: Collections
• MDN: Map
• Wikipedia: Hash table
• VisuAlgo: Linked List, Stack, Queue, Deque