Jak są zbudowane tablice w programowaniu?

Tablice są uporządkowanymi kolekcjami elementów tego samego typu, przechowywanymi w sąsiadujących (sekwencyjnych) komórkach pamięci.

Główne cechy:

• Indeksacja: Dostęp do elementów odbywa się za pomocą indeksu, który zaczyna się od 0. Indeks wskazuje przesunięcie od początku tablicy.
• Rozmiar: Rozmiar tablicy (liczba elementów) jest stały podczas jej tworzenia w językach statycznie typowanych lub może się dynamicznie zmieniać w językach z dynamicznym typowaniem (np. w Swift Array).
• Typ danych: Wszystkie elementy tablicy muszą mieć ten sam typ danych.
• Sąsiedztwo: Przechowywanie elementów w sąsiadujących komórkach pamięci zapewnia szybki dostęp do dowolnego elementu przez jego indeks.

Operacje:

• Dostęp przez indeks: O(1) - czas stały.
• Dodawanie/usuwanie na końcu: O(1) średnio dla dynamicznych tablic (Swift Array).
• Dodawanie/usuwanie na początku lub w środku: O(n) - czas liniowy, ponieważ może być konieczne przesunięcie elementów.

Przykład w Swift:

// Tworzenie tablicy stringów
var names: [String] = ["Alice", "Bob", "Charlie"]

// Dostęp do elementu przez indeks
let first_name = names[0] // "Alice"

// Dodanie elementu
names.append("David") // ["Alice", "Bob", "Charlie", "David"]

// Usunięcie elementu
names.remove(at: 1) // ["Alice", "Charlie", "David"]

// Iteracja po tablicy
for name in names {
    print(name)
}

Struktura wewnętrzna (dla dynamicznych tablic typu Swift Array):

Dynamically arrays are usually implemented on top of a statically allocated memory buffer. When the capacity of the buffer is reached, a new, larger buffer is allocated and the old elements are copied (reallocation). This provides an amortized O(1) complexity for appending at the end.