Informacje ogólne.

Lista - skończony ciąg elementów:

	-	lewy koniec listy
	-	prawy koniec listy
	-	długość (rozmiar) listy
	-	lista pusta

Przykładowe listy:

	gdzie

Podstawowymi abstrakcyjnymi operacjami na listach q i r są:

dostęp do elementu listy
podlista
złożenie

Za pomocą tych trzech operacji można definiować inne operacje na listach, na przykład:

wstawienie elementu za element na liście :

Listy używa się zwykle w specjalny sposób, ograniczając się do zmian jej końców:

1	front(q)	=		pobieranie lewego końca listy
2	push(q,x)	=		wstawienie elementu na lewy koniec listy
3	pop(q)	=		usunięcie bieżącego lewego końca listy
4	rear(q)	=		pobieranie prawego końca listy
5	inject(q,x)	=		wstawienie elementu na prawy koniec listy
6	eject(q)	=		usunięcie bieżącego prawego końca listy

Listę, na której można wykonać wszystkie sześć operacji, nazywa się kolejką podwójną.

W szczególnych przypadkach, tzn.

kiedy uwzględnia się tylko operacje front, push i pop, nazywa się ją stosem (bufor LIFO - Last In, First Out),

kiedy uwzględnia się tylko operacje front, pop, inject - kolejką (bufor FIFO First In, First Out).

	front(q)	push(q,x)	pop(q)	rear(q)	inject(q,x)	eject(q)
Lista podwójna	+	+	+	+	+	+
Stos (LIFO)	+	+	+
Kolejka (FIFO)	+		+		+

Reprezentacje listy.

Reprezentacje listy
to:

Tablicowa:

gdzie

Jak wskazuje nazwa, lista zaimplementowana w ten sposób opiera się na tablicy obiektów (lub rekordów) danego typu.

Dopisanie elementu	Usunięcie elementu
to wstawienie elementu do tablicy: jeśli ma ono nastąpić na końcu listy, będzie to kolejny element w tablicy; jeśli nowy element ma znaleźć się między innymi elementami, należy przesunąć o jedno pole w prawo wszystkie elementy o indeksie wyższym niż pole, na które będzie wstawiany obiekt; następnie w powstałą lukę wpisuje się nowy element.	Jeżeli za indeks elementu przyjmiemy i-ty element tablicy jest to przesunięcie o jedno pole w lewo wszystkich elementów o indeksie większym od i.

Zalety	Wady
prosta nawigacja wewnątrz listy, korzystanie z gotowej struktury tablicy, szybki dostęp do elementu o konkretnym numerze, większa odporność na błędy.	niska elastyczność (szczególnie dotycząca rozmiaru tablicy), liniowa złożoność operacji wstawiania i usuwania

Implementację tablicową stosuje się tam, gdzie elastyczność nie odgrywa istotnej roli, a wymagana jest szybka i prosta nawigacja.

Dowiązaniowa /wskaźnikowa:

W tej implementacji każdy obiekt na liście musi zawierać dodatkowy element: wskaźnik do innego obiektu tego typu.

Dopisanie elementu (dla prostej listy jednokierunkowej)

Usunięcie elementu

jeśli ma ono nastąpić na końcu listy, to wskaźnik wiążący w obiekcie ostatnim ustawia się na nowy obiekt danego typu; jeśli ma ono nastąpić wewnątrz listy, to najpierw tworzy się nowy obiekt danego typu i jego wskaźnik wiążący ustawia się na następnik elementu, za którym ma być wstawiany. Później wskaźnik poprzednika przestawia się na ten nowy obiekt. W tym przypadku bardzo ważna jest kolejność, której zachwianie jest częstą przyczyną błędów. Np. można najpierw przestawić wskaźnik poprzednika na nowy obiekt, co spowoduje bezpowrotną utratę dostępu do dalszych elementów listy, na które już nie będzie pokazywał żaden wskaźnik. Ustawienie wskaźnika nowego elementu na następnik nie będzie możliwe, bo nie będzie znany jego adres.

jest odwrotne do wstawiania: w pewnym miejscu zapisuje się wskaźnik do usuwanego elementu (aby nie "zgubić" jego adresu), następnie wskaźnik wiążący poprzednika przestawia się na następnik. Dopiero w tym momencie zwalnia się pamięć po obiekcie usuwanym (do tego potrzebny jest ten wskaźnik tymczasowy).

Zalety	Wady
duża elastyczność (ilość potrzebnej pamięci), stała złożoność operacji wstawiania i usuwania	dość skomplikowana nawigacja wewnątrz listy, długi dostęp do elementu poprzedniego, końcowego dla dużych list, mała odporność na błędy (naruszanie struktury listy przy używaniu tych samych wskaźników wewnątrz i na zewnątrz funkcji list).

	liniowa	cykliczna
Pojedyncza (jednokierunkowa)
Podwójna (dwukierunkowa)

---