Obie przechowują sekwencje, ale mają przeciwstawne profile kosztów. Tablica to contiguous memory z dostępem O(1); lista powiązana to rozproszone węzły połączone wskaźnikami, z O(1) wstawianiem/usuwaniem na końcach, ale bez indeksowania.
Obie przechowują sekwencje, ale mają przeciwstawne profile kosztów. Tablica to contiguous memory z dostępem O(1); lista powiązana to rozproszone węzły połączone wskaźnikami, z O(1) wstawianiem/usuwaniem na końcach, ale bez indeksowania.
| Operacja | Tablica (dynamiczna) | Lista powiązana |
|---|
| Dostęp przez indeks | O(1) | O(n) |
| Wyszukiwanie | O(n) | O(n) |
| Wstawianie/usuwanie na początku | O(n) | O(1) |
| Wstawianie/usuwanie na końcu | O(1) amortyzowane | O(1) z tail ptr |
| Wstawianie/usuwanie w środku | O(n) | O(n) szukaj + O(1) splice |
| Overhead pamięci | niski | wysoki (wskaźnik na węzeł) |
| Lokalność cache | doskonała | słaba |
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
W praktyce tablice zwycięskają większość czasu, ponieważ lokalność cache przewyższa różnice Big-O dla typowych rozmiarów.
Znajomość obydwu pozwala ci uzasadnić swój wybór w rozmowach zamiast ślepo wybierać domyślnie — i wyjaśnić dlaczego "O(1) wstawianie" rzadko pokonuje contiguous tablicę.