Informatyka dla klas III - Listy

Listy

Rodzaje list

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ą.

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.

 

Reprezentacja list w pamięci komputera

Tworząc zmienną typu lista, tworzymy w niej trzy pola: head, tail  oraz count (obowiązkowe jest pole head, pozostałe usprawniają obsługę list, ale nie są konieczne – dla list jednokierunkowych specjalnie pominęliśmy tail  oraz count).

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.

 

Podstawowe operacje na liście jednokierunkowej

Przejście przez listę

Przechodzenie listy – ma na celu przejście kolejno przez wszystkie elementy listy, począwszy od pierwszego, a skończywszy na ostatnim. Operacja ta jest częścią składową wielu innych operacji, gdzie algorytm musi coś wyszukać na liście. W przypadku listy jednokierunkowej możemy się po niej poruszać tylko w jednym kierunku: od początku do końca. Z uwagi na sposób powiązania ze sobą elementów listy, do jej przechodzenia potrzebna jest zmienna typu wskaźnik, która będzie wskazywała na kolejne elementy. Na początku algorytmu zmienna ta powinna wskazywać pierwszy element na liście. W pętli przetwarzamy element wskazywany przez tą zmienną, po czym za nową wartość zmiennej przyjmuje się adres następnego elementu listy. Adres ten jest przechowywany w polu next  elementu bieżącego. Listę przechodzimy do momentu, aż zmienna wskazująca przyjmie wartość 0. Stanie się tak po wyjściu z ostatniego elementu listy, w którego polu next  przechowywany jest adres 0.

 

Algorytm przechodzenia przez listę jednokierunkową

Wejście
p  –  wskazanie początku listy jednokierunkowej, czyli adres pierwszego elementu na liście
Wyjście:

Przejście przez wszystkie elementy listy

Lista kroków:
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  ← (pnext) ; w p umieść zawartość pola next elementu wskazywanego przez p
K04: Zakończ  

 

Liczba elementów listy

Problem liczby elementów listy rozwiązujemy za pomocą algorytmu przejścia przez listę. Tworzymy licznik, któremu na początku nadajemy wartość 0. Następnie przechodzimy kolejno przez wszystkie elementy na liście. Przy każdym mijanym elemencie zwiększamy licznik o 1. Po przejściu całej listy w liczniku będzie liczba elementów.

 

Algorytm wyznaczania liczby elementów na liście jednokierunkowej

Wejście
p  –  wskazanie listy jednokierunkowej
Wyjście:
c  –  liczba elementów
Lista krokó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  ← (pnext) ; w p umieść zawartość pola next elementu wskazywanego przez p
K05: Zakończ zwracając c ; koniec, wynik w c

 

 

Dodawanie elementu na początku listy

obrazek

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:

obrazek

Tworzymy dynamicznie w pamięci nowy element listy (na rysunku w kolorze zielonym). Wprowadzamy do niego dane dla pola data.

obrazek

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.

obrazek

W zmiennej head  umieszczamy adres nowego elementu. Po tej operacji początkiem listy staje się nowo utworzony element.

 

Algorytm dołączania nowego elementu na początek listy jednokierunkowej

Wejście
head  –  zmienna wskazująca początek listy
v   wartość wprowadzana do elementu
Wyjście:

Lista z dołączonym na początku elementem o wartości v.

Dane pomocnicze:
p  –  wskazanie elementu listy
Lista kroków:
K01: Utwórz nowy element listy  
K02: p  ← adres nowego elementu  
K03: (pdata) ← v ; umieszczamy dane w elemencie
K04: (pnext) ← 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.

 

 

Usuwanie elementu z początku listy

obrazek

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.

obrazek

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.

obrazek

Odłączony element usuwamy z pamięci.

obrazek

Otrzymujemy listę bez pierwszego elementu.

 

Algorytm usuwania elementu z początku listy jednokierunkowej

Wejście
head  –  zmienna wskazująca początek listy
Wyjście:

Lista bez pierwszego elementu.

Dane pomocnicze:
p  –  wskazanie elementu listy
Lista kroków:
K01: p ← head ; zapamiętaj pierwszy element
K02 Jeśli p = nil, to zakończ ; zakończ, jeśli lista jest pusta
K03: head  ← (pnext) ; początkiem listy będzie element następny
K04: Usuń z pamięci element wskazany przez p  
K05: Zakończ  

 

 

Podstawowe operacje na liście dwukierunkowej

Przejście przez listę

W porównaniu z listami jednokierunkowymi, opisanymi w poprzednim rozdziale, listy dwukierunkowe są bardziej skomplikowane, ponieważ każdy ich element posiada dodatkowe pole prev. Pole to wskazuje element poprzedni na liście. Zatem listy tego typu można przechodzić w obu kierunkach. Z drugiej strony ta możliwość skraca czas wykonania wielu operacji na liście, gdzie wymagany jest element poprzedzający w stosunku do danego. W przypadku listy jednokierunkowej element ten znajdowany był za pomocą przejścia od początku listy – w liście dwukierunkowej mamy go danego bezpośrednio poprzez pole prev.

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).

 

Algorytm przechodzenia przez listę dwukierunkową

Wejście
L  –  zmienna obsługująca listę
Wyjście:

Przejście przez wszystkie elementy listy od pierwszego do ostatniego lub od ostatniego do pierwszego

Dane pomocnicze:
p  –  wskazanie elementu listy
Lista kroków : przejście w przód
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  ← (pnext) ; w p umieść zawartość pola next elementu wskazywanego przez p
K05: Zakończ  
Lista kroków : przejście wstecz
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  ← (pprev) ; w p umieść zawartość pola prev elementu wskazywanego przez p
K05: Zakończ  

 

 

Liczba elementów listy

Dla listy dwukierunkowej nie musimy posiadać osobnego algorytmy wyznaczania liczby elementów, ponieważ pole count  zmiennej obsługującej listę przechowuje bezpośrednio tę informację.

 

Dodawanie elementu na początku listy

 obrazek

Naszym zadaniem jest dodanie nowego elementu na początku listy dwukierunkowej.

obrazek

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.

obrazek

W polu next  umieszczamy adres przechowywany przez pole head. W ten sposób następnikiem nowego elementu stanie się obecny pierwszy element listy.

obrazek

W polu head  umieszczamy adres nowego elementu, który teraz staje się pierwszym elementem listy.

obrazek

Zwiększamy pole count  o 1.

obrazek

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.

obrazek

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ą.

 

Algorytm dołączania nowego elementu na początek listy dwukierunkowej

Wejście
L  –  zmienna obsługująca listę
v   wartość wprowadzana do elementu
Wyjście:

Lista z dołączonym na początku elementem o wartości v.

Dane pomocnicze:
p  –  wskazanie elementu listy
Lista kroków:
K01: Utwórz nowy element  
K02: p  ← adres nowego elementu  
K03: (pdata) ← v ; umieszczamy dane w nowym elemencie
K04: (pprev) ← nil '; pierwszy element nie posiada poprzednika
K05: (pnext) ← 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 (pnext) ≠ nil, to ((pnext)→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

obrazek

Dodawanie elementu na koniec listy jest symetryczne z dodawaniem na początek. Musi tak być, ponieważ lista dwukierunkowa jest strukturą symetryczną.

obrazek

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.

obrazek

Do pola prev  kopiujemy zawartość pola tail  ze zmiennej obsługującej listę. Poprzednikiem nowego elementu stanie się obecny ostatni element listy.

obrazek

W polu tail  umieszczamy adres nowego elementu. Nowy element staje się ostatnim elementem listy

obrazek

Zwiększamy o 1 zawartość pola count.

obrazek

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ść.

obrazek

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.

 

Algorytm dołączania nowego elementu do końca listy dwukierunkowej

Wejście
L  –  zmienna obsługująca listę
v   wartość wprowadzana do elementu
Wyjście:

Lista z dołączonym na końcu nowym elementem o wartości v

Dane pomocnicze:
p  –  wskazanie elementu listy
Lista kroków:
K01: Utwórz nowy element  
K02: p ← adres nowego elementu  
K03: (pdata) ← v ; umieszczamy dane w nowym elemencie
K04: (pnext) ← nil ; ostatni element nie będzie posiadał następnika
K05; (pprev) ← 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 (pprev) ≠ nil, to ((pprev)→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  

 

 

Dodawanie nowego elementu przed wybranym elementem listy

obrazek

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.

obrazek

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.

obrazek

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).

obrazek

Zwiększamy o 1 licznik elementów count  w zmiennej obsługującej listę.

obrazek

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.

 

Algorytm dołączania nowego elementu przed wybranym elementem listy dwukierunkowej

Wejście
L  –  zmienna obsługująca listę
e  – wskazanie elementu listy, przed którym ma zostać wstawiony nowy element
v  – dane dla nowego elementu
Wyjście:

Lista z nowym elementem wstawionym przed element wskazywany przez e.

Dane pomocnicze:
p  –  wskazania elementu listy
Lista kroków:
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: (pdata) ← v ; umieszczamy dane w nowym elemencie
K07: (pnext) ← e ; następnikiem będzie element wybrany
K08: (pprev) ← (eprev) ; poprzednikiem będzie poprzednik elementu wybranego
K09: L.count  ← L.count  + 1 ; zwiększamy licznik elementów listy
K10: ((eprev)→next) ← p ; następnikiem poprzednika elementu wybranego będzie nowy element
K11: (eprev) ← p ; poprzednikiem elementu wybranego będzie nowy element
K12: Zakończ  

 

 

Dodawanie nowego elementu za elementem wybranym

obrazek

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.

obrazek

Załóżmy, że wybrany element nie jest ostatni na liście. Wtedy posiada następnik (na rysunku w kolorze żółtym).

obrazek

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.

obrazek

Zwiększamy licznik elementów count  o 1.

obrazek

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.

 

Algorytm dołączania nowego elementu za wybranym elementem listy dwukierunkowej

Wejście
L  –  zmienna obsługująca listę
e  – wskazanie elementu listy, za którym ma zostać wstawiony nowy element
v  – dane dla nowego elementu
Wyjście:

Lista z nowym elementem wstawionym za elementem wskazywanym przez e.

Dane pomocnicze:
p  –  wskazania elementu listy
Lista kroków:
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: (pdata) ← v ; umieszczamy dane w nowym elemencie
K07: (pnext) ← (enext) ; następnikiem będzie następnik elementu wybranego
K08: (pprev) ← e ; poprzednikiem będzie element wybrany
K09: L.count  ← L.count  + 1 ; zwiększamy licznik elementów
K10: ((pnext)→prev) ← p ; ustawiamy p jako poprzednik następnika
K11: (enext) ← p ; ustawiamy p jako następnik elementu wybranego
K12: Zakończ  

 

 

Usuwanie wybranego elementu listy

obrazek

obrazek

obrazek

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.

obrazek

obrazek

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.

obrazek

obrazek

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

obrazek

Usuwamy element wybrany z pamięci.

 

Algorytm usuwania wybranego elementu listy dwukierunkowej

Wejście
L  –  zmienna obsługująca listę
e  – wskazanie elementu listy do usunięcia
Wyjście:

Lista bez elementu wskazywanego przez e.

Lista kroków:
K01: L.count  ← L.count  - 1 ; zmniejszamy licznik elementów listy
K02: Jeśli (eprev) ≠ nil, to ((eprev)→next) ← (enext)
inaczej L.head  ← (enext)
; następnikiem poprzednika będzie następnik usuwanego elementu
; jeśli poprzednika nie ma, modyfikujemy head
K03: Jeśli (enext) ≠ nil, to ((enext)→prev) ← (eprev)
inaczej L.tail  ← (eprev)
; poprzednikiem następnika będzie poprzednik usuwanego elementu
; jeśli następnika nie ma, to modyfikujemy tail
K04: Usuń element e  
K05: Zakończ  

 

 

Usuwanie elementu z początku listy

Nie musimy tworzyć osobnego algorytmu, wykorzystamy algorytm usuwania wybranego elementu listy.

 

Algorytm usuwania elementu z początku listy dwukierunkowej

Wejście
L  –  zmienna obsługująca listę
Wyjście:

Lista bez pierwszego elementu.

Lista kroków:
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

 

 

Usuwanie elementu z końca listy

Tutaj również wykorzystujemy algorytm ogólny.

 

Algorytm usuwania elementu z końca listy dwukierunkowej

Wejście
L  –  zmienna obsługująca listę
Wyjście:

Lista bez ostatniego elementu.

Lista kroków:
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   
im. Kazimierza Brodzińskiego
w Tarnowie

©2024 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

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