Mindkettő sorozatot tárol, de ellentétes költségprofillal rendelkeznek. A tömb folytonos memória O(1) indexeléssel; a kapcsolt lista szétszórt csomópontok, amelyek mutatókkal összekapcsolódnak, O(1) beszúrás/törlés a végeken, de indexelés nélkül.
Mindkettő sorozatot tárol, de ellentétes költségprofillal rendelkeznek. A tömb folytonos memória O(1) indexeléssel; a kapcsolt lista szétszórt csomópontok, amelyek mutatókkal összekapcsolódnak, O(1) beszúrás/törlés a végeken, de indexelés nélkül.
| Operáció | Tömb (dinamikus) | Kapcsolt lista |
|---|
| Hozzáférés indexek szerint | O(1) | O(n) |
| Keresés | O(n) | O(n) |
| Beszúrás/törlés az elején | O(n) | O(1) |
| Beszúrás/törlés a végén | O(1) amortizált | O(1) farok mutatóval |
| Beszúrás/törlés a közepén | O(n) | O(n) keresés + O(1) összeillesztés |
| Memória terhelés | alacsony | magas (mutató csomópontonként) |
| Cache lokalitás | kitűnő | gyenge |
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
A gyakorlatban a tömbök többnyire nyernek, mivel a cache lokalitása felülmúlja a Big-O különbségeket a tipikus méreteknél.
Mindkettőt ismerve igazolhatja a választásait az interjúkon ahelyett, hogy vakon alapértelmezne — és megmagyarázza, hogy miért az "O(1) beszúrás" ritkán győzi le a folytonos tömböt.