Python Data Structures: 5M-Item List Search Timed Out

Data structures aren't just a Computer Science exam topic — they're the daily tools every Python developer reaches for without thinking. Whether you're building a REST API, scraping a website, or crunching data in pandas, the choice between a list and a set, or a dict and a defaultdict, changes how fast your code runs and how readable it stays. Interviewers love data structure questions because they reveal whether you understand trade-offs, not just syntax.

The real problem most candidates have isn't that they don't know what a list is. It's that they can't articulate WHY they'd choose one structure over another under pressure, and they miss the subtle gotchas — mutability, hashing, ordering guarantees — that separate junior answers from senior ones.

By the end of this article you'll be able to answer questions about time complexity, pick the right structure for a given problem, explain the internals of dicts and sets in plain English, and dodge the three most common mistakes candidates make mid-interview. Let's build this up piece by piece.

Lists vs Tuples — It's Not Just About Mutability

Every candidate says 'lists are mutable, tuples are immutable' — and then the interviewer nods politely and waits for more. That answer is correct but incomplete.

The deeper WHY: because tuples are immutable, Python can store them more efficiently in memory and use them as dictionary keys or set members. A list can never be a dict key — try it and you'll get a TypeError. Tuples also communicate intent: when you return (latitude, longitude) from a function, you're signalling to the next developer 'these two values belong together and shouldn't be shuffled around'.

Lists shine when your collection needs to grow, shrink, or be sorted — think a queue of incoming HTTP requests or a shopping cart. Tuples shine when you want a fixed record — RGB colours, database row results, coordinate pairs.

Appending to a list is O(1) amortised — Python over-allocates memory in chunks, so you're not copying the whole list on every append. Inserting at position 0 is O(n), because every element shifts right. That detail trips up a lot of candidates.

import time
import sys

# 1. Memory Efficiency: Tuples are smaller because they are fixed-size
tpl = (1, 2, 3, 4, 5)
lst = [1, 2, 3, 4, 5]
print(f"Tuple size: {sys.getsizeof(tpl)} bytes")
print(f"List size:  {sys.getsizeof(lst)} bytes")

# 2. Hashability: Using a tuple as a coordinate key
locations = {
    (40.7128, -74.0060): "New York",
    (51.5074, -0.1278): "London"
}
print(f"Location lookup: {locations[(40.7128, -74.0060)]}")

# 3. Performance Trap: O(n) vs O(1)
data = list(range(100_000))

start = time.perf_counter()
data.append(100_001)  # O(1) amortized
print(f"Append time: {time.perf_counter() - start:.8f}s")

start = time.perf_counter()
data.insert(0, -1)     # O(n) - moving 100k items!
print(f"Insert at front time: {time.perf_counter() - start:.8f}s")

Dictionaries and Sets — Hash Tables Under the Hood

Python dicts and sets are both built on hash tables — and understanding that one fact makes you dangerous in interviews.

Here's the mental model: when you do user_scores['alice'], Python doesn't scan the entire dict looking for 'alice'. It runs hash('alice'), gets a number, jumps directly to the corresponding memory bucket, and returns the value. That's why dict lookup is O(1) — it's a single mathematical jump, not a search.

Sets work identically but only store keys, no values. That's why 'alice' in large_set is blindingly fast while 'alice' in large_list gets slower as the list grows.

The critical interview implication: only hashable objects can be dict keys or set members. Integers, strings, and tuples are hashable. Lists and dicts are not — they're mutable, so their hash could change after insertion, which would corrupt the hash table.

Since Python 3.7, dicts maintain insertion order as a language guarantee — not an implementation detail. That matters when you're iterating and need predictable output.

from collections import Counter
import time

# 1. Membership Testing: List vs Set (The FAANG Favorite)
large_list = list(range(10_000_000))
large_set = set(large_list)

start = time.perf_counter()
9_999_999 in large_list  # O(n) - must check every item
print(f"List search: {time.perf_counter() - start:.5f}s")

start = time.perf_counter()
9_999_999 in large_set   # O(1) - immediate hash jump
print(f"Set search:  {time.perf_counter() - start:.5f}s")

# 2. Frequency Analysis with Counter
logs = ["ERROR", "INFO", "ERROR", "WARN", "ERROR", "INFO"]
error_counts = Counter(logs)
print(f"Most common: {error_counts.most_common(1)}")

# 3. Set Algebra: Finding common items
admin_ids = {101, 105, 110}
active_ids = {105, 110, 120}
print(f"Active Admins: {admin_ids & active_ids}") # Intersection

Stacks, Queues, and When the Built-ins Aren't Enough

Python doesn't have built-in Stack or Queue classes — and that confuses candidates who learned data structures in Java or C++. The Pythonic answer is: use what already exists, but use it correctly.

A list works fine as a stack (LIFO): append() to push, pop() to pop — both O(1). But using a list as a queue is a performance trap. list.pop(0) removes from the front and is O(n) because every remaining element shifts.

For queues (FIFO), use collections.deque. It's a doubly-linked list under the hood — appendleft and popleft are O(1). For priority queues — where you want to always retrieve the smallest (or largest) item first — use the heapq module. This comes up constantly in real interviews, especially graph problems like Dijkstra's algorithm.

Knowing the right tool signals that you've actually used Python in production, not just read a tutorial.

from collections import deque
import heapq

# 1. Efficient Queue with deque
visitor_queue = deque(["User_A", "User_B"])
visitor_queue.append("User_C")   # O(1)
served = visitor_queue.popleft() # O(1)
print(f"Served: {served}, Remaining: {list(visitor_queue)}")

# 2. Priority Queue (Min-Heap)
tasks = []
# Pushing tuples: (priority, data)
heapq.heappush(tasks, (3, "Low Priority Job"))
heapq.heappush(tasks, (1, "Critical Hotfix"))
heapq.heappush(tasks, (2, "Standard Feature"))

# Always pops the lowest priority number first
while tasks:
    prio, task = heapq.heappop(tasks)
    print(f"Processing: [{prio}] {task}")

List Comprehensions, Memory, and Generator Expressions

List comprehensions are one of Python's most loved features — and one of the most misused. The interview trap isn't 'can you write one?' — it's 'do you know when NOT to use one?'

A list comprehension builds the entire list in memory at once. If you're filtering a million database records to find ten matches, you've just loaded a million items into RAM before discarding 999,990 of them. That's wasteful.

Generator expressions solve this. They look almost identical to list comprehensions but use parentheses instead of square brackets. Crucially, they're lazy — they compute each value only when you ask for it. Memory usage stays flat regardless of input size.

For interview questions about large datasets, memory efficiency, or streaming data, generator expressions are almost always the right answer. Interviewers listen carefully for whether you distinguish between the two.

import sys

# Generating 1 million squares
n = 1_000_000

# List Comprehension: All numbers stored in RAM
sq_list = [x**2 for x in range(n)]
print(f"List Comp Size: {sys.getsizeof(sq_list) / 1024:.2f} KB")

# Generator Expression: Only the object/logic stored
sq_gen = (x**2 for x in range(n))
print(f"Generator Size: {sys.getsizeof(sq_gen)} bytes")

# Consuming the generator (simulated file processing)
print(f"First item: {next(sq_gen)}")
print(f"Second item: {next(sq_gen)}")

Choosing the Right Data Structure: The Interview Decision Tree

Interviewers love asking you to pick the right structure for a problem. The real skill isn't memorising APIs — it's knowing the trade-offs. Here's a practical decision tree:

• Need to look up items by a key? → Dict (or defaultdict for missing keys).
• Need to store items without duplicates and check membership fast? → Set (or frozenset if immutable).
• Need to maintain insertion order and allow duplicates? → List.
• Need a fixed record that can be used as a key? → Tuple.
• Need a FIFO queue? → deque (not list).
• Need to always get the smallest/largest element? → heapq (priority queue).
• Need to count frequencies? → collections.Counter.
• Need a read-only, hashable set? → frozenset.

The key insight: most interview problems reduce to choosing the right underlying data structure. Once you do, the algorithm becomes obvious.

Practice with problems like: "Design a system to cache the last N visited URLs" → OrderedDict. "Find unique words in a 10GB file" → set or bloom filter. "Track the users who visited today" → set.

from collections import defaultdict, Counter, OrderedDict

# Problem: Count word frequencies in a log file efficiently
log_lines = ["INFO: user login", "ERROR: timeout", "INFO: user login"]
counter = Counter()
for line in log_lines:
    word = line.split(':')[0]
    counter[word] += 1
print(f"Frequencies: {dict(counter)}")

# Problem: LRU-like cache with ordered dict
def process_request(url):
    pass
recent = OrderedDict()
recent['/home'] = 'cached'
recent['/about'] = 'cached'
recent.move_to_end('/home')  # mark as recently used
print(f"Cache order: {list(recent.keys())}")