Jak zaimplementować połączoną listę cykliczną w java?

Question

Przeczytałem książkę o "Strukturach danych i algorytmach", w której znajduje się zadanie, które prosi mnie o zaimplementowanie połączonej listy. Jest to ćwiczenie do nauki, a mój kod może nie mieć bardzo wysokiego standardu.

Głównym założeniem mojego wdrożenia połączonej listy kołowej jest posiadanie wskaźnika wskazującego ostatni element i za każdym razem, gdy dodam nowy element, pole "następny" ostatniego elementu zostanie odświeżone, aby wskazać nowo dodany przedmiot.

Metoda wstawiania działa dobrze, mogę dodać pozycję bez żadnych problemów, ale z jakiegoś powodu nie mogę usunąć pozycji z listy.

Oto kod dla „link” lub „Node”:

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 

Jest to kod dla klasy, która wykonuje pracę, a błąd jest oczywiście gdzieś tutaj:

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 

A głównym kod aplikacji:

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 

kwota wyświetlacz wygląda trochę głupie, po prostu starał się uniknąć nieskończoną pętlę i m coś prostego, co po prostu działa.

Answer 1

Dodaj last.next = first przed return temp w kasowania function():

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

Aktualizacja:

nie mogę znaleźć scenariusz, który zaspokoi first.next == null, a my powinniśmy wziąć pod uwagę wywołanie delete() na pustej liście.

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

Twoja metoda delete() nie obsługuje okrągłości listy. Ostatni element wskazuje na pierwszy element; to również wymaga aktualizacji po usunięciu pierwszego elementu.

Innymi słowy, należy ustawić last.next, aby wskazać nowy first zamiast starego first.

Innym problemem jest to, że jeśli usuniesz ostatni element (tak, że jest teraz pusty), musisz również ustawić last na null.

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