Abstrakcyjne struktury danych: Lista
Lista cykliczna dwukierunkowa wiązana
W poprzednim przykładzie napisaliśmy listę dwukierunkową wiązaną, teraz postaramy się ją przerobić na cykliczną listę dwukierunkową wiązaną. Od poprzedniej naszej listy różni się ona tym, że pierwszy element znacznikiem prev wskazuje na ostatni, a ostatni znacznikiem next na pierwszy.
Graficznie prezentuje się to tak:
Dla przypomnienia, to wszystkie operacje będziemy wykonywać na tym kodzie:
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) {
}Nowa metoda add() będzie więc wyglądać tak:
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;
first.prev = last;
last = l;
last.next = first;
}
else
{
l = new Value(x, v.next, v);
if(l.next != null)
v.next.prev = l;
else
{
last = l;
last.next = first;
}
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) {
}Nowa metoda delete() będzie wyglądać tak:
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;
first.prev = last;
last = l;
last.next = first;
}
else
{
l = new Value(x, v.next, v);
if(l.next != null)
v.next.prev = l;
else
{
last = l;
last.next = first;
}
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 = last;
}
else
{
prev.next = f.next;
if(f.next == null)
{
last = prev;
last.next = first;
}
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) {
}
}Oczywiście musimy również przeprowadzić drobną modyfikację metody searchValue() tak aby program nam się nie zapętlił:
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;
first.prev = last;
last = l;
last.next = first;
}
else
{
l = new Value(x, v.next, v);
if(l.next != null)
v.next.prev = l;
else
{
last = l;
last.next = first;
}
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 = last;
}
else
{
prev.next = f.next;
if(f.next == null)
{
last = prev;
last.next = first;
}
else
f.next.prev = prev;
}
}
int searchValue(int x)
{
Value f = first;
if(f.value == x)
return f.value;
else
f = f.next;
while(f != null && f.value != x || f != first)
f = f.next;
return f.value;
}
}
public class Main {
public static void main(String[] args) {
}
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 ;)