Her ikisi de dizileri depolar, ancak karşıt maliyet profillerine sahiptir. Dizi, O(1) indeksleme ile bitişik bellektir; bağlantılı liste, işaretçilerle birleştirilen dağınık düğümlerdir; uçlarda O(1) ekleme/silme ancak indeksleme yoktur.
Her ikisi de dizileri depolar, ancak karşıt maliyet profillerine sahiptir. Dizi, O(1) indeksleme ile bitişik bellektir; bağlantılı liste, işaretçilerle birleştirilen dağınık düğümlerdir; uçlarda O(1) ekleme/silme ancak indeksleme yoktur.
| İşlem | Dizi (dinamik) | Bağlantılı liste |
|---|
| İndekse göre erişim | O(1) | O(n) |
| Arama | O(n) | O(n) |
| Başta ekleme/silme | O(n) | O(1) |
| Sonda ekleme/silme | O(1) amortized | O(1) kuyruk ptr ile |
| Ortada ekleme/silme | O(n) | O(n) arama + O(1) splice |
| Bellek yükü | düşük | yüksek (düğüm başına işaretçi) |
| Önbellek yerellığı | mükemmel | kötü |
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
Uygulamada diziler çoğu zaman kazanır çünkü önbellek yerelliliği tipik boyutlar için Big-O farklarını gölgeler.
Her ikisini bilmek, sahte bir şekilde varsayılan olarak seçim yapmak yerine görüşmelerde seçiminizi haklı çıkarmanızı sağlar — ve neden "O(1) ekleme" nadiren bitişik bir diziyi yendiğini açıklar.