Przeczytaj
Listy: podstawowe informacje
Lista jest strukturą danych zbudowaną z elementów tego samego typu, w której elementy są ułożone w porządku liniowym. W tym e‑materiale omówimy dwa rodzaje list: jednokierunkowe oraz dwukierunkowe.
Lista to dynamiczna struktura danych, dlatego pamięć na bieżąco jest przydzielana jej nowym elementom. Pozwala to na budowanie list o dowolnej długości, zmieniającej się w czasie działania programu.
Jak jest tworzona lista? Otóż wykorzystuje się przy tym wskaźnikiwskaźniki. Każdy element listy jednokierunkowej poza polem przechowującym klucz zawiera pole wskazujące na następny element listy (next). Element listy dwukierunkowej zawiera dodatkowo wskaźnik do elementu poprzedniego (prev).
Elementy należące do listy nie muszą zajmować ciągłego obszaru w pamięci – mogą być rozmieszczone w różnych jej częściach. Z tego właśnie powodu są wykorzystywane wskaźniki. W przypadku gdy chcemy odwołać się do któregokolwiek elementu, musimy po kolei odczytywać wskaźniki przechowywane w elementach poprzednich.
Zamieszczone niżej rysunki pokazują schematyczną budowę elementu
listy dwukierunkowej:
RHm9pRa797hh3 Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.
Każdy element listy dwukierunkowej musi się składać co najmniej z trzech pól – key (pole zawierające klucz elementu), next oraz prev.
Dla danego elementu listy a
atrybut next[a]
wskazuje na jego następnik, prev[a]
– poprzednik.
Warto zaznaczyć, że jeśli prev[a] = NIL
, element a nie ma poprzednika – to znaczy, że jest pierwszym elementem listy; jeśli next[a] = NIL
, element nie ma następnika – jest ostatnim elementem listy.
listy jednokierunkowej.
R1XmvFcTQW94w Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.
Każdy element listy jednokierunkowej składa się z minimum dwóch pól – key (pole zawierające klucz elementu) oraz next.
Dla danego elementu a na liście atrybut next[a]
wskazuje na jego następnik.
Pamiętajmy, że jeśli next[a] = NIL
, element nie ma następnika – jest ostatnim elementem listy.
Zazwyczaj, tworząc listę, rezerwuje się w pamięci dodatkowo dwie zmienne wskaźnikowe do jej obsługi: head (głowa – wskazuje na pierwszy element listy) i tail (ogon – wskazuje na ostatni element listy).
Przyjrzyjmy się dwóm szczególnym elementom listy tak jedno-, jak i dwukierunkowej.
Gdy element nie ma poprzednika, jest on pierwszym elementem. Wskazująca na niego zmienna head po polsku jest nazywana głową listy.
Gdy element nie ma następnika, będzie on ostatnim elementem listy. Wskazująca na niego zmienna tail po polsku nazywa się ogonem listy.
Rodzaje list
Rozróżniamy następujące rodzaje list:
Lista dwukierunkowa – lista, w której możemy poruszać się w dwóch kierunkach. Każdy element zawiera co najmniej trzy pola: klucz, prev oraz next. W rezultacie elementy wskazują zarówno swoje poprzedniki, jak i następniki.
Rv4E1vBrs8xBz Lista dwukierunkowaŹródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.Lista jednokierunkowa – lista, w której możemy poruszać się po elementach tylko w jednym kierunku. Każdy element zawiera minimum dwa pola (klucz, next). W takim przypadku nie da się przejść do poprzedniego elementu.
RdvtP5P31dqww Lista jednokierunkowaŹródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.Lista cykliczna dwukierunkowa – lista, w której wskaźnik next ostatniego elementu przechowuje adres pierwszego elementu, a wskaźnik prev pierwszego elementu wskazuje ostatni element, jest listą cykliczną dwukierunkową. W jej przypadku możemy przechodzić w kółko po elementach w obu kierunkach. Natomiast w liście cyklicznej jednokierunkowej poruszamy się tylko w jedną stronę.
R1NJUfUKvAPas Lista cykliczna dwukierunkowaŹródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.
Różnice między listą a tablicą
W związku z tym, że elementy listy mogą być umieszczone w różnych miejscach pamięci, nie musimy rezerwować dla niej z góry ustalonego, ciągłego obszaru (tak jak dzieje się w przypadku tablic). W rezultacie do listy można dodawać nowe elementy.
Aby odwołać się do któregokolwiek elementu tablicy, wystarczy podać jego indeks. W przypadku list jest inaczej. Gdy chcemy odwołać się do wybranego elementu, musimy przejść kolejno przez wszystkie elementy go poprzedzające. Cecha ta jest rezultatem sekwencyjnej budowy listy, a zatem jej elementy nie są oznaczone za pomocą indeksów (tak jak w przypadku tablic), lecz odwołują się do siebie kolejno (obiekt A wskazuje obiekt B, obiekt B wskazuje obiekt C i tak dalej).
Słownik
zmienna przechowująca adres innej zmiennej
czas niezbędny do rozwiązania określonego problemu, podawany zazwyczaj w liczbach operacji podstawowych/dominujących (zależy ona od ilości danych wejściowych)