如何在一個圓形單鏈表中實現刪除和搜索？

我想實現一個刪除（節點x）方法和一個搜索（E鍵）方法，但我不明白我如何可以使循環遍歷列表？我試圖寫入刪除方法。以下是我的代碼：如何在一個圓形單鏈表中實現刪除和搜索？

public class CircularSinglyLinkedList<E> { 

    private Node<E> head; 
    private Node<E> tail; 

    private class Node<E> { 
     public final E key; 
     public Node<E> next; 

     private Node(E key) { 
      this.key = key; 
     } 
    } 

    public void insert(Node<E> x) { 
     x.next = head; 
     tail.next = x; 
     head = x; 
    } 

    public void delete(Node<E> x) { 
     Node<E> y = head; 
     while(y != x && y.next != head) { 
      y = y.next; 
     } 
     if(y.next == x) { 
      y.next = x.next; 
      x.next = null; 
     } 
    } 

    public E search(E key) { 

    } 

}

來源

2015-06-21 Ali Mustafa

從頭部或指定節點搜索到結尾，1乘1. –

但是我會在循環中使用什麼條件？ –

@如果你試圖找到一個元素，那麼做比較。 –

您將需要遍歷循環列表以刪除和搜索節點。我希望下面的代碼會有幫助：

private Node delete(Node x) { 
    Node node = head; 
    do { 
     if (node.next.element == x.element) { 
      Node n = node.next; 
      node.next = n.next; 
      if (n == head) { // removal of head 
       head = node; 
      } 
      return n; 
     } 
     node = node.next(); 
    } while(node != head); 
    return null; 
}

它會搜索節點x並將其刪除。雖然你沒有發佈你的課程結構，但我仍然希望你能做出相應的改變。

該函數將拒絕刪除最後一個元素（當列表只包含一個元素時），如同在循環鏈表中我假設最後一個元素的頭部爲下一個元素。

來源

2015-06-21 13:10:08

感謝您的回答。你能不能告訴我，如果有一種優雅或有效的方法來修改函數也刪除最後一個元素？ –

提示：最後一個節點的'next'將指向'head'。 –

您需要在Node類中實現equals和hashCode方法。

while(!y.equals(x) && !y.next.equals(head)) { 
    y = y.next; 
}

來源

2015-06-21 13:10:18

我想，你需要的是改變你的循環來，同時後置條件循環，就像這樣：

Node<E> y = head; 
do { 
    if (y.next == x) { 
     y.next = x.next; 
     x.next = null; 
     return; 
    } 
    y = y.next; 
} while (y != head);

這也將是更好地實現您的search方法節點搜索（使其返回Node<E>）。

順便說一句，delete方法需要Node<E>作爲參數，但將難以從外部調用它，因爲調用者不能從任何地方得到參考Node<E>：head和tail是私有的，search回報E，不Node<E> 。

來源

2015-06-21 13:10:22 hotkey

如何在一個圓形單鏈表中實現刪除和搜索？

回答

相關問題