Lista

Przykład listy jednokierunkowej

Lista - struktura danych służąca do reprezentacji zbiorów dynamicznych, w której elementy ułożone są w liniowym porządku. Rozróżniane są dwa podstawowe rodzaje list: lista jednokierunkowa w której z każdego elementu możliwe jest przejście do jego następnika oraz lista dwukierunkowa w której z każdego elementu możliwe jest przejście do jego poprzednika i następnika.

Implementacja listy

Istnieją dwie popularne implementacje struktury listy: tablicowa i wskaźnikowa.

Wskaźnikowa

W przypadku tej implementacji każdy element listy składa się z co najmniej dwóch pól: klucza oraz pola wskazującego na następny element listy. W przypadku list dwukierunkowych każdy element listy zawiera także pole wskazujące na poprzedni element listy. Pole wskazujące poprzedni i następny element listy są najczęściej wskaźnikami.

Dopisanie elementu (dla prostej listy jednostronnej):

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

Usunięcie elementu 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 i wady tej implementacji są komplementarne w stosunku do implementacji tablicowej.

Wgłębiając się w szczegóły implementacji listy za pomocą wskaźników można wyróżnić następujące rodzaje list:

• lista jednokierunkowa - w każdym elemencie listy jest przechowywane odniesienie tylko do jednego sąsiada (następnika lub poprzednika).
  
• lista dwukierunkowa - w każdym elemencie listy jest przechowywane odniesienie zarówno do następnika jak i poprzednika elementu w liście. Taka reprezentacja umożliwia swobodne przemieszczanie się po liście w obie strony.
  
• lista cykliczna - następnikiem ostatniego elementu jest pierwszy element, a poprzednikiem pierwszego ostatni. Po liście można więc przemieszczać się cyklicznie. Nie ma w takiej liście charakterystycznego ogona (ani głowy), często rozpoznawanego po tym, że jego następnik jest pusty (NULL).
  
• lista z wartownikiem - lista z wyróżnionym elementem zwanym wartownikiem. Jest to specjalnie oznaczony element niewidoczny dla programisty wykorzystującego listę. Pusta lista zawiera wtedy tylko wartownika. Zastosowanie wartownika znacznie upraszcza implementację operacji na listach.

Powyższe cechy można prawie dowolnie łączyć, co daje możliwość stworzenia wielu różnych implementacji listy, zależnie od potrzeb.

Jednokierunkowe listy oparte na wskaźnikach są bardzo popularną podstawową strukturą danych w funkcyjnych językach programowania.

Lista dwukierunkowa z jednym wskaźnikiem

Istnieje możliwość realizacji takiej listy, wtedy gdy:

1. Wskaźnik można utożsamiać z liczbą i wykonywać na nim działania bitowe.
2. Wskaźnik pusty ma wartość liczbową 0.

Wówczas pojedynczy wskaźnik zawiera różnicę symetryczną (xor) wartości liczbowej wskaźników na poprzedni i następny element listy. Podczas przechodzenia listy pamiętany jest rzeczywisty wskaźnik uprzednio odwiedzonego elementu i dzięki własności $X \oplus (X \oplus Y) = Y$ można z zakodowanej liczby odtworzyć albo poprzedni albo następny element, w zależności od kierunku przeglądania listy. Warunek 2. gwarantuje, że wskaźniki na pierwszej i ostatniej pozycji można odkodować natychmiast.

Zaletą takiej reprezentacji jest oszczędność pamięci (jeden wskaźnik, zamiast dwóch), wadą natomiast utrudnione przeglądanie - jeśli nie rozpoczyna się od pierwszego lub ostatniego elementu, potrzeba znać co najmniej dwa wskaźniki w celu odkodowania rzeczywistych wartości.

Tablicowa

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

Dopisanie elementu do listy 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.

Usunięcie elementu znajdującego się pod danym indeksem tablicy to przesunięcie o jedno pole w lewo wszystkich elementów o indeksie wyższym.

Zalety tej implementacji: prosta nawigacja wewnątrz listy, korzystanie z gotowej struktury tablicy, szybki dostęp do elementu o konkretnym numerze, większa odporność na błędy.

Wady: 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.

Zobacz też

• lista z przeskokami
• kolejka
• stos
• tablica asocjacyjna
• krotka
• skośny system dwójkowy - umożliwiają stworzenie listy z dostępem swobodnym