Keduanya menyimpan urutan, tetapi memiliki profil biaya yang berlawanan. Array adalah memori kontinu dengan indeksing O(1); linked list adalah node yang tersebar yang digabungkan oleh pointer, dengan O(1) penyisipan/penghapusan di ujung tetapi tanpa indeksing.
| Operasi | Array (dinamis) | Linked list |
|---|
| Akses berdasarkan indeks | O(1) | O(n) |
| Pencarian | O(n) | O(n) |
| Penyisipan/penghapusan di kepala | O(n) | O(1) |
| Penyisipan/penghapusan di ekor | O(1) amortized | O(1) dengan tail ptr |
| Penyisipan/penghapusan di tengah | O(n) | O(n) pencarian + O(1) splice |
| Overhead memori | rendah | tinggi (pointer per node) |
| Lokalitas cache | excellent | buruk |
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
Dalam praktik array menang sebagian besar waktu karena lokalitas cache mengungguli perbedaan Big-O untuk ukuran tipikal.
Mengenal keduanya memungkinkan Anda membenarkan pilihan dalam wawancara daripada memilih default membabi-buta — dan menjelaskan mengapa "penyisipan O(1)" jarang mengalahkan array kontinu.