Implementacja listy jednokierunkowej w Javie
Implementacja listy jednokierunkowej w Javie
Nasza lista jest zbudowana z dwóch klas.
- Wezel – klasa wewnętrzna – reprezentuje pojedynczy węzeł na liście.
- Lista – klasa zewnętrzna – zawiera algorytmy dodawania, usuwania oraz wyświetlania elementów oraz przechowuje pierwszy element listy.
Aby pokazać różnice pomiędzy listami dwukierunkowymi a jednokierunkowymi postanowiliśmy opracować własną implementację. Ponownie naszym celem jest pokazanie działania tej struktury danych, a nie możliwości interfejsów, takich jak Comparable lub Iterable. Aby maksymalnie uprościć kod przechowywanym typem danych będzie int.
Naszym celem było napisanie jak najprostszego algorytmu, aby pokazać jak operować na listach jednokierunkowych. Tak, aby w praktyczny sposób przekazać wiedzę z naszego teoretycznego wstępu odnośnie list jednokierunkowych. Na pierwszy rzut oka implementacja jest bardzo podobna do listy dwukierunkowej, jednakże w przypadku usuwania węzła jesteśmy zmuszeni utworzyć tymczasową zmienną, która będzie go przechowywać. W przeciwnym wypadku stracimy możliwość np. zmiany referencji w poprzednim ogniwie listy, gdyż aktualnie usuwany element „nie zna” położenie swojego poprzednika.
Aby uruchomić poniższy kod należy skopiować kod, a następnie skompilować.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 |
package pl.programistajava.listaJednokierunkowa; public class Lista { private Wezel head; class Wezel { private Wezel next; private int data; public Wezel(int d){ next = null; data = d; } } public Lista() { this.head = null; } public static void main(String[] args){ Lista list = new Lista(); list.addWezel(1); list.addWezel(2); list.addWezel(3); list.wypiszListe(); System.out.println(); list.removeWezel(1); list.wypiszListe(); } 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 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 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 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; } } } |
Wewnętrzna klasa Wezel
Powyższy program można podzielić na dwie części. Pierwszą jest obiekt, który przechowuje dane i jest nią klasa Wezel. Ze względu na to, że ta struktura danych jest mało elastyczna umieściliśmy ją wewnątrz klasy Lista, gdyż i tak nie wykorzystamy jej nigdzie indziej. Takie podejście jest wygodnie, ponieważ mamy ułatwiony dostęp do pól obu klas.
Pola
Obiekt klasy Wezel zawiera jedną referencję do kolejnego obiektu oraz zmienną przechowującą dane. Jeśli dany węzeł jest ostatni (ogon), to jego referencją na następny obiekt jest wartość null.
Konstruktor
Inicjuje dane – referencję do następnego obiektu na null, a pole z danymi uzupełnia wartością przekazaną w argumencie.
Zewnętrzna klasa Lista
Obiekt klasy Lista przechowuje referencję do pierwszego elementu listy, czyli głowę (ang. head). Zawiera również niezbędne algorytmy, takie jak:
- dodawanie elementów do listy,
- usuwanie elementów z listy,
- szukanie elementu o konkretnym indeksie,
- wypisanie wszystkich elementów listy.
W metodzie main znajduje się przykładowy przebieg programu. Wykonanie metody main spowoduje wyświetlenie następujących komunikatów w konsoli.
|
1 2 |
[ 1 2 3 ] [ 1 3 ] |
Zachęcamy do eksperymentów z kodem.
Metody
Podstawową różnicą między implementacją listy dwukierunkowej jest algorytm usuwania elementu. Żaden węzeł nie zna położenia swojego poprzednika zatem przy przechodzeniu listy musimy utworzyć zmienną pomocniczą, którą będzie przechowywała jego referencję.
Czemu jednak nie postąpić jak w przypadku list dwukierunkowych i do zmiennej pomocniczej nie użyć po prostu argumentu n-1? Przecież byłoby to dużo wygodniejsze i kod zajmowałby mniej linii. Powodem jest wydajność. Zwróćmy uwagę, że metoda getWezel() byłaby wywołana dwa razy – raz z argumentem n, a za drugim razem n-1. Jednakże dwukrotnie przejście przez listę zaczynałoby się od głowy listy. Oznacza to podwojenie liczby wykonywanych operacji. W przypadku małej kolekcji oczywiście nie ma to znaczenia, ale kolekcja może składać się z bardzo wielu elementów.
Wyjątek IndexOutOfBoundException
Jeżeli spróbujemy wpisać do metody szukającej indeks ujemny lub spoza naszej listy zostanie wyrzucony wyjątek.
System zbierania nieużytków (ang. Garbage collector)
W Javie nie ma potrzeby ręcznego czyszczenia pamięci. Jeśli nie mamy już referencji do obiektu, to nie musimy z tym nic robić. System zbierania nieużytków oczyści pamięć ze zbędnych obiektów.