圓形單鏈表

Question

我已經在Java中做了一些練習，現在我被困在這樣一個問題 - 我的列表工作不正確。我相信remove工作不正常，也許你可以幫助我（建議或代碼）以正確的方式實現一個圓形單獨鏈接列表。我不確定其他功能是否正常工作，但我盡力做到最好。

這裏是我的代碼：

import java.util.*; 


public class Node { 
    private Object value; 
    private Object nextValue; 

    private Node next; 


    public Node(int data) { 
     this.value = data; 
     this.next = null; 
    } 

    public Object getValue() { 
     return this.value; 
    } 

    public Node nextItem() { 
     return this.next; 
    } 

    public void setNextItem(Node nextItem) { 
     this.next = (Node) nextItem; 
     this.next.setValue(nextItem.getValue()); 
    } 


    public void setValue(Object arg0) { 
     this.value = arg0; 
    } 

} 

    ------------------------------------------------------------------- 

    import java.util.*; 



public class CircularList { 
    private Object[] array; 
    private int arrSize; 
    private int index; 
    private Node head; 
    private Node tail; 
    public CircularList() { 
     head = null; 
     tail = null; 
    } 



    public boolean add(Node item) { 

     if (item == null) { 
      throw new NullPointerException("the item is null!!!"); 
     } 


     if (head == null) { 
      head = item; 
      head.setNextItem(head); 
      arrSize++; 

      return true; 
     } 

     Node cur = head; 
     while(cur.nextItem() != head) { 
      if(cur.getValue() == item.getValue()) { 
       throw new IllegalArgumentException("the element already " + 
         "exists!"); 
      } 
      cur = cur.nextItem(); 
     } 

      head.setNextItem(item); 
      item.setNextItem(head); 
      arrSize++; 

      return true; 

    } 


    public Node getFirst() { 
     return head; 
    } 


    public void insertAfter(Node item, Node nextItem) { 

     if ((item == null) || (nextItem == null)) { 
      throw new NullPointerException("the item is nul!!!"); 
     } else if (this.contains(nextItem) == true) { 
      throw new IllegalArgumentException("the item already exists!"); 
     } 

     Node cur = head; 
     while(cur.nextItem() != head) { 
      if(cur.getValue() == item.getValue()) { 
       nextItem.setNextItem(item.nextItem()); 
       item.setNextItem(nextItem); 
      } else { 
       cur = cur.nextItem(); 
      } 
     } 

    } 


    public boolean remove(Node item) { 

     if(item == head) { 
      Node cur = head; 
      for(int i = 0; i < arrSize-1; i++) { 
       cur = cur.nextItem(); 
      } 

      head = head.nextItem(); 

      for(int i = 0; i < arrSize; i++) { 
       cur = cur.nextItem(); 
      } 
      arrSize--; 
      return true; 
     } 

     Node cur = head; 
     int counter = 0; 
     while(cur.nextItem() != head) { 
      if(cur == item) { 
       item = null; 
       cur = cur.nextItem(); 
       while(cur.nextItem() != head) { 
        cur.setNextItem(cur.nextItem().nextItem()); 
       } 
      return true;  
      } 
      cur = cur.nextItem(); 
     } 



     return false; 
    } 

    public int size() { 

     return arrSize; 
    } 

    public boolean contains(Object o) { 
     if ((o == null) && (arrSize == 0)) { 
      return false; 
     } 
     Node cur = head; 
     while(cur.nextItem() != head) { 
      if(cur.getValue() == o) { 
       return true; 
      } 
      cur = cur.nextItem(); 
    } 


     return false; 
    } 



} 

Answer 1

許多這些算法可以更簡單。

例子：

public boolean remove(Node item) { 
    Node current = head; 
    for(int i = 0; i < size; i++) { 
     if (current.getNext() == item) { 
      current.next = current.getNext().getNext(); 
      size --; 
      return true; 
     } 
     current = current.getNext() 
    } 
    return false; 
    } 

Answer 2

有很多種這裏超越了名單的問題。你似乎正在比較你的節點與==。此代碼將輸出'不匹配'。

Node n1 = new Node(5); 
Node n2 = new Node(5); 
if (n1 == n2) 
    System.out.println("objects match"); 
else 
    System.out.println("no match"); 

加（），它看起來像你永遠只能在列表中的兩個項目，所以

head.setNextItem(item); 
item.setNextItem(head); 

應該是這樣的：

cur.setNextItem(item); 
item.setNextItem(head); 

Answer 3

有很多事情在你的代碼中，以下是一些建議：

1. 在您的Node類中：Java命名約定：與setter應以「set」爲前綴的相同方式，getters應以「get：」作爲前綴，nextItem()應該確實爲getNextItem()。

2. 同樣在你的Node類中：就我所知，鏈表的節點的「next value」字段通常是對列表中下一個節點的引用，因此應該是Node，不只是任何對象。它應該按照您的方式工作，但使用明確的打字方式會更安全。 （如果使用「對象」確實是構建鏈表下一個節點的常用方法，請糾正我）

3. 在第一種情況下，當刪除頭部時：您正在循環列表達到最後的價值，大概是爲了重新設定新的頭「下一個價值」，但你實際上並沒有這樣做。你想這樣的事情：

   if (item == head) { 
   head = head.nextItem(); 
   for(int i = 0; i < arrSize-1; i++){ 
   cur = cur.nextItem();    
   } 
   } 
   cur.setNextItem(head); 
   

   我不知道你希望用第二個循環完成什麼。

4. 在第二種情況下remove()：我不確定你想要做什麼第二個while循環 - 重置整個列表中的所有鏈接？鏈表的整個意義在於讓它變得沒有必要。刪除鏈接列表中的節點實際上並沒有擺脫該對象（因此，您不必將item設置爲null）。相反，你簡單地說「圍繞」不想要的對象和「忽略」，從而有效從列表中刪除它，如：

最初的名單：

[ Value: A; Next: B ] --> [ Value: B; Next: C ] --> [ Value C; Next: D ] ... 

刪除節點B之後：

[ Value: A; Next: C ] --> [Value C; Next: D ] ... 

[ Value: B; Next: C ]仍然存在於內存中，但沒有指向它，所以它將在下一次垃圾回收循環中被刪除。

要實施：當您走過列表時，請保留對您訪問過的前一個節點的引用。然後，一旦你找到你要找的（用正確的比較，因爲托馬斯指出）的項目，你可以簡單地設置prev.setNextItem(cur.nextItem());（警告：未經測試的代碼）：

Node prev = head; 
    Node cur; 
    while ((cur = prev.nextItem()) != head) { 
    if (cur.equals(item)) { 
    prev.setNextItem(cur.getNextItem()); 
    return true; 
    } 
    } 

我希望這些技巧幫助你沿着正確的路徑。