Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Podstawowe pojęcia dotyczące list

SPIS TREŚCI

Definicje

Lista ( ang. list ) jest sekwencyjną strukturą danych, która składa się z ciągu elementów tego samego typu. Dostęp do elementów listy jest sekwencyjny – tzn. z danego elementu listy możemy przejść do elementu następnego lub do poprzedniego. Dojście do elementu i-tego wymaga przejścia przez kolejne elementy od pierwszego do docelowego. Takie zachowanie się tej struktury jest konsekwencją budowy jej elementów. Oprócz samych danych każdy element listy przechowuje zwykle dwa wskaźniki – do elementu następnego listy oraz do elementu poprzedzającego na liście. Nazwijmy te wskaźniki odpowiednio ( stosujemy nazwy angielskie z powodu ich powszechności w literaturze ):

obrazek

W przeciwieństwie do tablicy elementy listy nie muszą leżeć obok siebie w pamięci. Zatem lista nie wymaga ciągłego obszaru pamięci i może być rozłożona w różnych jej segmentach – w porównaniu do tablic jest to niewątpliwie zaletą.

Inną zaletą list w stosunku do tablic jest to, iż nowe elementy można szybko dołączać w dowolnym miejscu listy, zatem lista może dynamicznie rosnąć w pamięci. Również z listy można usuwać dowolne elementy, co powoduje, iż lista kurczy się w pamięci.

Wskaźniki przechowywane w każdym elemencie pozwalają powiązać te elementy w ciąg:

obrazek

Po tak określonej liście możemy się poruszać w obu kierunkach, które wyznaczają pola next  i prev. Listę o takiej własności nazywamy listą dwukierunkową ( ang. doubly linked list ). Pierwszy element listy nie posiada poprzednika, zatem w polu prev  przechowuje wskaźnik pusty ( czyli zero – adres zero nie wskazuje żadnego elementu ). Podobnie ostatni element listy nie posiada następnika i jego pole next  zawiera wskaźnik pusty.

W niektórych zastosowaniach nie potrzebujemy przechodzić listy w obu kierunkach. W takim przypadku w każdym elemencie wystarczy jeden wskaźnik, np. next:

obrazek

Taką uproszczoną listę nazywamy listą jednokierunkową ( ang. singly linked list ).

Jeśli za następnik ostatniego elementu listy przyjmiemy pierwszy element na liście, to otrzymamy jednokierunkową listę cykliczną ( ang. singly linked cyclic list ):

obrazek

Lista cykliczna nigdy się nie kończy – przechodzimy ją cyklicznie w koło.

Jeśli dodatkowo poprzednikiem pierwszego elementu listy zrobimy ostatni element, to otrzymamy dwukierunkową listę cykliczną ( ang. doubly linked cyclic list ):

obrazek

Taką listę cykliczną możemy przechodzić w obu kierunkach.

W tablicy dostęp do wybranego elementu jest bardzo szybki, ponieważ elementy znajdują się jeden obok drugiego w ciągłym bloku pamięci ( aby obliczyć adres elementu o danym indeksie wystarczy do adresu tablicy dodać iloczyn indeksu przez rozmiar elementu ). W przypadku listy nie możemy tak postąpić, ponieważ elementy mogą znajdować się w dowolnym obszarze pamięci i niekoniecznie obok siebie. Nawet jeśli znajdują się obok siebie, to ich kolejność na liście wcale nie musi odpowiadać kolejności położenia w pamięci. W przypadku listy musimy przechodzić kolejno od jednego elementu do drugiego wzdłuż ścieżki wyznaczonej przez ich pola next  lub prev. Przy długiej liście może to być operacja czasochłonna. To z kolei jest wadą list w porównaniu z tablicami.

Tworząc listę w pamięci zwykle dodatkowo rezerwuje się trzy zmienne dla jej obsługi:

obrazek

Zmienna tego typu umożliwia dostęp do początku i do końca listy oraz zapamiętuje liczbę elementów przechowywanych na liście. Można ją stosować zarówno do list jednokierunkowych jak i dwukierunkowych. Jeśli interesuje nas jedynie dostęp do początku listy, to można pominąć składniki tail  i count. W dalszej części artykułu podajemy podstawowe algorytmy operujące na listach. Przyjęliśmy zasadę, iż listy jednokierunkowe będą maksymalnie uproszczone – do obsługi listy będzie stosowana tylko zmienna head, a listy dwukierunkowe będą posiadały wszystkie ułatwienia.

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.