Listy jako struktura danych

by Red 16 marca 2020

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.

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

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

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.

public Wezel getWezel(int n) {
if(n < 0) {
throw new IndexOutOfBoundsException("Nie można podać ujemnego argumentu");
}
int i = 0;
Wezel curr = this.head;
while(curr != null && i++ < n) {
curr = curr.next;
}
if (curr == null) {
throw new IndexOutOfBoundsException("Nie istnieje obiekt o podanym argumencie.");
}
return curr;
}

public Wezel getWezel(int n) {

if(n < 0) {

throw new IndexOutOfBoundsException("Nie można podać ujemnego argumentu");

}

int i = 0;

Wezel curr = this.head;

while(curr != null && i++ < n) {

curr = curr.next;

}

if (curr == null) {

throw new IndexOutOfBoundsException("Nie istnieje obiekt o podanym argumencie.");

}

return curr;

}

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.

public void wypiszListe() {
Wezel curr = this.head;
System.out.print("[ ");
while(curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.print("]");
}

public void wypiszListe() {

Wezel curr = this.head;

System.out.print("[ ");

while(curr != null) {

System.out.print(curr.data + " ");

curr = curr.next;

}

System.out.print("]");

}

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

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.

public void addWezel(int s) {
Wezel curr = head;
Wezel newWezel = new Wezel(s);
if(curr == null) {
this.head = newWezel;
}else {
while(curr.next != null) {
curr = curr.next;
}
curr.next = newWezel;
}
}

public void addWezel(int s) {

Wezel curr = head;

Wezel newWezel = new Wezel(s);

if(curr == null) {

this.head = newWezel;

}else {

while(curr.next != null) {

curr = curr.next;

}

curr.next = 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 ś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

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.

public void removeWezel(int n) {
Wezel curr = head;
Wezel prev = null;
int i = 0;
if(curr == null) {
//gdy lista jest pusta
throw new NullPointerException("Lista jest pusta.");
}else {
while(curr.next != null && i++ < n) {
prev = curr;
curr = curr.next;
}
}
if(n > i) {
throw new IndexOutOfBoundsException("Nie istnieje obiekt o podanym argumencie");
}
if(prev == null) {
//gdy usuwamy głowę
this.head = curr.next;
}else if(curr.next == null) {
//gdy usuwamy ogon
prev.next = null;
}else {
//gdy usuwamy środek
prev.next = curr.next;
}			
}

public void removeWezel(int n) {

Wezel curr = head;

Wezel prev = null;

int i = 0;

if(curr == null) {

//gdy lista jest pusta

throw new NullPointerException("Lista jest pusta.");

}else {

while(curr.next != null && i++ < n) {

prev = curr;

curr = curr.next;

}

if(n > i) {

throw new IndexOutOfBoundsException("Nie istnieje obiekt o podanym argumencie");

}

if(prev == null) {

//gdy usuwamy głowę

this.head = curr.next;

}else if(curr.next == null) {

//gdy usuwamy ogon

prev.next = null;

}else {

//gdy usuwamy środek

prev.next = curr.next;

}

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

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.

public Wezel getWezel(int n) throws IndexOutOfBoundsException{
if(n < 0) {
throw new IndexOutOfBoundsException("Nie można podać ujemnego argumentu");
}
int i = 0;
Wezel w = this.head;
while(w != null && i++ < n) {
w = w.next;
}
if (w == null) {
throw new IndexOutOfBoundsException("Nie istnieje obiekt o podanym argumencie.");
}
return w;
}

public Wezel getWezel(int n) throws IndexOutOfBoundsException{

if(n < 0) {

throw new IndexOutOfBoundsException("Nie można podać ujemnego argumentu");

}

int i = 0;

Wezel w = this.head;

while(w != null && i++ < n) {

w = w.next;

}

if (w == null) {

throw new IndexOutOfBoundsException("Nie istnieje obiekt o podanym argumencie.");

}

return w;

}

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.

public void wypiszListe() {
Wezel w = this.head;
System.out.print("[ ");
while(w != null) {
System.out.print(w.data + " ");
w = w.next;
}
System.out.print("]");
}

public void wypiszListe() {

Wezel w = this.head;

System.out.print("[ ");

while(w != null) {

System.out.print(w.data + " ");

w = w.next;

}

System.out.print("]");

}

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

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

public void addWezel(int s) {
Wezel curr = head;
Wezel newWezel = new Wezel(s);
if(curr == null) {
this.head = newWezel;
}else {
while(curr.next != null) {
curr = curr.next;
}
curr.next = newWezel;
newWezel.prev = curr;
}
}

public void addWezel(int s) {

Wezel curr = head;

Wezel newWezel = new Wezel(s);

if(curr == null) {

this.head = newWezel;

}else {

while(curr.next != null) {

curr = curr.next;

}

curr.next = newWezel;

newWezel.prev = curr;

}

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 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 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 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.

public void removeWezel(int n) {
Wezel w = getWezel(n);
if(w.prev == null) {
//gdy usuwamy głowę
this.head = w.next;
this.head.prev = null;
}	
else if(w.next == null) {
//gdy usuwamy ogon
w = w.prev;
w.next = null;
}	
else {
//gdy usuwamy środek
w.prev.next = w.next;
w.next.prev = w.prev;
}			
}

public void removeWezel(int n) {

Wezel w = getWezel(n);

if(w.prev == null) {

//gdy usuwamy głowę

this.head = w.next;

this.head.prev = null;

}

else if(w.next == null) {

//gdy usuwamy ogon

w = w.prev;

w.next = null;

}

else {

//gdy usuwamy środek

w.prev.next = w.next;

w.next.prev = w.prev;

}

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

Tweetuj

Udostępnij

Przypnij

0 Udostępnień