Implementacja listy wiązanej dwukierunkowej

by Red 25 marca 2020

Struktura listy dwukierunkowej

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.

Lista ta powstała w celu dydaktycznym, aby pokazać jak wygląda własne opracowanie algorytmu. W związku z tym nie implementujemy żadnych interfejsów, takich jak Comparable, który mógłby posłużyć do sortowania elementów. Z tego samego powodu nie jest to również klasa generyczna, dlatego nie można w tej kolekcji przechowywać żadnych typów własnych, ani innych typów prostych niż int.

Naszym celem było napisanie jak najprostszego algorytmu, aby skupić się na działaniu tej konkretnej struktury danych. Tak, aby w praktyczny sposób przekazać wiedzę z naszego teoretycznego wstępu odnośnie list dwukierunkowych.

Typem danych do przechowywania jest int. Aby uruchomić poniższy kod należy skopiować kod, a następnie skompilować.

package pl.programistajava.lista;
public class Lista {
private Wezel head;
class Wezel {
private Wezel next;
private Wezel prev;
private int data;
public Wezel(int d){
next = null;
prev = 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 w = this.head;
System.out.print("[ ");
while(w != null) {
System.out.print(w.data + " ");
w = w.next;
}
System.out.print("]");
}
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 void addWezel(int s) {
Wezel w = head;
Wezel last = null;
Wezel tmp = new Wezel(s);
while(w != null) {
last = w;
w = w.next;
}
if(last == null) {
this.head = tmp;
}else {
last.next = tmp;
tmp.prev = last;
}			
}
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;
}			
}
}

package pl.programistajava.lista;

public class Lista {

private Wezel head;

class Wezel {

private Wezel next;

private Wezel prev;

private int data;

public Wezel(int d){

next = null;

prev = 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 w = this.head;

System.out.print("[ ");

while(w != null) {

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

w = w.next;

}

System.out.print("]");

}

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 void addWezel(int s) {

Wezel w = head;

Wezel last = null;

Wezel tmp = new Wezel(s);

while(w != null) {

last = w;

w = w.next;

}

if(last == null) {

this.head = tmp;

}else {

last.next = tmp;

tmp.prev = last;

}

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;

}

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 dwie referencje do innych obiektów oraz zmienną przechowującą dane.

Konstruktor

Inicjuje dane – pola obiektowe czyli referencje do poprzednie i następnego obiektu ustawia 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. Dane zostały dobrane w taki sposób, aby nie spowodować wyjątku. Wykonanie metody main() spowoduje wyświetlenie następujących komunikatów w konsoli.

[ 1 2 3 ]
[ 1 3 ]

1 2	[ 1 2 3 ] [ 1 3 ]

Zachęcamy do eksperymentów z kodem.

Metody

Wielokrotne wykorzystanie kodu pozytywnie wpływa na jego objętość. Lista dwukierunkowa pozwala na ponowne wykorzystanie metody getWezel() w celu znalezienia usuwanego węzła zamiast pisać ponownie kod, który robi tę samą czynność.

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)

Być może programiści innych języków zwrócili uwagę na to, że po usunięciu elementów nie czyścimy ręcznie pamięci. W językach z rodziny C oprócz zmiany wskaźników na odpowiednie elementy należy użyć funkcji free(), która czyści pamięć – w przeciwnym wypadku po wyjściu z funkcji usuwania elementu stracimy wskaźnik na usuwany element i nigdy już go nie będziemy w stanie usunąć – do restartu maszyny.

W Javie jeśli nie mamy dostępu do obiektu, to nie musimy z tym nic robić. System zbierania nieużytków zrobi wszystko za nas i oczyści pamięć ze zbędnych obiektów.

Polecamy również zapoznać się z implementacją listy jednokierunkowej. Pozornie obie wydają się podobne, jednakże różnią się znacznie przy samej budowie.

Tweetuj

Udostępnij

Przypnij

0 Udostępnień