linked list
📊 Big-O Comparison: Array vs Linked List
🔹 Time Complexity
| Operation | Array | Linked List | Notes |
|---|---|---|---|
| Access by index | O(1) | O(n) | Array has direct indexing |
| Search (unsorted) | O(n) | O(n) | Same for both |
| Search (sorted) | O(log n) | O(n) | Binary search only works on arrays |
| Insert at beginning | O(n) | O(1) | Array needs shifting |
| Insert at end | O(1)* | O(n) / O(1) | O(1) if tail pointer exists |
| Insert at middle | O(n) | O(n) | Traversal needed in LL |
| Delete at beginning | O(n) | O(1) | Shifting in array |
| Delete at end | O(1) | O(n) | Need previous node |
| Delete at middle | O(n) | O(n) | Traversal needed |
| Traversal | O(n) | O(n) | Same |
| Update by index | O(1) | O(n) | No index in LL |
| Reverse | O(n) | O(n) | Logic differs |
| Find predecessor | O(1) | O(n) | Easy in arrays |
* Amortized O(1) for dynamic arrays
🔹 Space Complexity
| Structure | Space |
|---|---|
| Array | O(n) |
| Linked List | O(n) + pointers |
Linked list uses extra memory for pointers (next, prev).
🔹 Key Differences (Quick View)
| Feature | Array | Linked List |
|---|---|---|
| Memory | Contiguous | Non-contiguous |
| Indexing | Yes | No |
| Cache friendly | Yes | No |
| Dynamic size | ❌ (static) / ✅ (dynamic array) | ✅ |
| Pointer overhead | ❌ | ✅ |
🔹 When to Use What?
✅ Use Array when:
Fast access by index is needed
Memory efficiency matters
Mostly read operations
✅ Use Linked List when:
Frequent insertions/deletions
Size changes often
No need for random access
🧠 Interview One-Liner
Arrays offer O(1) access but costly insertions, while linked lists allow fast insertions but slow access.
Comments
Post a Comment