Tablice a listy połączone
Tablice są najczęściej używaną strukturą danych do przechowywania kolekcji elementów. Większość języków programowania udostępnia metody umożliwiające łatwe deklarowanie tablic i uzyskiwanie dostępu do elementów w tablicach. Lista połączona, a dokładniej lista połączona pojedynczo, jest również strukturą danych, której można 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, jak tablica wyglądałaby w pamięci.
Powyższy kod definiuje tablicę, która może przechowywać 5 liczb całkowitych, a dostęp do nich uzyskuje się za pomocą indeksów od 0 do 4. Jedną z ważnych właściwości tablicy jest to, że cała tablica jest przydzielana jako pojedynczy blok pamięci, a każdy element otrzymuje własną przestrzeń w tablicy. Po zdefiniowaniu tablicy jej rozmiar jest ustalany. Więc jeśli nie masz pewności co do rozmiaru tablicy w czasie kompilacji, musisz zdefiniować wystarczająco dużą tablicę, aby była bezpieczna. Ale przez większość czasu będziemy używać mniejszej liczby elementów, niż przydzieliliśmy. Tak więc znaczna ilość pamięci jest marnowana. Z drugiej strony, jeśli „wystarczająco duża tablica” nie jest w rzeczywistości wystarczająco duża, program ulegnie awarii.
Lista połączona przydziela pamięć do swoich elementów oddzielnie we własnym bloku pamięci, a ogólną strukturę uzyskuje się przez połączenie tych elementów jako ogniw 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 listy połączonej jest przechowywany jako nagłówek listy połączonej.
Rysunek 3: Element listy połączonej
Rysunek 4 przedstawia połączoną listę z trzema elementami. Każdy element przechowuje swoje dane, a wszystkie elementy oprócz ostatniego przechowują odniesienie do następnego elementu. Ostatni element zawiera wartość null w swoim następnym polu. Dostęp do dowolnego elementu na liście można uzyskać, zaczynając od początku i podążając za następnym wskaźnikiem, aż do osiągnięcia wymaganego elementu.
Mimo że tablice i połączone listy są podobne w tym sensie, że obie są używane do przechowywania kolekcji elementów, występują w nich różnice wynikające ze strategii, których używają do przydzielania pamięci do jej elementów. Tablice alokują pamięć do wszystkich swoich elementów jako pojedynczy blok, a rozmiar tablicy należy określić 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 przydziela 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 liście połączonej nie byłyby proste w porównaniu do bezpośredniego dostępu do elementów w tablicy przy użyciu jej indeksów.
