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

©2024 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ą, gdyż pozwala lepiej wykorzystać pamięć.

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
©2024 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.