Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek, wersja1.0 |
©2013 mgr
Jerzy Wałaszek
|
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ą.
Wskaźniki przechowywane w każdym elemencie pozwalają powiązać te elementy w ciąg:
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:
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):
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):
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:
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.
Zdefiniujmy podstawowe typy danych:
struct slistEl { slistEl * next; typ_danych data; }; |
struct dlistEl { dlistEl * next, * prev; typ_danych data; }; struct dlistVar { dlistEl * head, * tail; unsigned count; }; |
Górna część tablicy określa typy dla list jednokierunkowych. Dolna część to deklaracje dla list dwukierunkowych.
slistEl | – | element listy jednokierunkowej |
dlistEl | – | element listy dwukierunkowej |
dlistVar | – | zmienna obsługująca listę dwukierunkową,
jest strukturą o trzech polach: head – wskazuje pierwszy element listy tail – wskazuje ostatni element listy count – zawiera liczbę elementów przechowywanych na liście |
Dla list jednokierunkowych nie ma potrzeby tworzenia osobnego typu dla zmiennej obsługującej listę – zmienna ta będzie przechowywać tylko adres pierwszego elementu listy. Zmienną obsługującą listę tworzymy następująco (u góry dla list jednokierunkowych z uproszczoną obsługą, u dołu dla list dwukierunkowych z pełną obsługą):
... slistEl * head; ... |
... dlistVar L; ... |
Po deklaracji zmiennej należy ją bezwzględnie zainicjować. W tym celu do wszystkich pól wpisujemy zera. Dla listy dwukierunkowej możemy stworzyć prostą procedurę inicjalizacji:
... head = NULL; ... |
void l_init(dlistVar & L) { L.head = L.tail = NULL; L.count = 0; } |
Otrzymujemy w ten sposób pustą listę (ang. empty list), czyli listę, która nie zawiera żadnego elementu. Tak zainicjowana zmienna L jest gotowa do dalszego użycia w programach.
p | – | wskazanie początku listy jednokierunkowej, czyli adres pierwszego elementu na liście |
Przejście przez wszystkie elementy listy
K01: | Dopóki p ≠ nil, wykonuj kroki K02...K03 | ; w pętli przechodzimy przez kolejne elementy listy |
K02: | Przetwarzaj element wskazywany przez p | |
K03: | p ← (p→next) | ; w p umieść zawartość pola next elementu wskazywanego przez p |
K04: | Zakończ |
p | – | wskazanie listy jednokierunkowej |
c | – | liczba elementów |
K01: | c ← 0 | ; zerujemy licznik |
K02: | Dopóki p ≠ nil, wykonuj kroki K03...K04 | ; w pętli przechodzimy przez kolejne elementy listy |
K03: | c ← c + 1 | ; zwiększ licznik |
K04: | p ← (p→next) | ; w p umieść zawartość pola next elementu wskazywanego przez p |
K05: | Zakończ zwracając c | ; koniec, wynik w c |
Załóżmy, iż mamy daną listę trójelementową. Naszym zadaniem jest dodanie nowego elementu na początku tej listy. Postępujemy wg następującego schematu: |
|
Tworzymy dynamicznie w pamięci nowy element listy
(na rysunku w kolorze |
|
W polu next nowego elementu umieszczamy adres przechowywany przez zmienną head. W ten sposób następnikiem nowego elementu stanie się obecny pierwszy element listy. |
|
W zmiennej head umieszczamy adres nowego elementu. Po tej operacji początkiem listy staje się nowo utworzony element. |
head | – | zmienna wskazująca początek listy |
v | – | wartość wprowadzana do elementu |
Lista z dołączonym na początku elementem o wartości v.
p | – | wskazanie elementu listy |
K01: | Utwórz nowy element listy | |
K02: | p ← adres nowego elementu | |
K03: | (p→data) ← v | ; umieszczamy dane w elemencie |
K04: | (p→next) ← head | ; następnikiem będzie bieżący pierwszy element listy |
K05: | head ← p | ; ustawiamy początek listy na nowy element |
K06: | Zakończ |
Uwaga:
Elementy są umieszczone na liście w kierunku odwrotnym do kolejności ich wstawiania – ostatnio wstawiony element jest pierwszym elementem listy. Taka struktura pozwala prosto realizować stos.
Jeśli lista jest pusta, to nic nie robimy. Załóżmy, że mamy daną listę, z której początku należy usunąć element zaznaczony na rysunku kolorem czerwonym. |
|
W zmiennej head umieszczamy zawartość pola next usuwanego elementu. W ten sposób początek listy rozpocznie się w następniku, a usuwany element zostanie wyłączony z listy. |
|
Odłączony element usuwamy z pamięci. |
|
Otrzymujemy listę bez pierwszego elementu. |
head | – | zmienna wskazująca początek listy |
Lista bez pierwszego elementu.
p | – | wskazanie elementu listy |
K01: | p ← head | ; zapamiętaj pierwszy element |
K02 | Jeśli p = nil, to zakończ | ; zakończ, jeśli lista jest pusta |
K03: | head ← (p→next) | ; początkiem listy będzie element następny |
K04: | Usuń z pamięci element wskazany przez p | |
K05: | Zakończ |
Zasada przechodzenia listy dwukierunkowej jest identyczna jak przy listach jednokierunkowych. Potrzebujemy wskaźnika, który będzie wskazywał poszczególne elementy listy. Wskazywany element przetwarzamy, po czym przechodzimy do następnego poprzez pole next lub do poprzedniego poprzez pole prev. Operację przejścia kontynuujemy dotąd, aż wskaźnik przyjmie wartość 0 (ostatni element listy ma w polu next wartość 0, pierwszy element listy ma w polu prev wartość 0 – zatem wyjście z ostatniego lub z pierwszego elementu poprzez next/prev skutkuje adresem zerowym).
L | – | zmienna obsługująca listę |
Przejście przez wszystkie elementy listy od pierwszego do ostatniego lub od ostatniego do pierwszego
p | – | wskazanie elementu listy |
K01: | p ← L.head | ; w p ustawiamy adres pierwszego elementu listy |
K02: | Dopóki p ≠ nil, wykonuj kroki K03...K05 | ; w pętli przechodzimy przez kolejne elementy listy |
K03: | Przetwarzaj element wskazywany przez p | |
K04: | p ← (p→next) | ; w p umieść zawartość pola next elementu wskazywanego przez p |
K05: | Zakończ |
K01: | p ← L.tail | ; w p ustawiamy adres ostatniego elementu listy |
K02: | Dopóki p ≠ nil, wykonuj kroki K03...K05 | ; w pętli przechodzimy przez kolejne elementy listy |
K03: | Przetwarzaj element wskazywany przez p | |
K04: | p ← (p→prev) | ; w p umieść zawartość pola prev elementu wskazywanego przez p |
K05: | Zakończ |
|
Naszym zadaniem jest dodanie nowego elementu na początku listy dwukierunkowej. |
Tworzymy nowy element dynamicznie w pamięci (na rysunku w kolorze zielonym), umieszczamy w nim dane, a w polu prev zapisujemy adres zerowy, ponieważ pierwszy element listy nie posiada poprzednika. |
|
W polu next umieszczamy adres przechowywany przez pole head. W ten sposób następnikiem nowego elementu stanie się obecny pierwszy element listy. |
|
W polu head umieszczamy adres nowego elementu, który teraz staje się pierwszym elementem listy. |
|
Zwiększamy pole count o 1. |
|
Teraz musimy zapewnić komunikację w drugą stronę. Jeśli istnieje następnik dodanego elementu, to w polu prev następnika umieszczamy adres nowego elementu. Pozwoli to przejść z następnika do pierwszego elementu. Lista staje się kompletna. |
|
|
Jeśli następnik nie istnieje, to dodawaliśmy element do pustej listy. W takim przypadku w polu tail należy również wprowadzić adres nowego elementu – lista stanie się listą jednoelementową. |
L | – | zmienna obsługująca listę |
v | – | wartość wprowadzana do elementu |
Lista z dołączonym na początku elementem o wartości v.
p | – | wskazanie elementu listy |
K01: | Utwórz nowy element | |
K02: | p ← adres nowego elementu | |
K03: | (p→data) ← v | ; umieszczamy dane w nowym elemencie |
K04: | (p→prev) ← nil | '; pierwszy element nie posiada poprzednika |
K05: | (p→next) ← L.head | ; następnikiem będzie obecny pierwszy element listy |
K06: | L.head ← p | ; dołączamy element do początku listy |
K07 | L.count ← L.count + 1 | ; zwiększamy licznik elementów o 1 |
K08: | Jeśli (p→next) ≠
nil, to ((p→next)→prev) ←
p inaczej L.tail ← p |
; jeśli istnieje następnik, to
jego poprzednikiem czynimy nowy element ; inaczej adres nowego elementu umieszczamy w polu tail |
K09: | Zakończ |
Dodawanie elementu na koniec listy jest symetryczne z dodawaniem na początek. Musi tak być, ponieważ lista dwukierunkowa jest strukturą symetryczną. |
|
Tworzymy dynamicznie w pamięci nowy element (oznaczony na rysunku kolorem zielonym) i umieszczamy w nim dane. W polu next wstawiamy adres zerowy – ostatni element nie posiada następnika. |
|
Do pola prev kopiujemy zawartość pola tail ze zmiennej obsługującej listę. Poprzednikiem nowego elementu stanie się obecny ostatni element listy. |
|
W polu tail umieszczamy adres nowego elementu. Nowy element staje się ostatnim elementem listy |
|
Zwiększamy o 1 zawartość pola count. |
|
Jeśli istnieje poprzednik nowego elementu (pole prev ma wartość różną od zera), to w poprzedniku ustawiamy pole next na adres nowego elementu – lista zostanie połączona w całość. |
|
Jeśli poprzednik nie istnieje, to lista była pusta, a teraz zawiera jeden element – ten dodany przez nas. W takim przypadku adres nowego elementu należy wprowadzić również do pola head. Lista stanie się jednoelementowa, a dodany element będzie zarówno pierwszym jak i ostatnim jej elementem. |
L | – | zmienna obsługująca listę |
v | – | wartość wprowadzana do elementu |
Lista z dołączonym na końcu nowym elementem o wartości v
p | – | wskazanie elementu listy |
K01: | Utwórz nowy element | |
K02: | p ← adres nowego elementu | |
K03: | (p→data) ← v | ; umieszczamy dane w nowym elemencie |
K04: | (p→next) ← nil | ; ostatni element nie będzie posiadał następnika |
K05; | (p→prev) ← L.tail | ; poprzednikiem będzie obecny ostatni element |
K06: | L.tail ← p | ; nowy element staje się ostatnim na liście |
K07: | L.count ← L.count + 1 | ; zwiększamy o 1 licznik elementów listy |
K08: | Jeśli (p→prev) ≠
nil, to ((p→prev)→next) ← p inaczej L.head ← p |
; jeśli istnieje poprzednik,
to nowy element będzie jego następnikiem ; inaczej adres nowego elementu umieszczamy w polu head |
K09: | Zakończ |
Jeśli wybrany element (na rysunku zaznaczony kolorem jasnoniebieskim) jest pierwszym elementem listy, to zadanie sprowadza się do dodania nowego elementu na początku listy, co opisaliśmy wcześniej w tym rozdziale. |
|
Załóżmy, że wybrany element nie jest pierwszym elementem listy. Musi wtedy posiadać poprzednik (na rysunku zaznaczyliśmy go kolorem żółtym). Dostęp do poprzednika mamy poprzez pole prev elementu wybranego. |
|
Tworzymy dynamicznie w pamięci nowy element (na rysunku w kolorze zielonym). Umieszczamy w nim dane, pole next ustawiamy na adres elementu wybranego, a pole prev na adres poprzednika elementu wybranego (zawartość pola prev w elemencie wybranym). |
|
Zwiększamy o 1 licznik elementów count w zmiennej obsługującej listę. |
|
Pola next w poprzedniku oraz prev w elemencie wybranym ustawiamy na adres nowego elementu. Teraz nowy element stanie się częścią składową listy i będzie umieszczony w niej przed elementem wybranym. |
L | – | zmienna obsługująca listę |
e | – | wskazanie elementu listy, przed którym ma zostać wstawiony nowy element |
v | – | dane dla nowego elementu |
Lista z nowym elementem wstawionym przed element wskazywany przez e.
p | – | wskazania elementu listy |
K01: | Jeśli e ≠ L.head, to idź do K04 | ; sprawdzamy, czy wybrany element nie jest pierwszym elementem listy |
K02: | Wstaw nowy element na początek listy | ; jeśli jest, to wykorzystujemy algorytm wstawiania na początek listy |
K03: | Zakończ | |
K04: | Utwórz nowy element | |
K05; | p ← adres nowego elementu | |
K06: | (p→data) ← v | ; umieszczamy dane w nowym elemencie |
K07: | (p→next) ← e | ; następnikiem będzie element wybrany |
K08: | (p→prev) ← (e→prev) | ; poprzednikiem będzie poprzednik elementu wybranego |
K09: | L.count ← L.count + 1 | ; zwiększamy licznik elementów listy |
K10: | ((e→prev)→next) ← p | ; następnikiem poprzednika elementu wybranego będzie nowy element |
K11: | (e→prev) ← p | ; poprzednikiem elementu wybranego będzie nowy element |
K12: | Zakończ |
Wstawianie za wybranym elementem jest symetryczne do wstawiania przed wybranym elementem. Jeśli wybrany element jest ostatnim elementem listy (w polu next ma adres zerowy), to wykorzystujemy opisany wcześniej algorytm wstawiania na koniec listy. |
|
Załóżmy, że wybrany element nie jest ostatni na liście. Wtedy posiada następnik (na rysunku w kolorze żółtym). |
|
Tworzymy nowy element (na rysunku w kolorze zielonym), wprowadzamy do niego dane, w polu next umieszczamy adres następnika z pola next elementu wybranego, a w polu prev umieszczamy adres elementu wybranego. |
|
Zwiększamy licznik elementów count o 1. |
|
Adres nowego elementu umieszczamy w polach prev następnika oraz next elementu wybranego. Nowy element stanie się częścią listy i będzie umieszczony w niej za elementem wybranym. |
L | – | zmienna obsługująca listę |
e | – | wskazanie elementu listy, za którym ma zostać wstawiony nowy element |
v | – | dane dla nowego elementu |
Lista z nowym elementem wstawionym za elementem wskazywanym przez e.
p | – | wskazania elementu listy |
K01: | Jeśli e ≠ L.tail, to idź do K04 | ; sprawdzamy, czy e nie jest ostatnim elementem listy |
K02: | Wstaw nowy element na koniec listy | ; jeśli jest ostatnim elementem listy, wykorzystujemy algorytm wstawiania na koniec listy |
K03: | Zakończ | |
K04: | Utwórz nowy element | |
K05; | p ← adres nowego elementu | |
K06: | (p→data) ← v | ; umieszczamy dane w nowym elemencie |
K07: | (p→next) ← (e→next) | ; następnikiem będzie następnik elementu wybranego |
K08: | (p→prev) ← e | ; poprzednikiem będzie element wybrany |
K09: | L.count ← L.count + 1 | ; zwiększamy licznik elementów |
K10: | ((p→next)→prev) ← p | ; ustawiamy p jako poprzednik następnika |
K11: | (e→next) ← p | ; ustawiamy p jako następnik elementu wybranego |
K12: | Zakończ |
|
Zmniejszamy o 1 pole count. Usuwany element oznaczyliśmy kolorem czerwonym na rysunku. Element ten może znajdować się na początku listy, gdzieś w środku lub na jej końcu. Nasz algorytm sprawdzi każdą z tych trzech możliwości. |
|
Jeśli istnieje poprzednik usuwanego elementu (kolor żółty), to w jego polu next umieszczamy zawartość pola next usuwanego elementu, czyli adres następnika. W przeciwnym razie wybrany element jest pierwszym elementem listy. W takim przypadku w head umieszczamy zawartość pola next usuwanego elementu, czyli adres następnika. Zwróć uwagę, że w przypadku listy jednoelementowej do pola head trafi adres zerowy. |
|
Jeśli istnieje następnik usuwanego elementu (kolor zielony), to w jego polu prev umieszczamy zawartość pola prev usuwanego elementu, czyli adres poprzednika. W przeciwnym razie wybrany element jest ostatnim elementem listy. W polu tail umieszczamy zawartość pola prev. Zwróć uwagę, że w przypadku listy jednoelementowej do pola tail trafi adres zerowy. W obu przypadkach usuwany element staje się odłączony od listy |
Usuwamy element wybrany z pamięci. |
L | – | zmienna obsługująca listę |
e | – | wskazanie elementu listy do usunięcia |
Lista bez elementu wskazywanego przez e.
K01: | L.count ← L.count - 1 | ; zmniejszamy licznik elementów listy |
K02: | Jeśli (e→prev) ≠
nil, to ((e→prev)→next) ← (e→next) inaczej L.head ← (e→next) |
; następnikiem poprzednika
będzie następnik usuwanego elementu ; jeśli poprzednika nie ma, modyfikujemy head |
K03: | Jeśli (e→next) ≠
nil, to ((e→next)→prev) ← (e→prev) inaczej L.tail ← (e→prev) |
; poprzednikiem następnika
będzie poprzednik usuwanego elementu ; jeśli następnika nie ma, to modyfikujemy tail |
K04: | Usuń element e | |
K05: | Zakończ |
L | – | zmienna obsługująca listę |
Lista bez pierwszego elementu.
K01: | Jeśli L.count = 0, to zakończ | ; lista jest pusta i nie ma co usuwać |
K02 | Usuń z listy element wskazywany przez L.head | |
K03: | Zakończ | ; jeśli lista zawiera więcej niż 1 element, przejdź dalej |
L | – | zmienna obsługująca listę |
Lista bez ostatniego elementu.
K01: | Jeśli L.count = 0, to zakończ | ; lista jest pusta i nie ma co usuwać |
K02 | Usuń element wskazywany przez L.tail | |
K03: | Zakończ |
I Liceum Ogólnokształcące |
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe