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źnikwskaź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

  Ilustracja przedstawia kwadrat podzielony na trzy części.
  lewy górny róg: prev, środek: klucz, prawy dolny róg: next.
  Od części prev wychodzi strzałka skierowana w lewą stronę a od części next w prawą stronę.

  

• listy jednokierunkowej.

  R1XmvFcTQW94w

  Ilustracja przedstawia kwadrat podzielony na dwie części.
  środek: klucz, prawy dolny róg: next.
  Od części next wychodzi strzałka skierowana w prawą stronę.

  

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

  Ilustracja przedstawia sześć opisanych bloków w kształcie kwadratu.
  Kwadrat pierwszy: head, wychodzi od niego strzałka skierowana w prawą stronę.
  Kwadrat drugi podzielony na trzy części lewa górna: prev, środkowa z wartością: 90, prawa dolna: next.
  Z prev wychodzi strzałka skierowana w lewą stronę na napis: NIL, od next wychodzi strzałka skierowana na następny blok po prawej stronie.
  Kwadrat trzeci podzielony na trzy części lewa górna: prev, środkowa z wartością: 12, prawa dolna: next.
  Z prev wychodzi strzałka skierowana w lewą stronę na poprzedni blok, od next wychodzi strzałka skierowana na następny blok po prawej stronie.
  Kwadrat czwarty podzielony na trzy części lewa górna: prev, środkowa z wartością: 1, prawa dolna: next.
  Z prev wychodzi strzałka skierowana w lewą stronę na poprzedni blok, od next wychodzi strzałka skierowana na następny blok po prawej stronie.
  Kwadrat piąty podzielony na trzy części lewa górna: prev, środkowa z wartością: 22, prawa dolna: next.
  Z prev wychodzi strzałka skierowana w lewą stronę na poprzedni blok, od next wychodzi strzałka skierowana na napis NIL po prawej stronie.
  Na końcu znajduje się ostatni kwadrat podpisany jako: tail zawierający napis: next.
  Wychodzi od niego strzałka wskazująca na poprzedni blok.

  

• 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

  Ilustracja przedstawia pięć opisanych bloków w kształcie kwadratu.
  Kwadrat pierwszy: head, wychodzi od niego strzałka skierowana w prawą stronę.
  Kwadrat drugi podzielony na dwie części: środkowa z wartością: 90, prawa dolna: next Od next wychodzi strzałka skierowana na następny blok po prawej stronie.
  Kwadrat trzeci podzielony na dwie części: środkowa z wartością: 12, prawa dolna: next. Od next wychodzi strzałka skierowana na następny blok po prawej stronie.
  Kwadrat czwarty podzielony na dwie części: środkowa z wartością: 1, prawa dolna: next. Od next wychodzi strzałka skierowana na następny blok po prawej stronie.
  Kwadrat piąty podzielony na dwie części: środkowa z wartością: 22, prawa dolna: next.

  

• 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

  Ilustracja przedstawia cztery opisane bloki w kształcie kwadratu.
  Kwadrat pierwszy podzielony na trzy części lewa górna: prev, środkowa z wartością: 90, prawa dolna: next.
  Z prev wychodzi strzałka wskazująca czwarty kwadrat, od next wychodzi strzałka skierowana na następny blok po prawej stronie.
  Kwadrat drugi podzielony na trzy części lewa górna: prev, środkowa z wartością: 12, prawa dolna: next.
  Z prev wychodzi strzałka skierowana w lewą stronę na poprzedni blok, od next wychodzi strzałka skierowana na następny blok po prawej stronie.
  Kwadrat trzeci podzielony na trzy części lewa górna: prev, środkowa z wartością: 1, prawa dolna: next.
  Z prev wychodzi strzałka skierowana w lewą stronę na poprzedni blok, od next wychodzi strzałka skierowana na następny blok po prawej stronie.
  Kwadrat czwarty podzielony na trzy części lewa górna: prev, środkowa z wartością: 22, prawa dolna: next.
  Z prev wychodzi strzałka skierowana w lewą stronę na poprzedni blok, od next wychodzi strzałka wskazująca na pierwszy blok.

  

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