Circular LinkedList w Javie

Question

Odbieram struktury danych, czytając książkę, a jedno z pytań, które prosi, to zbudować okrągłą listę z pojedynczym połączeniem, nie używając "pierwszych" wskaźników "pierwszych" &, ale raczej zezwalających na dostęp do niego za pomocą jednego odniesienia "bieżący". Nie jestem pewien, czy rozumiem to pytanie, zawsze uważałem, że potrzebuję przynajmniej pierwszego lub ostatniego. Oto moja implementacja, ale ma "pierwszy", nie wiem, jak sobie z tym poradzić. Czy możesz skomentować, w jaki sposób mogę dostosować mój kod, aby wyeliminować zależność od pierwszego?

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 

Wtedy oto lista sama:

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

Jeśli masz listę połączoną koliście, każdy węzeł wskazuje następny węzeł w pętli ciągłej. Więc nie ma ostatniego i nie pierwszego. W tej sytuacji potrzebujesz tylko jednego wskaźnika do struktury danych (które pytanie nazywa "bieżącym"), ponieważ możesz przejść całą listę, aż wrócisz do miejsca, w którym zacząłeś.

Jeden węzeł może wyglądać następująco:

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

Więc w tym środowisku, gdy dodasz swój pierwszy węzeł do listy, to „next” wskaźnik będzie wskazywać na siebie. Gdy dodasz drugi węzeł, każdy "następny" wskaże na drugi. Gdy dodasz trzeci węzeł, każdy z nich wskaże następny i prawdopodobnie zostanie to w jakiś sposób uporządkowane. Każdy dodatkowy węzeł zostanie wstawiony w odpowiednie miejsce w pętli.

Dobrym zastosowaniem dla takiej struktury danych byłby harmonogram, który jest powtarzany codziennie lub co godzinę. Wszystkie zdarzenia mogą być przechowywane na liście cyklicznej, a "bieżący" wskaźnik zawsze wskazuje na następny planowany termin.

Oczywiście podczas wyszukiwania listy takiej jak ta należy zachować odniesienie do pierwszego węzła. Jest to jedyny sposób, aby dowiedzieć się, czy przeszukałeś całą listę, ponieważ nie kończy się ona na zerowym "następnym" wskaźniku.

Edytuj: Jak wspomniano w (obszernych) komentarzach poniżej, wskaźnik "ogon" wydaje się być bardzo dobrym pomysłem tutaj dla operacji wstawiania. Oto oryginalna metoda, która napisałem, która została zmieniona 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; 
    } 
} 

Wskaźnik ogon zawsze zwrócić się do ostatniego węzła listy. Byłby to również węzeł przed pierwszym węzłem, ponieważ lista jest okrągła. Dlatego podczas manipulowania wskaźnikami należy zachować (tail.next == current). Oto nowa metoda wstawiania:

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 
    } 
} 

Wstawianie wartości powinno prawidłowo je wyłączać. Aby utrzymać porządek podczas dodawania, metoda add należy stosować:

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

Oto kod dla advance:

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

Kiedy stosować tak, aby tworzyć listy ...

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

... Obie listy są sortowane 1-2-3 z 1 jako bieżącym.

Answer 2

Zastosowanie Node current, int currentIndex, int size. Niech ostatni węzeł next wskaże pierwszy węzeł listy (= okrągły). Przy bieżącym indeksie możesz przejść elementy (rozmiar - 1), aby osiągnąć poprzedni węzeł: current.

Answer 3

Ponieważ połączona lista jest okrągła, nie byłoby pierwszego ani ostatniego elementu.

Możesz przechodzić całą listę zaczynając od dowolnego węzła (bieżący w tym kontekście).

Tak więc klasa Node będzie miała tylko następną referencję, a CircularLinkedList będzie miała tylko bieżące odniesienie.

Mam nadzieję, że to pomoże.
Powodzenia.