<p>Lista jest strukturą „zewnętrznie” podobną do tablicy. Zarówno tablice jak i listy, pozwalają na dodawanie i usuwanie oraz dostęp do poszczególnego elementu i oczywiście przechodzenie przez całą kolekcję. Przede wszystkim to co zwraca uwagę i sprawia, że tablica i lista mogą być używane zamiennie to liniowy porządek ułożenia elementów. Liniowy to znaczy, że dany element jeżeli nie jest pierwszym, lub ostatnim, ma jednego i tylko jednego bezpośredniego poprzednika, oraz następcę.</p>
<h2>Krótka charakterystyka</h2>
<p>Lista w przeciwieństwie do tablicy, nie jest ograniczona liczbą elementów – z racji swojej budowy(o której za chwilę) – nie ma problemu by usunąć lub dodać element do listy (w każdym miejscu). Elementy muszą oczywiście być tego samego typu. Jeżeli chodzi o dostęp do elementu to podobnie jak w przypadku tablicy można odwołać się do niego poprzez index, jednak nie jest to tak naturalna operacja jak w przypadku listy( o tym również za chwilę :)).</p>
<p><b>Węzeł:</b></p>
<p>W przypadku tablicy podstawową jednostką w pamięci jest „komórka” o określonej wielkości. W przypadku list będzie to węzeł(node). W tym miejscu warto się na chwilę zatrzymać, ponieważ węzły są podstawowymi „budulcami” wielu struktur danych (drzewa, grafy), choć oczywiście w każdej strukturze wyglądają one nieco inaczej. Mimo delikatnych różnic zawsze pełnią dwie funkcje: Dostarczają mechanizm przechowujący dane, oraz dostarczają informacji o połączeniu z innym węzłem. W przypadku listy węzeł składa się z dwóch części: właściwej zawartości (czyli tego co przechowujemy), oraz pewnego (zależnego od języka implementacji) wskaźnika (lub wskaźników, zależnie od wariantu listy), który mówi gdzie znajduje się element będący następnikiem (lub poprzednikiem) obecnego. Oprócz tego, w zależności od implementacji węzeł może np. nieść informację o tym czy jest pierwszy, ostatni itp.</p>
<p><b>Budowa listy:</b></p>
<p><b></b>Tak więc jak można się domyślić, lista jest po prostu łańcuchem węzłów. Wyróżniamy listy jednokierunkowe – takie w których węzeł posiada wskaźnik do swojego następcy – i listy dwukierunkowe – gdzie każdy węzeł oprócz informacji o następcy, posiada też wskaźnik do poprzednika. Są też pewne wariacje na temat list, ale wszystkie po prostu w pewien sposób modyfikują informacje niesione przez węzły. </p>
<p><b>Podstawowe operacje:</b></p>
<p> <b>• Dodawanie/usuwanie elementu: </b>Jest to operacja szybsza (O(c)) niż w przypadku tablicy, ponieważ wystarczy jedynie zmienić adres w węźle poprzednim (i w następnym w przypadku listy dwukierunkowej). Myślę że poniższa „grafika” to obrazuje. </p>
<p><b> • Dostęp do elementu:</b> W tym wypadku lista przegrywa rywalizację z tablicą (O(c) do O(n)). Główną przyczyną jest fakt, że listy jako takie nie są indeksowane. Trudniej jest dostać się do elementu, bo wymaga to przeszukiwania kolekcji </p>