Java編程 - 循環鏈表

Question

我想寫一個java類CircularList其中包含了常用的節點內部類和實例變量：

Answer 1

提示...循環鏈表應該有一個和以前的，而不是第一個和最後。邏輯很重要

Answer 2

好的，我不會給你這個班的全部實施，而是我會給你一些建議。

1. 您不需要持有對最後一個元素的引用。放置一個上一個和下一個引用到你的節點，你的最後一個節點將是第一個。預覽

2. 除了圓形列表沒有結束的事實，它們與常規列表完全相同，但是在哪裏可以找到像這樣的最後一個項目：

   Node tmp = first;

   while（tmp.Next！= null） tmp = tmp.Next;

在循環鏈表的想法是這樣的：

Node tmp = first; 

while (tmp.Next != first) 
    tmp = tmp.Next; 

因爲你永遠也找不到指向空節點，除非該列表是空的。最後一個建議是，如果你需要實現一個索引，記得在一個循環表有作爲指標超出範圍，沒有這樣的事，因爲

list[count] = list[0] = list[count * k] 

記住這一點，因此在計算你的這些方法的指數可相當棘手。對於正面指標，主要思路是：

index = index % count; 

對於負值略有不同。我希望我能用我的話幫助你。如果你想要一個實現，我相信，如果你禮貌地問谷歌，應該有幾個:)

祝你好運！

Answer 3

我不確定你的問題是什麼，你似乎有所需的一切。鏈接列表和普通列表之間唯一的區別就是增加結尾。

在常規鏈接列表中，您將創建一個新節點並將最後一個元素指向該節點。在這種情況下，您將•Last節點中的指針更改爲指向新節點，並將新節點指向•First。

刪除工作方式與正常鏈接列表相同。每當你想刪除一個節點時，你會發現哪一個節點指向那個節點（先前，或者在刪除第一個節點的情況下，選中•Last），並指向被刪除節點指向的任何節點。

如果這不能解決您的問題，請告訴我，我會盡力幫助。

只注意到有人已經要求完全一樣的問題： Can I use java.util.LinkedList to construct a circular/cyclic linked list?

Answer 4

class Node { 
    int value; 
    Node next; 
    Node prev; 
    Node(int initialValue) { 
     value = initialValue; 
     next = null; 
     prev = null; 
    } 
    public int getValue() { 
     return this.value; 
    } 
} 

class NodeList { 
    Node pointer; 
    NodeList() { 
     pointer = null; 
    } 
    public void insertNode(int nodeValue) { 
     Node newNode = new Node(nodeValue); 
     if(pointer == null) { 
      newNode.next = newNode; 
      newNode.prev = newNode; 
     }else if(pointer.next == null && pointer.prev == null && pointer != null) { 
      newNode.next = pointer; 
      newNode.prev = pointer; 
      pointer.prev = newNode; 
      pointer.next = newNode; 
     } 
     else if(pointer != null) { 
      newNode.next = pointer.next; 
      newNode.prev = pointer; 
      pointer.next.prev = newNode; 
      pointer.next = newNode; 
     } 
     pointer = newNode; 
     System.out.println(「Successfully inserted : 」 + pointer.getValue()); 
    } 
    public void printRing(boolean direction) { 
     Node tempNode = pointer; 
     do { 
      System.out.println(「Value = 」 + tempNode.getValue()); 
      tempNode = direction ? tempNode.next : tempNode.prev; 
     } while(tempNode.value != pointer.value);  
    }  
}