LinkedList circolare in Java

Question

Sto analizzando le mie strutture dati leggendo un libro e una delle domande che richiede è creare un singolo elenco collegato circolare non utilizzando "prima" & "ultimi" puntatori, ma piuttosto consentire l'accesso ad esso utilizzando un riferimento "corrente". Non sono sicuro di aver capito la domanda, ho sempre pensato di aver bisogno almeno del primo o dell'ultimo. Ecco la mia implementazione ma ha "prima", non so come aggirarla. Puoi per favore commentare come posso adattare il mio codice per eliminare la dipendenza prima?

class Link { 
    public int iData;    
    public Link next;    

    public Link(int id) { // constructor 
     iData = id;       
    }       

    public void displayLink() { 
     System.out.print(iData + " "); 
    } 
} // end class Link 

Poi ecco l'elenco stesso:

public class CircularLinkedList { 
    private Link first; 
    private Link current;  

    public Link getCurrent(){ 
     return current; 
    } 

    public void setCurrent(int data){ 

    } 

    public void advance(){ 
     current = current.next; 
    } 

    public void insert(int data) { 
     Link newLink = new Link(data); 
     if (first == null) { 
      first = current = newLink; 
     } else { 
      current.next = newLink; 
     } 
     current = newLink; 
     newLink.next = first; 
    } 
    ... 
} 

Answer 1

Se si dispone di un elenco circolare collegato, ciascun nodo punta al nodo successivo in un ciclo continuo. Quindi non c'è l'ultimo e non il primo. In questa situazione, hai solo bisogno di un puntatore nella struttura dati (che la domanda chiama "corrente") perché puoi percorrere l'intero elenco fino a quando non torni al punto in cui hai iniziato.

Un nodo potrebbe essere simile a questo:

public class ListNode<T> { 
    private T element; 
    private ListNode<T> next; 
} 

Quindi, in questo ambiente, quando si aggiunge il primo nodo alla lista, è puntatore "next" punterà a se stesso. Quando aggiungi il secondo nodo, ciascun puntatore "successivo" punta all'altro. Quando si aggiunge il terzo nodo, ognuno punta a quello successivo e presumibilmente questo viene ordinato in qualche modo. Ogni nodo aggiuntivo aggiunto verrà inserito nella posizione appropriata nel ciclo.

Un buon utilizzo per una struttura dati come questa sarebbe un programma che viene ripetuto ogni giorno o ogni ora. Tutti gli eventi possono essere memorizzati in un elenco circolare e il puntatore "corrente" punta sempre a quello che è in programma successivamente.

Ovviamente, quando si cerca una lista come questa, è necessario mantenere un riferimento al primo nodo. Questo è l'unico modo per sapere se hai cercato l'intero elenco poiché non termina con un puntatore "successivo" nullo.

Modifica: Come discusso nei (numerosi) commenti seguenti, un puntatore "a coda" sembra essere una buona idea qui per le operazioni di inserimento. Ecco il metodo originale che ho postato, che è stato rinominato insertAfter:

public void insertAfter(int data) { 
    Link newLink = new Link(data); 
    if (current == null) { 
     newLink.next = newLink; 
     current = newLink; 
    } else { 
     newLink.next = current.next; 
     current.next = newLink; 
    } 
} 

Un puntatore coda sarebbe sempre puntare al l'ultimo nodo della lista. Questo sarebbe anche il nodo prima del primo nodo, poiché la lista è circolare. Quindi, assicurati di mantenere (tail.next == current) durante la manipolazione dei puntatori. Ecco il nuovo metodo di inserimento:

public void insert(int data) { 
    Link newLink = new Link(data); 
    if (current == null) { 
     current = newLink; 
     tail = newLink; 
     newLink.next = newLink; // tail.next = current! 
    } else { 
     tail.next = newLink; // tail.next = current! 
     newLink.next = current; 
     current = newLink; // tail is unchanged, newLink is current 
    } 
} 

L'inserimento di valori dovrebbe giustamente metterli fuori ordine. Per mantenere l'ordine durante l'aggiunta, un metodo add dovrebbe essere utilizzato:

public void add(int data) { 
    this.insert(data); 
    this.advance(); 
} 

Ecco il codice per advance:

public void advance() { 
    if (current != null) { 
     tail = current; 
     current = tail.next; // tail.next = current! 
    } 
} 

Quando viene utilizzato come questo per creare liste ...

list1.add(1); 
list1.add(2); 
list1.add(3); 
list2.insert(3); 
list2.insert(2); 
list2.insert(1); 

... entrambe le liste sono ordinate 1-2-3 con 1 come corrente.

Answer 2

Usa Node current, int currentIndex, int size. Avere l'ultimo nodo del numero next al primo nodo dell'elenco (= circolare). Con l'indice corrente puoi camminare (size - 1) elementi per raggiungere il nodo precedente di current.

Answer 3

Poiché l'elenco collegato è circolare, non ci sarebbe il primo e l'ultimo elemento.

È possibile attraversare l'intero elenco a partire da qualsiasi nodo (corrente in questo contesto).

Quindi la classe Node avrebbe solo un riferimento successivo e CircularLinkedList avrà solo il riferimento corrente.

Spero che questo aiuti.
Buona fortuna.