Klasa II 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):

next – wskazuje kolejny element, (ang. next – następny)
prev – wskazuje poprzedni element (ang. prev od słówka previous – poprzedni)

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:

wskaźnik head – wskazuje pierwszy element listy (ang. head = głowa)
wskaźnik tail – wskazuje ostatni element listy (ang. tail = ogon)
licznik count – zlicza elementy na liście

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.

Operacje na listach jednokierunkowych

Typ elementu listy

struct slistEl
{
  slistEl * next;
  typ_danych data;
};

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

–

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 ≠ NULL, 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

Liczba elementów listy: l_size

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

–

wskazanie listy jednokierunkowej

Wyjście:

–

liczba elementów

Lista kroków:

K01:	c ← 0	; zerujemy licznik
K02:	Dopóki p ≠ NULL, 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 z wynikiem c	; koniec, wynik w c

Dodawanie elementu na początku listy: l_push_front

	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 zielonym). Wprowadzamy do niego dane dla pola data.
	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.

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:

–

wskazanie elementu listy

Lista kroków:

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.

Usuwanie elementu z początku listy: l_pop_front

	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.

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:

–

wskazanie elementu listy

Lista kroków:

K01:	p ← head	; zapamiętaj pierwszy element
K02	Jeśli p = NULL, 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

Dla prostych zastosowań podane powyżej operacje dla list jednokierunkowych zwykle wystarczają. W dalszej części artykułu rozszerzamy tę listę o kolejne operacje.

Operacje na listach dwukierunkowych

Typ elementu listy oraz zmiennej obsługującej listę

struct dlistEl
{
  dlistEl * next, * prev;
  typ_danych data;
};

struct dlistVar
{
  dlistEl * head, * tail;
  unsigned count;
};

Przejście przez listę

W porównaniu z listami jednokierunkowymi 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

–

zmienna obsługująca listę

Wyjście:

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

Dane pomocnicze:

–

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 ≠ NULL, 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

Lista kroków : przejście wstecz

K01:	p ← L.tail	; w p ustawiamy adres ostatniego elementu listy
K02:	Dopóki p ≠ NULL, 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

Liczba elementów listy: l_size

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: l_push_front

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

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:

–

wskazanie elementu listy

Lista kroków:

K01:	Utwórz nowy element
K02:	p ← adres nowego elementu
K03:	(p→data) ← v	; umieszczamy dane w nowym elemencie
K04:	(p→prev) ← NULL	'; 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) ≠ NULL, 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: l_push_back

	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.

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:

–

wskazanie elementu listy

Lista kroków:

K01:	Utwórz nowy element
K02:	p ← adres nowego elementu
K03:	(p→data) ← v	; umieszczamy dane w nowym elemencie
K04:	(p→next) ← NULL	; 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) ≠ NULL, 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

Dodawanie nowego elementu przed wybranym elementem listy: l_insert_before

	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.

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:

–

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:	(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

Dodawanie nowego elementu za elementem wybranym: l_insert_after

	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.

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:

–

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:	(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

Usuwanie wybranego elementu listy: l_remove

	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.

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 (e→prev) ≠ NULL, 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) ≠ NULL, 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

Usuwanie elementu z początku listy: l_pop_front

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

Algorytm usuwania elementu z początku listy dwukierunkowej

Wejście

–

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: l_pop_back

Tutaj również wykorzystujemy algorytm ogólny.

Algorytm usuwania elementu z końca listy dwukierunkowej

Wejście

–

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

Informatyka dla klas II

Listy

Rodzaje list

Reprezentacja list w pamięci komputera

Operacje na listach jednokierunkowych

Typ elementu listy

Przejście przez listę

Algorytm przechodzenia przez listę jednokierunkową

Wejście

Wyjście:

Liczba elementów listy: l_size

Algorytm wyznaczania liczby elementów na liście jednokierunkowej

Wejście

Wyjście:

Dodawanie elementu na początku listy: l_push_front

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

Wejście

Wyjście:

Dane pomocnicze:

Usuwanie elementu z początku listy: l_pop_front

Algorytm usuwania elementu z początku listy jednokierunkowej

Wejście

Wyjście:

Dane pomocnicze:

Operacje na listach dwukierunkowych

Typ elementu listy oraz zmiennej obsługującej listę

Przejście przez listę

Algorytm przechodzenia przez listę dwukierunkową

Wejście

Wyjście:

Dane pomocnicze:

Lista kroków : przejście w przód

Lista kroków : przejście wstecz

Liczba elementów listy: l_size

Dodawanie elementu na początku listy: l_push_front

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

Wejście

Wyjście:

Dane pomocnicze:

Dodawanie elementu na koniec listy: l_push_back

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

Wejście

Wyjście:

Dane pomocnicze:

Dodawanie nowego elementu przed wybranym elementem listy: l_insert_before

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

Wejście

Wyjście:

Dane pomocnicze:

Dodawanie nowego elementu za elementem wybranym: l_insert_after

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

Wejście

Wyjście:

Dane pomocnicze:

Usuwanie wybranego elementu listy: l_remove

Algorytm usuwania wybranego elementu listy dwukierunkowej

Wejście

Wyjście:

Usuwanie elementu z początku listy: l_pop_front

Algorytm usuwania elementu z początku listy dwukierunkowej

Wejście

Wyjście:

Usuwanie elementu z końca listy: l_pop_back

Algorytm usuwania elementu z końca listy dwukierunkowej

Wejście

Wyjście: