Różnica między tablicami a połączonymi listami

Tablice a listy połączone

Tablice są najczęściej stosowaną strukturą danych do przechowywania kolekcji elementów. Większość języków programowania zapewnia metody łatwego deklarowania tablic i uzyskiwania dostępu do elementów w tablicach. Lista połączona, a dokładniej lista pojedynczo połączona, jest również strukturą danych, która może być używana 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 pokazuje, jak tablica wyglądałaby w pamięci.

Powyższy kod definiuje tablicę, która może przechowywać 5 liczb całkowitych i można do nich uzyskać dostęp za pomocą indeksów od 0 do 4. Jedną ważną właściwością tablicy jest to, że cała tablica jest przydzielona jako pojedynczy blok pamięci, a każdy element otrzymuje własną przestrzeń w tablicy. Po zdefiniowaniu tablicy jej rozmiar jest ustalany. Jeśli więc nie jesteś pewien wielkości tablicy w czasie kompilacji, musisz zdefiniować wystarczająco dużą tablicę, aby być po bezpiecznej stronie. Ale w większości przypadków będziemy używać mniejszej liczby elementów niż przydzieliliśmy. Tak więc marnuje się znaczną ilość pamięci. Z drugiej strony, jeśli „wystarczająco duża tablica” nie jest wystarczająco duża, program się zawiesi.

Połączona lista przydziela pamięć jej elementom osobno we własnym bloku pamięci, a ogólną strukturę uzyskuje się poprzez połą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 rzeczywiste dane przechowywane, 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.

Rysunek 3: Element połączonej listy

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 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ż osiągniesz wymagany element.

Mimo że tablice i połączone listy są podobne w tym sensie, że oba służą do przechowywania kolekcji elementów, występują różnice wynikające ze strategii, które stosują do alokacji pamięci do swoich elementów. Tablice alokują pamięć do wszystkich jej elementów jako pojedynczy blok, a rozmiar tablicy należy określić w czasie wykonywania. To sprawiłoby, że tablice byłyby nieefektywne w sytuacjach, w których nie znasz wielkości tablicy w czasie kompilacji. Ponieważ lista połączona alokuje pamięć do swoich elementów osobno, byłaby znacznie wydajniejsza w sytuacjach, w których nie znasz wielkości listy w czasie kompilacji. Deklaracja i dostęp do elementów na połączonej liście nie byłby prosty w porównaniu z tym, jak bezpośrednio uzyskujesz dostęp do elementów w tablicy za pomocą jej indeksów.