Zanim opisze listę dwukierunkową to zacznę od listy jednokierunkowej

**Lista jednokierunkowa** jest zbudowana tak: mamy wskaźnik do pierwszego elementu, a każdy element oprócz swojej wartości przechowuje wskaźnik do następnego elementu. Ostatni element ma wskaźnik do następnego ustawiony na 0 (adres pusty).

{{:algorytmy_i_struktury_danych:lista1.gif|
}}

**Jak działa lista?**

Mając wskaźnik do pierwszego elementu i odczytując wskaźniki do kolejnych można przejść wszystkie elementy list. Gorzej, jeśli potrzebne byłoby dostać się do konkretnego elementu, np. piątego. W przeciwieństwie do wektorów, tutaj trzeba przejść przez wszystkie poprzednie (pierwszy, drugi, trzeci, czwarty) odczytując wskaźniki do następnych. Indeksowanie listy ma więc złożoność liniową - rzędu O(n).

Ale lista ma też zalety. Bardzo proste jest wstawianie nowego elementu w konkretne miejsce. Wystarczy odpowiednio powiązać wskaźniki z poprzednim i następnym. Nie trzeba przepisywać żadnych elementów, jak to było w wektorze. Osobnymi blokami pamięci rezerwowanymi dla pojedynczych elementów zarządza sam system.

{{:algorytmy_i_struktury_danych:lista2.gif|:algorytmy_i_struktury_danych:lista2.gif}}

Usuwanie elementów jest równie proste. Wystarczy usunąć z pamięci dany element, a wskaźnik w poprzednim ustawić na następny.

{{:algorytmy_i_struktury_danych:lista3.gif|:algorytmy_i_struktury_danych:lista3.gif}}

W ramach podsumowania 2 istotne punkty o listach jednokierunkowych:
  * Nie ma dostępu swobodnego - elementy trzeba przechodzić po kolei.
  * Wstawianie i usuwanie elementów jest bardzo proste i szybkie.

**Lista dwukierunkowa** - to taka lista, w której przechowujemy wskaźnik na pierwszy i ostatni element, a każdy element przechowuje wskaźnik na poprzedni i następny. Taką listę można przechodzić w obydwie strony. Dodawanie i usuwanie elementów jest analogiczne jak w liście jednokierunkowej, trzeba tylko pamiętać nie o jednym, a o dwóch wskaźnikach, które trzeba odpowiednio uzupełnić przy tych operacjach.

{{:algorytmy_i_struktury_danych:lista4.gif|:algorytmy_i_struktury_danych:lista4.gif}}

Myślę, że w ramach powtórki to wystarczy - jeśli nie to pisać ;)

/*

tak na marginesie to wyczytałem, że istnieje jeszcze kilka innych list:

**Lista z wartownikiem** to taka lista, do której dołączamy poszukiwany element. Dzięki temu podczas przeszukiwania nie musimy sprawdzać dwóch warunków - czy element odnaleziono i czy osiągnięto koniec listy - tylko ten pierwszy. Potem wystarczy sprawdzić: jeśli odnaleziony element to wartownik, to znaczy, że we właściwej kolekcji szukanego elementu nie było.

**Lista cykliczna** to taka lista, w której ostatni element nie pokazuje na adres pusty (0), tylko na pierwszy i tak powstaje zamknięty obieg.

**Lista wielowątkowa** to lista, której elementy mają po kilka wskaźników na następny element. Każdy z nich tworzy osobną listę i dzięki temu te same elementy mogą być w różnych listach umieszczone w różnej kolejności, np. posortowane wg różnych kryteriów.

*/

Szczególnym przypadkiem listy może być [[http://www.algorytm.org/index.php?option=com_content&task=view&id=67&Itemid=45|KOLEJKA]] lub [[http://www.algorytm.org/index.php?option=com_content&task=view&id=41&Itemid=45|STOS]]


[[http://oen.dydaktyka.agh.edu.pl/dydaktyka/informatyka/c_algorytmy_i_str_danych/index.php?go=lista|Inne źródło informacji o listach (1)]]

[[http://www.algorytm.org/index.php?option=com_content&task=view&id=109&Itemid=54|Inne źródło informacji o listach (2)]]