从链表中删除所有指定元素

Question

我已经花了几个小时来完成这个实验任务，但是无法理解为什么这个代码不起作用。问题是需要在一个实现了链表接口的类中添加方法int removeEvery(T item)，该方法删除所有出现的“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;
}

这是包含在 LinkList 类中的 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

- Forest Hughes

Answer 1

我认为你遇到的问题来自于remove(i)。

当你删除第i个元素时，第i+1个元素变成了第i个元素，以此类推：每个元素都被移动了。因此，如果你需要从索引为j和j+1的列表中删除2个元素，则调用remove(j)将使第j+1个元素移到索引j处。因此，删除第二个元素需要再次调用remove(j)，而不是remove(j+1)。

因此，在删除后需要将i减1。

由于你的remove方法实际上会将numberOfEntries减少，因此while循环的条件得到了适当的更新。所以，你只需要替换

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

通过

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

---

Iterator.remove()

这个问题展示了当使用JDK的数据结构遍历可迭代集合并在遍历过程中删除元素时，Iterator.remove() 的实用性。

- Jean Logeart

---

帮助减少集合中删除循环的混乱和错误的一种方法是通过反向循环集合，从最后一条记录开始。这样，您就不必考虑集合变短并手动添加额外的减量到循环计数器。 - jwenting

我之前尝试过这个，但是由于某种原因，当它到达项目的第一个出现时，它会删除列表中所有剩余的条目。编辑* 这是指将i递减。 - Forest Hughes

我正在尝试理解iterator.remove()。我是个新手。@jwenting，我不确定该怎么做，因为这不是一个双向链表。所以每个节点没有引用前一个节点。没有相应的“getPreviousNode（）”可以往回工作。 - Forest Hughes

@ForestHughes Iterator.remove() 方法会从底层集合中移除当前迭代器所选定的元素，使集合减少一个元素。Java集合框架会为您处理双向链表的问题，因此您无需担心。 - jwenting

Answer 2

你的链表有些特别，你可以通过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;

- pgras

---

太好了！这个可行。我之前尝试过一个版本，但从未让它正常工作。非常感谢。 - Forest Hughes

Answer 3

这里是一个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();
     }
}

输出：

10 6 9

- Jeevendra Singh

Answer 4

在删除节点后，如@Vakimshaar所建议的那样，您需要减少i，因为该索引处的节点已被删除，并且在相同索引处有一个新节点。除此之外，您还需要更新currentNode引用，因为它仍然指向您刚刚删除的节点，但实际上应该指向移动到此索引的新节点。

因此，在if (item.equals(currentNode.getData())){块中，您需要执行以下操作：

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

通过这个，你的代码应该能够正确地删除所有出现的内容。

- Kshitij