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;
last = l;
first.prev = last; //pierwszy element wskazuje sam na siebie
last.next = first;
}
else
{
l = new Value(x, v.next, v);
v.next.prev = l;
v.next = l;
if(v == last) //dopisaliśmy element na końcu listy
last = 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;
last = l;
first.prev = last; //pierwszy element wskazuje sam na siebie
last.next = first;
}
else
{
l = new Value(x, v.next, v);
v.next.prev = l;
v.next = l;
if(v == last) //dopisaliśmy element na końcu listy
last = 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 == first) //wykonaliśmy pełny cykl - wartości nie ma na liście
{
f = null;
break;
}
}
if (f != null)
if (f.next == f) //usuwamy jedyny element listy
{
first = null;
last = null;
}
else if (prev == null) //usuwamy pierwszy element
{
first = f.next;
first.prev = last;
last.next = first;
}
else
{
prev.next = f.next;
f.next.prev = prev;
if(f == last) //usuwamy ostatni element
last = 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;
last = l;
first.prev = last; //pierwszy element wskazuje sam na siebie
last.next = first;
}
else
{
l = new Value(x, v.next, v);
v.next.prev = l;
v.next = l;
if(v == last) //dopisaliśmy element na końcu listy
last = 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 == first) //wykonaliśmy pełny cykl - wartości nie ma na liście
{
f = null;
break;
}
}
if (f != null)
if (f.next == f) //usuwamy jedyny element listy
{
first = null;
last = null;
}
else if (prev == null) //usuwamy pierwszy element
{
first = f.next;
first.prev = last;
last.next = first;
}
else
{
prev.next = f.next;
f.next.prev = prev;
if(f == last) //usuwamy ostatni element
last = prev;
}
}
int searchValue(int x)
{
Value f = first;
if(f.value == x)
return f.value;
else
f = f.next;
while(f != first && f.value != x)
f = f.next;
if(f == first) //wykonaliśmy pełny cykl - wartości nie ma na liście
return -1;
return f.value;
}
}
public class Main {
public static void main(String[] args) {
}
}
Napisz poprawnie wyraz „dopóki” w ostatniej linijce drugiego akapitu, bo aż kłuje w oczy.
Dzięki za informację, 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 ;)