Data Structures
list vs dict vs two dicts — the contacts app that makes time & space trade-offs unforgettable.
Your phone has 500 contacts. You type "P" and in 0.2 seconds you see Priya, Pooja, Praveen. It doesn't read all 500 names one by one — that would take 500 steps.
Now WhatsApp gets a call from +91 98765 43210. It shows whose number this is before you pick up. To do that instantly, it keeps a second copy of contacts mapped by phone number — same data stored twice, 2× the memory, but the answer is instant.
Every data structure trades time for space or space for time. Pick wrong and a 1ms operation becomes a 10-second freeze.
⏲ The Two Costs (5–25 min)
O(1) = 1 step always (dict lookup)
O(log n) = 10 steps for 1000 items (binary search)
O(n) = 1000 steps for 1000 items (list scan)
O(1) = no extra (list — just the array)
O(n) = extra proportional to items (dict overhead)
O(2n) = double your data (two dicts, bidirectional)
📞 The Contacts App — 4 Structures, 1 Problem
Store contacts as a list of tuples. To find "Priya": check every item from index 0.
⚠ For 5 million WhatsApp contacts, this is 5 million checks per search. The app freezes.
Sort contacts A–Z, use Python's bisect for binary search. Found "Priya" in 9 steps from 500 contacts.
⚠ Adding a new contact? Must re-sort or shift elements. Good for read-heavy, bad if contacts change often.
Python dict maps name → phone. Finding "Priya": hash("Priya"), go directly to that slot. No scanning.
Need both: name→number AND number→name. Store two dicts — one forward, one reverse.
Double memory for instant two-way lookup. WhatsApp makes this trade because caller ID speed matters more than RAM.
💻 Live Coding — ContactBook in Python (25–45 min)
# contact_book.py # ── Option 1: list ───────────────────────────────────────────────────────── contact_list = [] def add_to_list(name, phone): contact_list.append((name, phone)) def find_in_list(name): steps = 0 for contact in contact_list: # O(n) — checks every contact steps += 1 if contact[0] == name: print(f" list: found in {steps} steps") return contact[1] return None # ── Option 3: dict (one-way) ─────────────────────────────────────────────── name_to_phone = {} # empty dict def add_to_dict(name, phone): name_to_phone[name] = phone # O(1) insert def find_in_dict(name): print(" dict: found in 1 step O(1)") return name_to_phone.get(name) # O(1) — always 1 step # ── Option 4: two dicts (bidirectional) ────────────────────────────────── phone_to_name = {} # EXTRA memory! def add_bidirectional(name, phone): name_to_phone[name] = phone # forward phone_to_name[phone] = name # reverse ── costs 2x space def whose_number(phone): return phone_to_name.get(phone) # O(1) ── paid with space # ── Demo ─────────────────────────────────────────────────────────────────── for i in range(1, 500): add_to_list(f"Contact{i}", f"900000{i}") add_to_dict(f"Contact{i}", f"900000{i}") add_to_list("Priya", "9876543210") # last entry — worst case add_bidirectional("Priya", "9876543210") print("Searching for Priya...") find_in_list("Priya") # 500 steps! find_in_dict("Priya") # 1 step print(f"\nIncoming call: 9876543210") print(f"Caller: {whose_number('9876543210')}") # Priya
📄 When to Use Each Structure
| Structure | Search | Insert | Space | Use it when… | Real Example |
|---|---|---|---|---|---|
| list | O(n) | O(1) | O(n) | Ordered data, loop through, rarely search by value | Zomato order history — shown newest first, you scroll through in order, never jump to "order #347" |
| dict | O(1) | O(1) | O(n)+overhead | Instant lookup by key (name, ID, token) | Contacts app — type "Priya", instant result. Also: every login session (token → userId), every product page cache |
| Two dicts | O(1) both | O(1) | O(2n) | Instant lookup in both directions | WhatsApp caller ID — name↔number. Same data twice, O(1) both ways. Double memory, zero latency |
| set | O(1) | O(1) | O(n)+overhead | Unique items, fast membership check | Instagram following — "Is Priya following Ravi?" O(1) check in a set of 1 billion users |
| deque (Stack) | O(n) | O(1) | O(n) | Last-in-first-out: undo, browser back | VS Code Ctrl+Z — every keystroke pushed onto a stack, Ctrl+Z pops the last one |
| deque (Queue) | O(n) | O(1) | O(n) | First-in-first-out: jobs in arrival order | Swiggy restaurant queue — first order placed = first cooked. Also: OTP SMS delivery jobs |
- Copy
contact_book.pyinto VS Code and run it — see "500 steps" vs "1 step" yourself - Add function
delete_contact(name)that removes from both dicts — get the phone first, then delete both keys - Add function
rename_contact(old, new)— update both dicts correctly - Space challenge: Add
recent_searches = []and updatefind_in_dict()to save each search — keep max 10, remove oldest when over - Think out loud: If RAM was expensive (embedded device), which structure would you drop? Tell the instructor your reasoning
📄 Day 2 Cheat Sheet — Python Data Structures
list
| contacts = [] | Create empty |
| contacts.append(x) | Add end — O(1) |
| contacts[0] | By index — O(1) |
| x in contacts | Search — O(n) |
| contacts.remove(x) | Remove — O(n) |
| sorted(contacts) | Sort — O(n log n) |
dict
| d = {} | Create empty |
| d["key"] = val | Insert — O(1) |
| d["key"] | Lookup — O(1) |
| d.get("key", default) | Safe get |
| "key" in d | Check — O(1) |
| del d["key"] | Delete — O(1) |
set & deque
| s = set() | Empty set |
| s.add(x) | Add — O(1) |
| x in s | Check — O(1) |
| from collections import deque | Import |
| dq.append(x) / dq.pop() | Stack (LIFO) |
| dq.append(x) / dq.popleft() | Queue (FIFO) |
Space–Time Rule
| Fast search by key? | dict — costs memory |
| Both-way lookup? | Two dicts — costs 2x memory |
| Memory tight? | sorted list + bisect |
| Unique items? | set — O(1) check |
| Undo / back? | deque as stack |
| Job queue? | deque as queue |