Listy jako struktura danych

Naszą podróż po kolekcjach w Javie zaczniemy od Klas implementujących interfejs List czyli od list.

Czym są listy?

Listy są liniowymi strukturami danych o dynamicznym rozmiarze co oznacza, że mogą zmieniać swój rozmiar w czasie działania programu (w przeciwieństwie do tablic). Najważniejszymi pojęciami, które należy znać są:

  • głowa (ang. head) – początek listy,
  • następny węzeł (ang. next node) – następny element listy,
  • poprzedni węzeł (ang. prev node) – poprzedni element listy.

W zależności od tego czy lista jest jednokierunkowa czy dwukierunkowa, ostatni element jest opcjonalny.

Struktura list

Listę możemy wyobrazić sobie jako pudełka, które przechowują dane oraz informacje, gdzie znajduje się kolejny element i ewentualnie poprzedni.  Informacje o kolejnym elemencie są konieczne gdyż ze względu na sposób implementacji kolejne elementy nie muszą być ułożone obok siebie w pamięci, a mogą znajdować się w dowolnym innym miejscu pamięci operacyjnej.

Odczyt z pamięci z dowolnego bloku jest taki sam w porównaniu do dysków twardych (magnetycznych) jednakże ze względu na taktyki stosowane przez procesor, a mianowicie lokalność przestrzenną odczyt może być wolniejszy niż w przypadku ułożenia elementów obok siebie.

Lokalność przestrzenna to taktyka polegająca na załadowaniu z góry kolejnego elementu z pamięci, gdyż „może się przydać”.

Tę cechę wykorzystuje jedna z implementacji interfejsu List czyli klasa ArrayList. Jak sama nazwa wskazuje jest to implementacja listy przy pomocy tablicy i dzięki temu odczyt jest bardzo szybki. Inne podejście jest wykorzystywane w klasie LinkedList, w której elementy znajdują się tam, gdzie miejsce znajdzie kompilator. Jej zaletą jest szybsze wstawianie elementów w środku kolekcji.

Lista jednokierunkowa

Poniżej pokażemy jak wygląda połączenie takich „pudełek”, aby oddać istotę listy. Interfejs List nie gwarantuje, że elementy będą umieszczone obok siebie w pamięci. Każdy element w zależności od typu zna położenie kolejnego elementu (z wyjątkiem ogona listy jednokierunkowej).

Kluczowym elementem jest głowa, która znajduje się po lewej stronie obrazka. Referencję do niej można przechowywać w prywatnym polu klasy, co powinno ułatwić zadanie, aby zachować integralność danych. Przy opracowywaniu algorytmów ważnym zadaniem programisty jest pilnowanie, aby nie stracić referencji do głowy listy.

Lista jednokierunkowa

Budowa listy jednokierunkowej

Węzły są obiektami, które posiadają miejsce na dane oraz wskazanie na następny element. Ostatni pokazuje na specjalną wartość null.

Lista dwukierunkowa

Lista dwukierunkowa

Budowa listy dwukierunkowej.

Taka lista oprócz wskazania na następny element dodatkowo pokazuje poprzedni. Głowa przy wskazaniu na poprzedni element ma ustawioną wartość null.

Algorytmy na listach jednokierunkowych w Javie

Odczyt z listy jednokierunkowej

Pobranie wartości z listy możemy podzielić na dwa etapy. Pierwszy z nich to znalezienie odpowiedniego obiektu. Następnie odczytujemy odpowiednią wartość z pola. W naszym przykładzie szukamy 3 elementu listy.

Szukanie węzła na liście jednokierunkowej

Szukanie węzła na liście jednokierunkowej

W pierwszym kroku sprawdzamy czy podany indeks nie jest ujemny. Następnie przechodzimy listę tyle razy, ile pokazuje indeks lub aż zmienna curr będzie wskazywała na null.

W powyższym kodzie pojawił się pewien fragment, który nie jest jeszcze znany czyli temat rzucania wyjątków. Omówimy go w przyszłości, a na razie traktujemy jako zabezpieczenie przed próbą dostępu do nieistniejącego elementu.

Wypisanie wszystkich elementów listy jednokierunkowej

Wypisanie wszystkich elementów kolekcji działa podobnie do poprzedniego algorytmu. Jedyną różnicą jest to, że przeglądamy całą listę aż element będzie wskazywał, że następny element to wartość null. Metoda nie zwraca żadnych wartości, tylko wypisuje je na ekranie.

Dodawanie elementu do listy jednokierunkowej

Algorytm polega na przejściu całej listy i wskazanie referencji aktualnego ogona na nowo utworzony obiekt.

Dodawanie węzła do listy jednokierunkowej

Dodawanie węzła do listy jednokierunkowej

Na początku tworzymy zmienną curr, która przechowuje referencję do głowy listy oraz węzeł newWezel, który jest elementem dodawanym. Jeżeli zmienna curr wskazuje na null, to znaczy, że lista jest pusta i nową głową staje się dodawany element. W przeciwnym wypadku przechodzimy listę aż do ogona. W nim ustawiamy następne element na newWezel.

Usuwanie elementów z listy jednokierunkowej

Najważniejszym zadaniem jest to, aby przy usuwaniu elementu nie stracić ciągłości listy. Usuwanie dowolnych elementów można podzielić na trzy przypadki.

Usuwanie pierwszego węzła – głowy

W przypadku usuwania pierwszego elementu należy w pierwszej kolejności jako głowę ustawić drugi element listy. Ponieważ elementy nie posiadają referencji do poprzednich elementów nie trzeba ich aktualizować.

Usuwanie pierwszego elementu z listy jednokierunkowej

Usuwanie pierwszego węzła z listy jednokierunkowej

Usuwanie ostatniego elementu – ogona

W tym przypadku należy przejść całą listę do końca, a w dodatkowej zmiennej przechowywać referencję do poprzedniego elementu. Jeżeli dojdziemy do końca listy, to w zmiennej pomocniczej należy odpiąć referencję do następnego obiektu.

Usuwanie ostatniego węzła z listy jednokierunkowej

Usuwanie ostatniego węzła z listy jednokierunkowej

Usuwanie środkowego elementu

Tutaj również przyda się zmienna pomocnicza, która będzie przechowywała poprzedni element. Gdy już znajdziemy element do usunięcia, to należy ustawić referencję elementu pomocniczego na następny element obiektu usuwanego.

Usuwanie środkowego węzła z listy jednokierunkowej

Usuwanie środkowego węzła z listy jednokierunkowej

Pełny algorytm usuwania węzła z listy

W pierwszej kolejności należy sprawdzić czy lista nie jest pusta. Jeśli nie jest, należy przejść całą listę aż referencja na następny element zmiennej curr będzie wskazywała na null i indeks węzła będzie mniejszy niż podany w parametrze. Za każdym razem ustawiamy zmienną prev na aktualną wartość curr oraz curr ustawiamy na kolejny element listy. Następnie sprawdzamy, którą z trzech sytuacji będziemy musieli obsłużyć:

  • jeśli prev będzie wskazywała na null, to mamy do czynienia z usunięciem głowy,
  • jeśli referencja na kolejny element curr będzie wskazywała na null, to usuwamy ogon,
  • w innym przypadku usuwamy element ze środka listy.

Algorytmy na listach dwukierunkowych w Javie

Odczyt z listy dwukierunkowej

Odczyt z listy możemy rozwiązać na kilka sposobów. W zależności od potrzeby może to być n-ty element. Możemy też szukać konkretnej wartości lub wypisać wartości z każdego węzła listy. Poniżej pokażemy przykład metody, która znajduje element podany w parametrze. W naszym przypadku będzie to 3 element listy.

szukanie węzła na liście dwukierunkowej

Szukanie węzła na liście dwukierunkowej

Aby znaleźć konkretny element należy przejść po liście przez kolejne węzły, a następnie zwrócić żądany element. Poniżej przykładowa implementacja.

W powyższym kodzie pojawił się pewien fragment, który nie jest jeszcze znany czyli temat rzucania wyjątków. Omówimy go w przyszłości, a na razie traktujemy jako zabezpieczenie przed próbą dostępu do nie istniejącego elementu.

Wypisanie wszystkich elementów listy dwukierunkowej

Kolejny algorytm będzie wypisywał wszystkie elementy z listy. Zwróćmy uwagę, że kod nie różni się od tego potrzebnego do obsługi listy jednokierunkowej, gdyż przechodzimy ją tylko do przodu.

Dodawanie węzła do listy dwukierunkowej

Element może zostać dodany początek, koniec lub środek listy. W każdym przypadku należy zaktualizować powiązania z sąsiadami. Nasz algorytm będzie dodawał element na końcu listy.

dodawanie węzła do listy dwukierunkowej

dodawanie węzła do listy dwukierunkowej

Poniżej pokazujemy przykładowy algorytm dodania węzła na koniec listy.

Usuwanie węzła z listy dwukierunkowej

Podobnie jak powyżej należy zaktualizować odpowiednio relacje między węzłami. Należy uważać, aby przez przypadek nie usunąć głowy lub nie stracić „ciągłości” listy przez brak wskazania do następnego elementu. Te czynności są szczególnie uporczywe w językach, w których może dojść do wycieku pamięci.

Usuwanie pierwszego elementu – głowy

W przypadku usuwania pierwszego elementu należy w pierwszej kolejności jako głowę ustawić drugi element listy. Następnie usunąć połączenia między nową głową a elementem usuwanym.

Usuwanie pierwszego elementu z listy

Usuwanie pierwszego elementu z listy dwukierunkowej

Oczywiście zniknięcie elementu jest umowne, gdyż w Javie nie mamy kontroli nad systemem zbierania nieużytków tak jak w innych językach np. C i poleceniu free. Dlatego należy usunąć referencję do obiektu, aby następnym razem podczas czyszczenia pamięci również system usunął z pamięci nasz nieużywany węzeł.

Usuwanie ostatniego węzła z listy (ogona)

Podobnie jak w poprzednim przypadku musimy odłączyć od listy element, ale tym razem nie musimy obawiać się o głowę.

Usuwanie ostatniego elementu z listy

Usuwanie ostatniego elementu z listy dwukierunkowej

Usuwanie środkowego węzła z listy

W tym przypadku należy zmienić następny element poprzednika wskazanego elementu na następny element od usuwanego elementu. Następnie podobnie postąpić z poprzednikiem następnego elementu.

Usuwanie środkowego elementu z listy

Usuwanie środkowego elementu z listy dwukierunkowej

Pełny algorytm usuwania węzła z listy

Poniżej znajduje się algorytm usunięcia węzła z dowolnej pozycji. Najpierw wyszukiwana jest pozycja węzła wg. podanego wcześniej argumentu, a następnie w zależności od tego, który węzeł jest usuwany ustawiane są odpowiednie referencje.

Oczywiście istnieje wiele innych przydatnych metod, które można wymienić, ale te powyższe są podstawowe i pozwalają zrozumieć istotę list.

Nasze implementacje list w Javie