Wie implementiert man zirkuläre verkettete Liste in Java?

Question

Ich lese ein Buch über "Datenstrukturen und Algorithmen", in dem es eine Aufgabe gibt, die mich auffordert, eine zirkuläre verkettete Liste zu implementieren. Dies ist eine Lernübung und mein Code ist möglicherweise nicht von sehr hohem Standard.

Der Grundgedanke hinter meiner Implementierung einer zirkular verknüpften Liste ist ein Zeiger, der auf das letzte Element zeigt und jedes Mal, wenn ich ein neues Element hinzufüge, wird das Feld 'next' des letzten Elements aktualisiert neu hinzugefügter Artikel

Die Einfügemethode funktioniert gut, ich kann Element ohne Probleme hinzufügen, aber aus irgendeinem Grund kann ich keine Elemente aus der Liste löschen. Hier

ist der Code für ‚Link‘ oder ‚Knoten‘:

public class Link { 
    public long data; 
    public Link next; 

    public Link(long val) { 
    data = val; 
    next = null; 
    } 

    public void displayLink() { 
    System.out.print(data + " "); 
    } 

} // end class 

Dies ist der Code für die Klasse, die die Arbeit ausführt, und der Fehler ist offensichtlich irgendwo hier:

public class CircularList { 
Link first; 
Link last; 

public CircularList() { 
    first = null; 
    last = null; 
} 

public Link find(long key) { 
    Link current = first; 
    while(current.data != key) { 
     current = current.next; 
    } 
    return current; 
} // end find 

public Link delete() { 
    if(first.next == null) 
     last = null; 
    Link temp = first; 
    first = first.next; 
    return temp; 
} // end delete 

public boolean isEmpty() { return (first == null); } 

public void insert(long val) { 
    Link newLink = new Link(val); 

    if(isEmpty()) 
     last = newLink; 

    newLink.next = first; 
    first = newLink; 
    last.next = first; 
} // end insert 

public void displayAmount(int n) { 
    Link current = first; 
    while(n>0) { 
     current.displayLink(); 
     current = current.next; 
     n--; 
    } 
    System.out.println(""); 
} // end displayAmount 

} // end class 

und die Haupt App-Code:

public class App { 
public static void main(String[] args) { 
    CircularList cl = new CircularList(); 

    cl.insert(10); 
    cl.insert(20); 
    cl.insert(30); 
    cl.insert(40); 

    cl.displayAmount(6); 

    cl.delete(); 

    cl.displayAmount(6); 
} 
} // end class 

die Anzeige Menge Art von albern aussieht, ich habe gerade versucht Endlosschleife und m zu vermeiden ade etwas einfaches, das einfach funktioniert.

Answer 1

hinzufügen last.next = first vor return temp in Ihrem delete() Funktion:

public Link delete() { 
    if(first.next == null) 
     last = null; 
    Link temp = first; 
    first = first.next; 
    if(last != null) 
     last.next = first 
    return temp; 
} 

Aktualisiert:

Ich kann kein Szenario finden, die first.next == null erfüllen, und wir sollten berücksichtigen, löschen() aufrufen auf einer leeren Liste.

public Link delete() { 
    Link temp = first; 
    if(first == null){ 
     ; // or you can throw some exception as a warning 
    } 
    else if(first==last){ // only one element 
     first = null; // reset to initial state 
     last = null; 
    } 
    else{ 
     first = first.next; 
     last.next = first; 
    } 
    return temp; 
} 

Answer 2

Ihre delete() Methode behandelt nicht die Zirkularität der Liste. Das letzte Element zeigt auf das erste Element; das muss auch aktualisiert werden, wenn das erste Element gelöscht wird.

Mit anderen Worten, Sie müssen last.next auf den neuen first anstelle der alten first zeigen.

Das andere Problem, das Sie haben, ist, dass wenn Sie das letzte Element löschen (so dass es jetzt leer ist), müssen Sie auch last auf null setzen.

public Link delete() { 
    if (first.next == null) { 
     first = null; 
     last = null; 
    } 
    Link temp = first; 
    first = first.next; 
    last.next = first; 
    return temp; 
}