Tablica to ciągły blok pamięci zawierający elementy tego samego typu, indeksowane od 0. Ponieważ elementy znajdują się obok siebie, adres elementu i jest obliczany bezpośrednio jako base + i * elementSize, co daje dostęp losowy O(1).
Tablica to ciągły blok pamięci zawierający elementy tego samego typu, indeksowane od 0. Ponieważ elementy znajdują się obok siebie, adres elementu i jest obliczany bezpośrednio jako base + i * elementSize, co daje dostęp losowy O(1).
index: 0 1 2 3 4
+-----+-----+-----+-----+-----+
arr = | 10 | 20 | 30 | 40 | 50 |
+-----+-----+-----+-----+-----+
address: base +4 +8 +12 +16 (4-byte ints)
arr = [10, 20, 30, 40, 50]
x = arr[3] # O(1) — direct index math
arr.append(60) # amortized O(1) (dynamic array)
arr.insert(0, 5) # O(n) — shift every element right
arr.pop(0) # O(n) — shift every element left
| Operacja | Czas |
|---|---|
| Dostęp przez indeks | O(1) |
| Wyszukiwanie (nieuporządkowane) | O(n) |
| Dołączenie (dynamiczne) | O(1) amortyzowane |
| Wstawienie/usunięcie na początku/w środku | O(n) |
Tablice stanowią fundament większości innych struktur — ciągi znaków, tabele haszujące, kopce i listy dynamiczne są na nich zbudowane.
Ich lokalność pamięci podręcznej często sprawia, że "wolniejsza" tablica z punktu widzenia Big-O pokonuje "szybszą" strukturę opartą na wskaźnikach w rzeczywistych testach wydajności.