Kemm-il ikzippja sekwenzi, iżda għandhom profiili ta' kostijiet opposti. Array hija memorja kontinwa b'indexing O(1); linked list hija nodi mifruxa konnessi b'pointers, b'insert/remove O(1) fit-tmiem iżda mingħajr indexing.
Kemm-il ikzippja sekwenzi, iżda għandhom profiili ta' kostijiet opposti. Array hija memorja kontinwa b'indexing O(1); linked list hija nodi mifruxa konnessi b'pointers, b'insert/remove O(1) fit-tmiem iżda mingħajr indexing.
| Operazzjoni | Array (dinamiku) | Linked list |
|---|
| Access b'index | O(1) | O(n) |
| Search | O(n) | O(n) |
| Insert/delete fil-head | O(n) | O(1) |
| Insert/delete fit-tail | O(1) amortized | O(1) b'tail ptr |
| Insert/delete fin-nofs | O(n) | O(n) find + O(1) splice |
| Memory overhead | baxxa | għolja (pointer per node) |
| Cache locality | eċċellenti | ħażina |
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
Fid-dehra arrays jirbħu l-aktar tal-ħin għax cache locality taħfeż Big-O differenzi għall-grandezzi tippiċi.
L-għarfien ta' kemm-il waħda jippermettilk li tiġġustifika l-għażla tiegħek f'interviews minflok taddunaw \ blindly — u tispjega għaliex "O(1) insert" rari jieħu l-ġid ta' array kontinwu.