दोन्ही sequences store करतात, परंतु त्यांच्याकडे विरुद्ध cost profiles आहेत. एक array हा contiguous memory आहे O(1) indexing सह; एक linked list हा scattered nodes आहे pointers ने जोडलेले, 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 फरकांना typical sizes साठी दुर्लक्ष करते.
दोन्ही जाणून घेणे तुम्हाला interviews मध्ये अंधाधुंद default करण्याऐवजी तुमची निवड न्यायसंगत करायला देते — आणि समजावून सांगा का "O(1) insert" क्वचित contiguous array ला हरवते.