Common Data Structures Pitfalls

Knowing a data structure's textbook complexity is not the same as using it correctly under pressure. Most interview and production bugs come from a small, recurring set of mistakes: off-by-one errors, forgetting worst-case behavior, ignoring collisions, and reaching for the wrong structure out of habit. This topic walks through the pitfalls that show up again and again, why they happen, and the concrete fix for each.

Off-by-one errors happen because array indices are zero-based but human counting is one-based, and loop bound conventions differ (< n vs <= n-1 vs < n-1). Common triggers: using <= instead of < in a loop and reading one element past the end, forgetting that a slice arr[i:j] excludes j, or miscalculating a midpoint in binary search as (low+high)/2 without considering integer overflow or infinite loops when low and high don't converge. Fix: always test loop bounds against the smallest cases (empty array, single element) and trace through indices explicitly rather than trusting intuition.

An unbalanced BST can degrade into a linked list — for example, inserting sorted data (1, 2, 3, 4, 5...) into a plain BST produces a tree that is entirely right children, turning every 'O(log n)' operation into O(n). The fix is to use a self-balancing structure (AVL tree, red-black tree) that performs rotations to keep height at O(log n), or to note in an interview that you'd use one when input order isn't guaranteed to be random.

Built-in hash tables (Python dict, Java HashMap) do handle collisions internally via chaining or open addressing, but the pitfall shows up when candidates implement a hash map from scratch and forget to handle collisions at all — silently overwriting values that hash to the same bucket. It also shows up when using mutable or poorly-distributed objects as keys, causing many collisions and degrading performance to O(n). Fix: when implementing a hash table, always chain or probe on collision, and choose keys with a good, immutable hash implementation.

Stating 'hash table lookup is O(1)' without qualification ignores that it's O(n) worst case if the hash function distributes keys poorly or an adversary crafts colliding keys (a known denial-of-service vector). Interviewers often push on this specifically to see if you understand the caveat. Fix: always state complexity as 'O(1) average, O(n) worst case' and explain what conditions cause the worst case.

Checking membership with x in my_list is O(n) because it scans linearly, while x in my_set or x in my_dict is O(1) average because it hashes directly to a bucket. A common pitfall is deduplicating or checking 'have I seen this before' inside a loop using a list, silently turning an O(n) algorithm into O(n^2). Fix: use a set for membership checks and a dict when you need to associate a value with the key, reserving lists for cases where order or duplicates matter.

Each recursive call pushes a new stack frame onto the call stack. Without a base case, an incorrect base case, or on very deep input (e.g. recursing over a linked list with 100,000 nodes), the call stack exceeds its limit and the program crashes with a stack overflow (or RecursionError in Python, which has a default recursion limit around 1000). Fix: verify the base case terminates correctly, convert deep recursion to an iterative approach using an explicit stack, or use tail-call-friendly patterns where the language supports optimizing them (note: Python does not optimize tail calls).

Removing or adding elements to a list, set, or dict while iterating over it directly (e.g. for x in my_list: my_list.remove(x)) causes skipped elements, RuntimeError (dicts/sets in Python), or undefined behavior in other languages, because the iterator's internal index or structure assumption becomes invalid mid-loop. Fix: iterate over a copy (for x in list(my_list):), build a new collection, or collect items to remove first and remove them after the loop.

In Python, a mutable default argument like def f(x, cache={}): is created once and shared across all calls, so mutations persist unexpectedly between invocations — a classic source of hard-to-debug state leaks in memoized functions or tree/graph builders. Similarly, appending the same list reference into multiple tree nodes means mutating one mutates all. Fix: use None as the default and create a new mutable object inside the function body, and be deliberate about when you want shared vs copied references.

In languages with fixed-width integers (Java, C++), computing a binary search midpoint as (low + high) / 2 can overflow if low + high exceeds the integer range, producing a negative or wrapped value and an incorrect index. Python integers don't overflow, but the same bug pattern ((low + high) // 2 vs low + (high - low) // 2) is still worth knowing since interviewers may ask about it or test in a typed language. Fix: use low + (high - low) // 2 to avoid the intermediate overflow-prone sum.