دونوں sequences کو store کرتے ہیں، لیکن ان کے مختلف cost profiles ہیں۔ ایک array contiguous memory ہے جس میں O(1) indexing ہے؛ ایک linked list scattered nodes ہے جو pointers سے جڑے ہوتے ہیں، جس میں ends پر O(1) insert/remove ہے لیکن indexing نہیں ہے۔
| Operation | Array (dynamic) | Linked list |
|---|
| Access by index | O(1) | O(n) |
| Search | O(n) | O(n) |
| Insert/delete at head | O(n) | O(1) |
| Insert/delete at tail | O(1) amortized | O(1) with tail ptr |
| Insert/delete in middle | O(n) | O(n) find + O(1) splice |
| Memory overhead | low | high (pointer per node) |
| Cache locality | excellent | poor |
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
عملی طور پر arrays زیادہ تر وقت جیتے ہیں کیونکہ cache locality عام سائز کے لیے Big-O فرق سے بہت بڑا ہے۔
dونوں کو جاننا آپ کو interviews میں اپنی پسند کو justify کرنے دیتا ہے بجائے اندھا پن سے default کرنے کے — اور یہ وضاحت کریں کہ کیوں "O(1) insert" شاذ و نادر ہی ایک contiguous array کو شکست دیتا ہے۔