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

Question

所以我正在构建我自己的双向链表 class（不是为了家庭作业，只是想构建我自己的库供以后使用），我在实现 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

尝试删除 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

我认为最有趣的是，如果我尝试删除所有 -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

好像 9 和 713 只是这些方法不起作用的随机情况。我认为问题出在 findNode 和 deleteNode 方法中。测试 removeFirst 和 removeLast 方法表明它们可以完美地工作并提供正确的输出。任何 help/guidance 非常感谢，我已经为此苦苦挣扎了将近 6 个小时。

Answer 1

这一行有问题：

    if(ptr.data == data)

我想你的意思是：

    if (ptr.data.equals(data))

由于您不能在列表中存储 int，我假设您的元素类型是 Integer。 Java 为 -6 等常用整数缓存 Integer 个对象，因此当您要求删除所有 -6 时，您会得到对相同缓存 -6 的引用也在您的列表中的对象。然后与 == 进行比较会得到 true，因为 ptr.date 和 data 是对同一对象的引用。删除工作。 713 没有被缓存，所以当你要求删除它时，你得到一个 new Integer 对象。 ptr.data 和 data 是两个不同的相同对象的引用。 == 产生 false。不会删除任何内容。

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

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

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

Trouble with deleting nodes in Doubly Linked List

java

linked-list

data-structures

doubly-linked-list