Come implementare l'elenco circolare circolare in java?

Question

Ho letto un libro su "Strutture dati e algoritmi" in cui esiste un incarico che mi chiede di implementare una lista circolare circolare. Questo è un esercizio di apprendimento e il mio codice potrebbe non essere di altissimo livello.

L'idea principale dietro la mia implementazione di un elenco circolare circolare è di avere un puntatore che punta all'ultimo elemento e ogni volta che aggiungo un nuovo elemento, il campo "prossimo" dell'ultimo elemento verrà aggiornato per puntare al nuovo elemento aggiunto.

Il metodo di inserimento funziona correttamente, posso aggiungere elementi senza problemi, ma per qualche motivo non riesco a eliminare elementi dall'elenco.

Qui è il codice per 'Link' o 'nodo':

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 

Questo è il codice per la classe che svolge il lavoro, e il bug è ovviamente da qualche parte qui:

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 

e il codice applicazione principale:

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 

la quantità di visualizzazione sembra un po 'sciocco, ho solo cercato di evitare il ciclo infinito e m Ade qualcosa di semplice che funziona.

Answer 1

Aggiungere last.next = first prima return temp nella funzione di cancellazione():

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

Aggiornato:

non riesco a trovare uno scenario che soddisfano first.next == null, e dovremmo prendere in considerazione chiamando delete() in una lista vuota.

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

Il metodo delete() non gestisce la circolarità dell'elenco. L'ultimo elemento punta al primo elemento; anche questo deve essere aggiornato quando il primo elemento viene cancellato.

In altre parole, è necessario impostare last.next in modo che punti al nuovo first anziché al vecchio first.

L'altra questione che hai è che se si elimina l'elemento finale (in modo che sia ora vuota), allora è anche necessario impostare last a null.

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