Lista jest to liniowo uporządkowany zbiór elementów, z których dowolny element można usunąć oraz dodać w dowolnym miejscu. Pierwszy i ostatni element listy nazywamy końcami listy. Szczególnym przypadkiem listy może być stos (gdy pobrać, odczytać i wstawić element można tylko na końcu listy) lub kolejka (pobrać i odczytać element można tylko na początku listy, a dodać na końcu).
Listy mogą być posortowane (najmniejszy element jest w korzeniu). Rozważmy przypadek jednokierunkowej listy posortowanej.
Aby dodać element do listy posortowanej należy sprawdzić, w którym miejscu powienien się on znajdować. Sprawdzamy od korzenia, schodząc w dół, jeśli element, który chcemy dodać jest większy od badanego węzła i mniejszy od jego następnika, to należy umieścić go między nimi. Musimy więc ustawić wskaźnik aktualnego węzła na dodawany element, a wskaźnik tego elementu na następnik. Ponieważ jest to lista jednokierunkowa, przeszukiwanie jej należy zawsze zaczynać od korzenia. Dodając więc pierwszy element do pustej listy należy zapamiętać jego wskaźnik, by później móc się do niego przenieść.
W przeciwieństwie do stosu i kolejki listy mogą zawierać dwa wskaźniki. Takie listy nazywamy dwukierunkowymi, poruszać się możemy w niej w obydwu kierunkach, co przyspiesza wszystkie operacje. Oto schemat listy dwukierunkowej:

Komentarze