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

Remove all occurrences of item from a Linked List

提问by Forest Hughes

I've been working on this lab assignment for a few hours and can't understand why this code is not working. The question is to add the method int removeEvery(T item)that removes all occurrences of item and returns the number of removed items to a link list class that implements a link list interface.

我已经在这个实验室作业上工作了几个小时，但不明白为什么这段代码不起作用。问题是添加int removeEvery(T item)删除所有出现的项目并将删除的项目数返回到实现链接列表接口的链接列表类的方法。

This is my code: It removes some occurrences of the item, but not all of them.

这是我的代码：它删除了一些出现的项目，但不是全部。

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

Here is the remove method that was included in the LinkList class:

这是包含在 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

采纳答案by pgras

There is something special with your linked list, you can access next element with current.getNextNode but you delete using the element index. You should look in the rest of your implementation how this index is managed. Does the first element have index 0 or 1 (you start your loop with 1). What happens to the indexes of all elements when you remove one. Do the elements know their index ?

您的链表有一些特别之处，您可以使用 current.getNextNode 访问下一个元素，但您可以使用元素索引进行删除。您应该查看实现的其余部分如何管理此索引。第一个元素的索引是 0 还是 1（从 1 开始循环）。当您删除一个元素时，所有元素的索引会发生什么变化。元素知道它们的索引吗？

You could use something like

你可以使用类似的东西

  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;

回答by Jean Logeart

I think the problem you have comes from remove(i).

我认为您遇到的问题来自remove(i).

When you remove the i-thelement, the i+1-thelement becomes the i-thand so on: every element is shifted. Therefore if you need to remove 2 elements in your list that are at index jand j+1, removing the j-thelement calling remove(j)will shift the j+1-thelement at the index j. Hence removing that second element requires calling remove(j)again, and not remove(j+1).

当您删除i-th元素时，该i+1-th元素变为i-th等等：每个元素都被移动。因此，如果您需要删除列表中位于 indexj和 的2 个元素，则j+1删除j-th元素调用remove(j)将移动j+1-thindex 处的元素j。因此删除第二个元素需要remove(j)再次调用，而不是remove(j+1).

So you need to decrement iafter removing.

所以你需要i在删除后递减。

Since your removemethod actually decrements numberOfEntries, the condition on your whileloop is properly updated. So all you need to do is replace

由于您的remove方法实际上是 decrements numberOfEntries，因此您的while循环条件已正确更新。所以你需要做的就是更换

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

by

经过

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

---

---

Iterator.remove()

迭代器.remove()

This problem you are describing shows the usefulness of Iterator.remove()when using data structures from the JDK for going through an iterable collection and removing elements as you go through it.

您描述的这个问题显示了Iterator.remove()在使用 JDK 中的数据结构来遍历可迭代集合并在遍历时删除元素时的用处。

回答by Kshitij

After removing a node, as @Vakimshaar suggested, you need to decrement the ibecause the node at this index has been removed and there is a new node at the same index. In addition to that, you also need to update the currentNodereference as it would still be pointing to the node you've just removed, but it should really be pointing to the new node that has moved to this index.

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

So in the if (item.equals(currentNode.getData())){block you need to do the following:

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

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

With this, your code should correctly remove all occurrences.

有了这个，您的代码应该正确删除所有出现的内容。

回答by Jeevendra Singh

Here is a Java Code to delete all occurrences of an item from a linked list :

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

Output :

输出 ：

10 6 9

10 6 9