Tablice a połączone listy
Tablice są najczęściej używaną strukturą danych do przechowywania kolekcji elementów. Większość języków programowania udostępnia metody do łatwego deklarowania tablic i uzyskiwania dostępu do elementów w tablicach. Lista połączona, a dokładniej lista połączona pojedynczo, to również struktura danych, która może służyć do przechowywania kolekcji elementów. Składa się z sekwencji węzłów, a każdy węzeł ma odniesienie do następnego węzła w sekwencji.
Na rysunku 1 pokazano fragment kodu zwykle używany do deklarowania i przypisywania wartości do tablicy. Rysunek 2 przedstawia wygląd tablicy w pamięci.
Powyższy kod definiuje tablicę, która może przechowywać 5 liczb całkowitych i są one dostępne za pomocą indeksów od 0 do 4. Jedną z ważnych właściwości tablicy jest to, że cała tablica jest alokowana jako pojedynczy blok pamięci, a każdy element ma swoje własne miejsce w tablicy. Po zdefiniowaniu tablicy jej rozmiar jest ustalony. Więc jeśli nie masz pewności co do rozmiaru tablicy w czasie kompilacji, musisz zdefiniować wystarczająco dużą tablicę, aby była po bezpiecznej stronie. Ale przez większość czasu będziemy używać mniej elementów niż przydzieliliśmy. Tak więc znaczna ilość pamięci jest faktycznie marnowana. Z drugiej strony, jeśli „wystarczająco duża tablica” nie jest wystarczająco duża, program się zawiesi.
Połączona lista alokuje pamięć do swoich elementów oddzielnie we własnym bloku pamięci, a ogólna struktura jest uzyskiwana przez łączenie tych elementów jako ogniwa w łańcuchu. Każdy element na połączonej liście ma dwa pola, jak pokazano na rysunku 3. Pole danych zawiera faktycznie przechowywane dane, a następne pole zawiera odniesienie do następnego elementu w łańcuchu. Pierwszy element połączonej listy jest przechowywany jako nagłówek połączonej listy.
| dane | następny |
Rysunek 3: Element połączonej listy
Rysunek 4 przedstawia połączoną listę z trzema elementami. Każdy element przechowuje swoje dane, a wszystkie elementy z wyjątkiem ostatniego przechowują odniesienie do następnego elementu. Ostatni element zawiera wartość null w następnym polu. Dostęp do dowolnego elementu na liście można uzyskać, zaczynając od nagłówka i podążając za następnym wskaźnikiem, aż napotkasz wymagany element.
Mimo że tablice i połączone listy są podobne w tym sensie, że obie są używane do przechowywania kolekcji elementów, powodują różnice ze względu na strategie, których używają do przydzielania pamięci swoim elementom. Tablice przydzielają pamięć wszystkim jej elementom jako pojedynczy blok, a rozmiar tablicy musi być określony w czasie wykonywania. To spowodowałoby, że tablice byłyby nieefektywne w sytuacjach, w których nie znasz rozmiaru tablicy w czasie kompilacji. Ponieważ lista połączona alokuje pamięć do swoich elementów oddzielnie, byłaby bardzo wydajna w sytuacjach, w których nie znasz rozmiaru listy w czasie kompilacji. Deklaracja i dostęp do elementów na połączonej liście nie byłyby proste w porównaniu z bezpośrednim dostępem do elementów tablicy za pomocą jej indeksów.
