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ą, gdyż pozwala lepiej wykorzystać pamięć.

Inną zaletą list w stosunku do tablic jest to, iż nowe elementy można szybko dołączać w dowolnym miejscu listy, zatem lista może dynamicznie rosnąć w pamięci. Również z listy można usuwać dowolne elementy, co powoduje, iż lista kurczy się w pamięci.

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