从链接列表中删除所有出现的项目

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(); 
    } 
} 

输出：