從鏈接列表中刪除所有出現的項目

Question

我一直在做這個實驗分配幾個小時，並不明白爲什麼這段代碼不工作。問題是添加方法int removeEvery(T item)，該方法刪除所有出現的項目，並將已刪除項目的數目返回到實現鏈接列表界面的鏈接列表類。

這是我的代碼：它刪除某些項目的事件，但不是全部。

public int removeEvery(T item){ 
int index = 0; 
Node currentNode = firstNode; 
for(int i = 1; i <= numberOfEntries; i++) 
    { 
    System.out.println(currentNode.getData()); 
     if (item.equals(currentNode.getData())){ 
      index++; 
      remove(i);} 
     else{ 
      currentNode = currentNode.getNextNode();} 
    } 
     if(index != 0) 
     return index; 
    return -1; 
} 

這裏是被列入鏈表類remove方法：

public T remove(int givenPosition) 
{ 
    T result = null;     // return value 

    if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) 
    { 
    assert !isEmpty(); 
    if (givenPosition == 1)  // case 1: remove first entry 
    { 
     result = firstNode.getData();  // save entry to be removed 
     firstNode = firstNode.getNextNode(); 
     if (numberOfEntries == 1) 
      lastNode = null; // solitary entry was removed 
     } 
     else       // case 2: givenPosition > 1 
     { 
      Node nodeBefore = getNodeAt(givenPosition - 1); 
      Node nodeToRemove = nodeBefore.getNextNode(); 
      Node nodeAfter = nodeToRemove.getNextNode(); 
      nodeBefore.setNextNode(nodeAfter); // disconnect the node to be removed 
      result = nodeToRemove.getData(); // save entry to be removed 

      if (givenPosition == numberOfEntries) 
       lastNode = nodeBefore; // last node was removed 
    } // end if 

    numberOfEntries--; 
    } // end if 

    return result;     // return removed entry, or 
            // null if operation fails 
} // end remove 

Answer 1

你的鏈表有一些特殊之處，你可以用current.getNextNode訪問下一個元素，但是你可以使用元素索引來刪除。您應該查看實施的其餘部分如何管理此索引。第一個元素是否具有索引0或1（您從1開始循環）。刪除一個元素時，所有元素的索引會發生什麼變化。元素是否知道他們的索引？

您可以使用類似

int deletedNodes = 0; 
    int currentIndex = 0; // check if 1 or 0 
    currentNode = fist; 
    while(currentNode != null){ // I guess lastNode.getNextNode() is null 
    if(//should remove){ 
     remove(currentIndex); 
     deletedNodes++ 
     // probably no need to change the index as all element should have been shifted back one index 
    } else { 
     currentIndex++; // index changes only if no node was deleted 
    } 
    currentNode = currentNode.getNextNode(); // will work even if it was deleted 
    } 
return deletedNodes; 

Answer 2

我認爲你有問題來自remove(i)。

當您刪除i-th元素時，i+1-th元素變爲i-th依此類推：每個元素都被移位。因此，如果您需要刪除列表中索引爲j和j+1的2個元素，則刪除調用remove(j)的j-th元素將會將j+1-th元素移動到索引j處。因此刪除第二個元素需要再次調用remove(j)，而不是remove(j+1)。

所以你需要在刪除後減去i。

由於您的remove方法實際上遞減numberOfEntries，因此您的while循環中的條件已正確更新。因此，所有你需要做的就是通過

if (item.equals(currentNode.getData())) { 
    index++; 
    remove(i--); 
} 
// update the current node, whether removing it or not 
currentNode = currentNode.getNextNode(); 

---

Iterator.remove（）

此問題，您正在使用的數據時，描述節目Iterator.remove()用處更換

if (item.equals(currentNode.getData())) { 
    index++; 
    remove(i); 
} 
else { 
    currentNode = currentNode.getNextNode(); 
} 

來自JDK的結構用於通過可迭代集合並在您通過它時刪除元素。

Answer 3

刪除節點後，作爲@Vakimshaar建議，你需要遞減i因爲該指數在節點已被刪除，有一個新的節點在同一指數。除此之外，還需要更新currentNode引用，因爲它仍然指向剛刪除的節點，但它應該確實指向已移至此索引的新節點。

所以在if (item.equals(currentNode.getData())){塊，你需要做到以下幾點：

Node nextNode = currentNode.getNextNode(); 
index++; 
remove(i--); 
currentNode = nextNode; 

有了這個，你的代碼應該正確刪除所有出現。

Answer 4

這裏是一個Java代碼從鏈接列表中刪除項目的所有實例：

public class LinkedList{ 
    Node head; 
    class Node{ 
     int data; 
     Node next; 
     Node(int d){data =d; next = null;} 
    } 

    public void push(int new_data){ 
     Node new_node = new Node(new_data); 
     new_node.next = head; 
     head = new_node; 
    } 

    public void insertAfter(Node givenNode, int new_data){ 
     if(givenNode == null) 
      System.out.println("Given node cannot be empty"); 

     Node new_node = new Node(new_data); 
     new_node.next = givenNode.next; 
     givenNode.next = new_node; 
    } 

    public void append(int new_data){ 
     Node new_node = new Node(new_data); 
     if(head == null) 
      head = new_node; 

     else{ 
     Node last = head; 

     while(last.next != null) 
      last = last.next; 

     last.next = new_node; 
    } 
    } 

    public void printList(){ 
     Node temp = head; 

     while(temp != null){ 
      System.out.println(temp.data + " "); 
      temp = temp.next; 
     } 
    } 

    void deleteNode(int key){ 
     // Store head node 
     Node temp = head, prev=null; 
     // If head node itself holds the key or multiple occurrences of key 
     while(temp != null && temp.data == key){ 
      head = temp.next; 
      temp = head; 
     } 
     // Delete occurrences other than head 
     while(temp != null){ 
      // Search for the key to be deleted, keep track of the 
      // previous node as we need to change 'prev.next' 
      while(temp != null && temp.data != key){ 
       prev = temp; 
       temp = temp.next; 
      } 
      // If key was not present in linked list 
      if(temp == null) return; 
      // Unlink the node from linked list 
      prev.next = temp.next; 
      //Update Temp for next iteration of outer loop 
      temp = prev.next; 
     } 
    } 

    public static void main(String[] args){ 
     LinkedList llist = new LinkedList(); 

     llist.push(6); 
     llist.append(7); 
     llist.append(7); 
     llist.append(7); 
     llist.append(9); 
     llist.push(10); 
     llist.deleteNode(7); 
     llist.printList(); 
    } 
} 

輸出：