Abstrakcyjne struktury danych: Lista
Lista wiązana dwukierunkowa
W poprzednim przykładzie napisaliśmy listę wiązaną jednokierunkową, teraz trochę ją przerobimy na listę wiązaną dwukierunkową czyli do każdego elementu dodamy wskaźnik na poprzedni oraz dla lepszej wygody zrobimy pole last, w którym będziemy przechowywać informacje o ostatnim elemencie listy.
Graficzna implementacja listy wiązanej dwukierunkowej:
Dla przypomnienia, to cały czas będziemy pracować na tym kodzie:
class Value
{
int value;
Value next;
Value(int x, Value Next)
{
value = x;
next = Next;
}
}
class List
{
Value first;
List()
{
first = null;
}
Value add(int x, Value v)
{
Value l;
if(first == null)
{
l = new Value(x, null);
first = l;
}
else
{
l = new Value(x, v.next);
v.next = l;
}
return l;
}
void delete(int x)
{
Value f = first;
Value prev = null;
while (f != null && f.value != x) {
prev = f ;
f = f.next;
}
if (f != null)
if (prev == null)
first = f.next;
else
prev.next = f.next;
}
int searchValue(int x)
{
Value f = first;
while(f != null && f.value != x)
f = f.next;
return f.value;
}
}
public class Main {
public static void main(String[] args) {
}
}No to skoro każdy element listy ma mieć wskaźnik na poprzedni to musimy nieco zmodyfikować naszą klasę Value. Dodajemy więc nowe pole o nazwie prev i inicjalizujemy je w konstruktorze:
class Value
{
int value;
Value next;
Value prev;
Value(int x, Value Next, Value Prev)
{
value = x;
next = Next;
prev = Prev;
}
}
class List
{
Value first;
List()
{
first = null;
}
Value add(int x, Value v)
{
Value l;
if(first == null)
{
l = new Value(x, null);
first = l;
}
else
{
l = new Value(x, v.next);
v.next = l;
}
return l;
}
void delete(int x)
{
Value f = first;
Value prev = null;
while (f != null && f.value != x) {
prev = f ;
f = f.next;
}
if (f != null)
if (prev == null)
first = f.next;
else
prev.next = f.next;
}
int searchValue(int x)
{
Value f = first;
while(f != null && f.value != x)
f = f.next;
return f.value;
}
}
public class Main {
public static void main(String[] args) {
}
}Oczywiście powyższy kod nam się nie skompiluje ponieważ metody takie jak add() oraz delete() są źle skonstruowane (jest niepoprawna liczba argumentów), musimy więc je przerobić.
Zabierzmy się więc za metodę add():
class Value
{
int value;
Value next;
Value prev;
Value(int x, Value Next, Value Prev)
{
value = x;
next = Next;
prev = Prev;
}
}
class List
{
Value first;
List()
{
first = null;
}
Value add(int x, Value v)
{
Value l;
if(first == null)
{
l = new Value(x, null, null);
first = l;
}
else
{
l = new Value(x, v.next);
v.next = l;
}
return l;
}
void delete(int x)
{
Value f = first;
Value prev = null;
while (f != null && f.value != x) {
prev = f ;
f = f.next;
}
if (f != null)
if (prev == null)
first = f.next;
else
prev.next = f.next;
}
int searchValue(int x)
{
Value f = first;
while(f != null && f.value != x)
f = f.next;
return f.value;
}
}
public class Main {
public static void main(String[] args) {
}
}
Jeśli chodzi o przypadek, w którym dodajemy do listy pierwszy element, no to tutaj sprawa jest banalnie prosta, jako argument odpowiadający za referencję do poprzedniego elementu podajemy oczywiście null i na tym kończymy modyfikację tego fragmentu kodu.
Teraz rozważmy drugi przypadek, gdzie dodajemy element do listy w której już jakieś elementy są:
class Value
{
int value;
Value next;
Value prev;
Value(int x, Value Next, Value Prev)
{
value = x;
next = Next;
prev = Prev;
}
}
class List
{
Value first;
List()
{
first = null;
}
Value add(int x, Value v)
{
Value l;
if(first == null)
{
l = new Value(x, null, null);
first = l;
}
else
{
l = new Value(x, v.next);
if(l.next != null)
v.next.prev = l;
v.next = l;
}
return l;
}
void delete(int x)
{
Value f = first;
Value prev = null;
while (f != null && f.value != x) {
prev = f ;
f = f.next;
}
if (f != null)
if (prev == null)
first = f.next;
else
prev.next = f.next;
}
int searchValue(int x)
{
Value f = first;
while(f != null && f.value != x)
f = f.next;
return f.value;
}
}
public class Main {
public static void main(String[] args) {
}
}Tutaj musimy sprawdzić czy nie jest to ostatni element i jeżeli nie jest, to do pola prev elementu następnego (v.next.prev) przypisujemy referencję do naszego nowego elementu. W przeciwnym wypadku automatycznie zostanie tam wstawiony null.
No to metodę add() mamy już za sobą więc pora na kolejną czyli delete():
class Value
{
int value;
Value next;
Value prev;
Value(int x, Value Next, Value Prev)
{
value = x;
next = Next;
prev = Prev;
}
}
class List
{
Value first;
List()
{
first = null;
}
Value add(int x, Value v)
{
Value l;
if(first == null)
{
l = new Value(x, null, null);
first = l;
}
else
{
l = new Value(x, v.next);
if(l.next != null)
v.next.prev = l;
v.next = l;
}
return l;
}
void delete(int x)
{
Value f = first;
Value prev = null;
while (f != null && f.value != x) {
prev = f ;
f = f.next;
}
if (f != null)
if (prev == null)
{
first = f.next;
first.prev = null;
}
else
{
prev.next = f.next;
if(f.next != null)
f.next.prev = prev;
}
}
int searchValue(int x)
{
Value f = first;
while(f != null && f.value != x)
f = f.next;
return f.value;
}
}
public class Main {
public static void main(String[] args) {
}
}Tutaj rozważamy dwa przypadki. Pierwszy to kasowanie pierwszego elementu naszej listy, w tym wypadku sprawa jest prosta: aktualizujemy pole first oraz do pola prev obiektu first przypisujemy null. W kolejnym kroku mamy nieco więcej do napisania. Zaczynamy od tego, że do pola elementu poprzedniego przypisujemy referencję na następny element po tym, który chcemy skasować (czyli jak by go omijamy) oraz zgodnie z tą samą zasadą aktualizujemy pole prev tak aby ominąć skasowany obiekt. Tutaj musimy się jeszcze zabezpieczyć przed próbą wykonania operacji na nieistniejącym punkcie listy.
Na końcu dla naszej lepszej wygody dorobimy jeszcze pole last odpowiedzialne za przechowywanie informacji o ostatnim elemencie listy:
class Value
{
int value;
Value next;
Value prev;
Value(int x, Value Next, Value Prev)
{
value = x;
next = Next;
prev = Prev;
}
}
class List
{
Value first;
Value last;
List()
{
first = null;
last = null;
}
Value add(int x, Value v)
{
Value l;
if(first == null)
{
l = new Value(x, null, null);
first = l;
last = l;
}
else
{
l = new Value(x, v.next, v);
if(l.next != null)
v.next.prev = l;
else
last = l;
v.next = l;
}
return l;
}
void delete(int x)
{
Value f = first;
Value prev = null;
while (f != null && f.value != x) {
prev = f ;
f = f.next;
}
if (f != null)
if (prev == null)
{
first = f.next;
first.prev = null;
}
else
{
prev.next = f.next;
if(f.next == null)
last = prev;
else
f.next.prev = prev;
}
}
int searchValue(int x)
{
Value f = first;
while(f != null && f.value != x)
f = f.next;
return f.value;
}
}
public class Main {
public static void main(String[] args) {
}
}Poniżej tradycyjnie zamieszczam w pełni działający program:
class Value
{
int value;
Value next;
Value prev;
Value(int x, Value Next, Value Prev)
{
value = x;
next = Next;
prev = Prev;
}
}
class List
{
Value first;
Value last;
List()
{
first = null;
last = null;
}
Value add(int x, Value v)
{
Value l;
if(first == null)
{
l = new Value(x, null, null);
first = l;
last = l;
}
else
{
l = new Value(x, v.next, v);
if(l.next != null)
v.next.prev = l;
else
last = l;
v.next = l;
}
return l;
}
void delete(int x)
{
Value f = first;
Value prev = null;
while (f != null && f.value != x) {
prev = f ;
f = f.next;
}
if (f != null)
if (prev == null)
{
first = f.next;
first.prev = null;
}
else
{
prev.next = f.next;
if(f.next == null)
last = prev;
else
f.next.prev = prev;
}
}
int searchValue(int x)
{
Value f = first;
while(f != null && f.value != x)
f = f.next;
return f.value;
}
}
public class Main {
public static void main(String[] args) {
List lista = new List(); //tworzymy listę
Value value = null;
for(int i = 0;i<10;i++)
{
value = lista.add(i,value); //dopisujemy do listy elementy od 0 do 9
}
Value x = lista.add(11,value); //dopisujemy element 11 na koniec listy
lista.add(13,value); //dopisujemy element 13 po elemencie 9
System.out.println(lista.searchValue(5)); //sprawdzamy czy element 5 jest na liście
lista.delete(6); //usuwamy element 6
Value f = lista.first;
while(f != null)
{
System.out.print(f.value + " -> "); //wypisujemy listę
f = f.next;
}
System.out.println();
System.out.println("----------------LISTA ODWRÓCONA-----------------");
f = lista.last;
while(f != null)
{
System.out.print(f.value + " -> "); //wypisujemy listę
f = f.prev;
}
}
}
W pierwszych kilku fragmentach kodu w klasie Value masz next typu List zamiast Value, poza tym takie coś jak:
List()
{
first = null;
}
jest nadmiarowe w Javie gdyż domyślnie zmienne składowe klasy będące obiektami inicjalizowane są nullami.
Faktycznie wkradł mi się drobny błąd, dzięki za info ;) Natomiast co do inicjalizacji to faktycznie w Java pola tego typu będą domyślnie wypełniane nullami więc nie ma potrzeby ich inicjalizacji w konstruktorze jednak w innych technologiach oraz przy innym typie zmiennych (np. int gdzie do zmiennej domyślnie zapisywane jest 0) będzie inaczej, a dobrą praktyką jest zawsze inicjalizowanie zmiennych ;)
Napisz poprawnie wyraz „dopóki” w ostatniej linijce drugiego akapitu, bo aż kłuje w oczy.
Dzięki za informację, poprawione ;)
Witam ;)
W 3 kodzie na stronie jest „mały błąd” – w konstruktorze jako jeden z argumentów bierzemy Next typu List, a przypisujemy go do next typu Value.
Świetna strona, pozdrawiam :)
Dzięki za czujność ;) Poprawione…
Witam,
czy mógłby mi ktoś wytłumaczyć dlaczego element 11 znajduje się na końcu listy?
A dokładniej, o co chodzi?
Nie bardzo rozumiem dlaczego element 11 znajduje się na końcu listy skoro metoda z 13 wywoływana jest później.
O który przykład chodzi?
2 strona (lista jednokierunkowa wiązana), na samym dole w metodzie main (wiersz 80-81)
W momencie dodawania elementu 11 do listy znajduje się on na jej końcu ;)