Próbuję zaimplementować listę dwukierunkową dwustronną i kilka operacji na niej, m.in. odwracanie listy oraz łączenie dwóch, ale natknąłem na problem, którego rozwiązanie zajęło mi już trochę czasu a efektów nie widać. Powyższe operacje (odwracanie, łącznie) wykonuję w czasie stałym. Odwracanie polega na zmianie flagi REVERSE_FLAG oraz przepięciu pierwszego elementu z ostatnim i ostatniego z pierwszym. Wszystko działa do czasu, aż nie stworzę dwóch list, nie odwrócę jednej a następnie nie spróbuję ich połączyć, co przedstawia poniższy przykład:
lista pierwsze: L1 L2 L3 L4 L5
lista druga: X1 X2 X3 X4 X5
- wykonuję reverse na liście drugiej i otrzymuję: X5 X4 X3 X2 X1,
- następnie union listy pierwszej oraz listy drugiej, co powinno dać L1 L2 L3 L4 L5 X5 X4 X3 X2 X1. Niestety otrzymuję gdzieś nieskończoną pętlę, gdyż program się zawiesza.
Mój typ, to problem z łączeniem w metodzie union. Obie listy to dwa obiekty. Samo przepięcie wskaźników nie rozwiązuje problemu REVERSE_FLAG, które dla każdego obiektu jest inne, co przy trawersowaniu metodą display z listy pierwszej, powoduje błędną interpretację drugiej listy, uprzednio obróconej, czyli ze zmienionym REVERSE_FLAG. To mój typ, ale nie jestem pewien oraz nie wiem w jaki sposób to rozwiązać. Dodam tylko, że przy odwróceniu obu list jednocześnie i późniejszym połączeniu, wyświetlają się poprawnie.
Funkcja łącząca:
public void union(String t1, String t2) {
DoublyLinked temp1 = locate(t1); // znajduje listę w zbiorze list
DoublyLinked temp2 = locate(t2); // znajduje listę w zbiorze list
temp1 = temp1.next;
temp2 = temp2.next;
temp1.setNext(temp1.last, temp2.first);
temp2.setPrev(temp2.first, temp1.last);
temp1.last = temp2.last;
train2.first = temp1.first;
temp2.last = temp1.last;
temp2.REVERSE_FLAG = temp1.REVERSE_FLAG;
}
class Link {
public Link next;
public Link prev;
public String value;
public Link (String value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
Lista dwukierunkowa dwustronna:
class DoublyLinked {
public boolean REVERSE_FLAG;
public String name;
public Link first;
public Link last;
public DoublyLinked next;
public DoublyLinked (String name, String w) {
New(name, w);
}
public void New(String name, String w) {
Link c = new Link(w);
this.REVERSE_FLAG = false;
this.name = name;
this.last = this.first = c;
}
public void insertFirst(String w) {
Link temp = new Link(w);
setNext(temp, this.first);
setPrev(this.first, temp);
this.first = temp;
}
public void insertLast(String w) {
Link temp = new Link(w);
setPrev(temp, this.last);
setNext(this.last, temp);
this.last = temp;
}
public String delFirst() {
if (getNext(this.first) != null) {
setPrev(getNext(this.first), null);
String temp = this.first.value;
this.first = getNext(this.first);
return temp;
} else {
this.first = this.last = null;
return this.first.value;
}
}
public String delLast() {
if (this.last != this.first) {
setNext(getPrev(this.last), null);
String temp = this.last.value;
this.last = getPrev(this.last);
return temp;
} else {
this.first = this.last = null;
return this.last.value;
}
}
public void reverse() {
REVERSE_FLAG = !REVERSE_FLAG;
Link swap;
swap = first;
first = last;
last = swap;
}
public String display() {
String output = new String();
Link curr = first;
while (curr != null) {
output += curr.value;
System.out.print(curr.value);
if (getNext(curr) != null) {
output += " ";
System.out.print(" ");
}
curr = getNext(curr);
}
System.out.println();
output += "\n";
return output;
}
public Link getNext(Link c) {
return (REVERSE_FLAG) ? c.prev : c.next;
}
public Link getPrev(Link c) {
return (REVERSE_FLAG) ? c.next : c.prev;
}
public void setNext(Link c, Link next) {
if (REVERSE_FLAG) {
c.prev = next;
} else {
c.next = next;
}
}
public void setPrev(Link c, Link prev) {
if (REVERSE_FLAG) {
c.next = prev;
} else {
c.prev = prev;
}
}
public boolean isEmpty() {
return (first == null && last == null) ? true : false;
}
public Link locate(String w) {
Link curr = first;
while (curr != null && !curr.value.equals(w)) {
curr = getNext(curr);
}
return curr;
}
}