删除双链表中的节点时遇到问题

So I'm building my own doubly linked list class (not for homework, just trying to build my own libraries for later use), and I'm having some difficulties implementing a removeAll method. Here is the relevant code (if you need more, let me know):

所以我正在构建我自己的双向链表类（不是为了做作业，只是为了以后建立我自己的库），而且我在实现removeAll方法时遇到了一些困难。这是相关代码（如果您需要更多，请告诉我）：

//ptr is a pointer node that moves through the list

//removes all nodes with type data
public void removeAll(T data) {
    while (findNode(data) != null) {
        deleteNode(findNode(data));
    } // end of while
} // end of removeAll method

//deletes single node
private void deleteNode(Node<T> del) {
    // del is head node 
    if (del.prevNode == null)
        removeFirst();
    // del is tail node
    else if (del.nextNode == null)
        removeLast();
    else {
        del.nextNode.prevNode = del.prevNode;
        del.prevNode.nextNode = del.nextNode;
        size--;
    } // end of if-else
} // end of deleteNode method

//returns node that matches criteria
private Node<T> findNode(T data) {
    ptr = head; // reset pointer
    while(ptr != null) {
        if(ptr.data == data)
            break;
        else {
            ptr = ptr.nextNode;
        } // end of if-else
    } // end of while
    return ptr;
} // end of findNode method

Output trying to remove 713 (I used integers for simplicity):

尝试删除713的输出（为简单起见，我使用了整数）：

[ 9 -6 -6 -6 -6 2 3 713 ] // this is just to show all elements in linked list
------------- // divider
[ 9 -6 -6 -6 -6 2 3 713 ]  // after trying to remove 713

What I think is most interesting is that if I try to remove all the -6's, the removeAll method works.

我认为最有趣的是，如果我尝试删除所有的-6，则removeAll方法可以正常工作。

[ -6 9 -6 -6 -6 2 3 713 -6 ] //added -6 to beginning and end
-------------
[ 9 2 3 713 ] //all -6's gone

It's as if 9 and 713 are just random cases where the methods don't work. I think the problem lies within the findNode and deleteNode methods. Testing the removeFirst and removeLast methods showed that they work flawlessly and give correct outputs. Any help/guidance is greatly appreciated, I've been struggling with this for close to 6 hours.

就像9和713只是方法不起作用的随机情况一样。我认为问题在于findNode和deleteNode方法。测试removeFirst和removeLast方法表明它们可以完美地工作并提供正确的输出。非常感谢任何帮助/指导，我一直在努力工作近6个小时。

1 个解决方案

#1

The issue is with this line:

问题在于这一行：

    if(ptr.data == data)

I think you meant:

我想你的意思是：

    if (ptr.data.equals(data))

Since you cannot store ints in your list, I have assumed that your element type is Integer. Java caches Integer objects for frequently used integers like -6, so when you ask to have all -6 removed, you get a reference to the same cached -6 object that is also in your list. Then comparison with == yields true because ptr.date and data are references to the same object. Deletion works. 713 is not cached, so when you ask to delete it, you get a new Integer object. ptr.data and data are references two distinct identical objects. == yields false. Nothing gets deleted.

由于您无法在列表中存储整数，因此我假设您的元素类型为Integer。 Java为常用的整数（如-6）缓存Integer对象，因此当您要求删除所有-6时，您将获得对列表中同一个缓存的-6对象的引用。然后与==进行比较得到true，因为ptr.date和data是对同一对象的引用。删除有效。 713未缓存，因此当您要求删除它时，您将获得一个新的Integer对象。 ptr.data和data是引用两个截然不同的相同对象。 ==产生错误。什么都没有删除。

PS You shouldn’t want to include a doubly linked list in your “own libraries for later use”. For one thing, you will never need a doubly linked list. The predefined ArrayList and ArrayDeque will serve the same purposes better in almost all cases. For another, the advantages of using classes from the standard library are huge. Those classes have proven useable through more than 20 years, and you’ve got folks to maintain them for you. Also other readers of your code will understand it more easily when you are using the standard APIs.

PS您不应该在“自己的库中包含双向链表”以供以后使用。首先，你永远不需要一个双向链表。在几乎所有情况下，预定义的ArrayList和ArrayDeque将更好地用于相同的目的。另一方面，使用标准库中的类的优势是巨大的。这些课程已经证明可以使用20多年了，你们有人为你们维护它们。当您使用标准API时，您的代码的其他读者也会更容易理解它。

Link: Question: Compare two objects with .equals() and == operator

链接：问题：使用.equals（）和==运算符比较两个对象

#1