Data Structures

📚 Overview

Data structures are ways to organize and store data for efficient access and modification.

🔑 Key Concepts

Time Complexity

Operation	Array	Linked List	Hash Table	BST	Heap
Access	O(1)	O(n)	O(1) avg	O(log n)	O(1)
Search	O(n)	O(n)	O(1) avg	O(log n)	O(n)
Insert	O(n)	O(1)*	O(1) avg	O(log n)	O(log n)
Delete	O(n)	O(1)*	O(1) avg	O(log n)	O(log n)

* At head or after an existing reference

🏗️ Common Data Structures

Array

Pros:

• Random access O(1)
• Good memory locality
• Easy to implement

Cons:

• Fixed size (static array)
• Insert/delete expensive

# Python
arr = [1, 2, 3, 4, 5]
arr.append(6)        # O(1) amortized
arr.pop()            # O(1)
arr.insert(0, 0)     # O(n)

Linked List

Pros:

• Dynamic size
• Insert/delete O(1) with reference
• No contiguous memory required

Cons:

• No random access
• Extra memory for pointers
• Poor cache locality

Hash Table

Collision Resolution:

1. Chaining: Each bucket is a linked list
2. Open Addressing: Find the next empty slot (linear probing, quadratic probing)

# Python dict/HashSet
hash_map = {"key": "value"}
hash_map["new_key"] = "new_value"  # O(1) average

Common pitfalls:

• Bad hash function → many collisions
• Load factor too high → degraded performance
• No order guarantee (except Python 3.7+, LinkedHashMap)

Tree - Binary Search Tree (BST)

Properties:

• Left subtree < root
• Right subtree > root
• In-order traversal = sorted array

Operations:

• Search: O(h), h = height
• Insert: O(h)
• Delete: O(h)

Balance:

• Unbalanced BST → O(n)
• Balanced (AVL, Red-Black) → O(log n)

Heap

Min-Heap:

• Parent ≤ Children
• Root = minimum element
• Complete binary tree

Common Operations:

• Insert: O(log n)
• Extract Min/Max: O(log n)
• Peek: O(1)
• Build Heap: O(n)

import heapq

# Min-heap
heap = [3, 1, 4, 1, 5]
heapq.heapify(heap)  # O(n)

heapq.heappush(heap, 2)   # O(log n)
min_val = heapq.heappop(heap)  # O(log n)

🎯 Use Cases

Data Structure	Use Case
Array	Random access, fixed size data
Linked List	Frequent insert/delete, unknown size
Hash Table	Fast lookup, caching
BST	Sorted data, range queries
Heap	Priority queue, top K elements
Graph	Relationships, networks
Trie	Prefix search, autocomplete

❓ Interview Questions

Easy

1. Valid Anagram - Hash table
2. Contains Duplicate - Hash set
3. Reverse Linked List - Two pointers

Medium

1. Group Anagrams - Hash table + sorting
2. LRU Cache - Hash map + doubly linked list
3. Top K Frequent Elements - Heap

Hard

1. Merge K Sorted Lists - Heap
2. Serialize and Deserialize Binary Tree - Tree + String
3. LFU Cache - Hash map + doubly linked list + frequency

🔗 Related Topics

• Algorithms
• System Design - Caching