java - 删除单链表中第二次出现的特定对象

Question

我正在尝试删除单链表中特定对象的第二次出现。

我的节点有以下代码:

public class Node {
    Node next;

    Object data;

    public Node(Object _data)
    {
        next = null;
        data = _data;
    }

    public Node(Object _data, Node _next)
    {
        next = _next;
        data = _data;
    }

    public Object getData()
    {
        return data;
    }

    public void setData(Object _data)
    {
        data = _data;
    }

    public Node getNext()
    {
        return next;
    }

    public void setNext(Node _next)
    {
        next = _next;
    }
}

这是我要删除的函数:

public void removeSecondAppear(Object data)
{
    Node temp = new Node(data);
    Node current = head;

    boolean found = false;

    for(int i = 1; i < size(); i++)
    {
        current = current.getNext();

        if(current.getData().equals(temp.getData()))
        {
            if(found == true)
            {
                // remove element
                current.setNext(current.getNext().getNext());
                listCount--;
                break;
            }
            else if(found == false)
            {
                found = true;
            }

        }
    }

}

由于某种原因，它不会删除该元素。找到它的方法工作正常，但我不知道为什么它不会删除该元素。我有一个类似的函数来删除特定索引的元素，效果很好:

public boolean remove(int index)
{
    if(index < 1 || index > size())
    {
        return false;
    }

    Node current = head;

    for(int i = 1; i < index; i++)
    {
        if(current.getNext() == null)
        {
            return false;
        }
        current = current.getNext();
    }

    current.setNext(current.getNext().getNext());

    listCount--;

    return true;
}

我使用相同的方法，但它在我的方法中无法删除第二次出现。有什么帮助我做错了什么吗？

public int indexOf(Object data)
{
    Node temp = new Node(data);
    Node current = head.getNext();

    for(int i = 0; i < size(); i++)
    {
        if(current.getData().equals(temp.getData()))
        {
            return i;
        }
        current = current.getNext();
    }

    return -1;
}

我的实现:

LinkedList LL = new LinkedList();

LL.add(1);
LL.add(2);
LL.add(3);
LL.add(4);
LL.add(4);
LL.add(5);
LL.removeSecondAppear("4");

我的添加方法:

public void add(Object data)
{
    Node temp = new Node(data);
    Node current = head;

    while(current.getNext() != null)
    {
        current = current.getNext();
    }

    current.setNext(temp);

    listCount++;
}

我的构造函数:

public LinkedList()
{
    head = new Node(null);
    listCount = 0;
}

Answer 1

您的问题将在这里(在几个地方)找到:

当你循环浏览时，你将不断前进current直到找到两个数据相等的实例，然后将其删除。您的删除将不起作用，因为您实际上并未删除所需的节点，它是您要删除的下一个节点，它不一定相等，因为您已经迭代了列表并丢失了之前的相等节点。

current = current.getNext();

if(current.getData().equals(temp.getData()))
{
    if(found == true)
    {
        // remove element
        current.setNext(current.getNext().getNext()); // this isn't actually removing 'current'...
        listCount--;
        break;
    }
    else if(found == false)
    {
        found = true;
    }

}

首先，在找不到相等的节点后，您不会重置找到的节点。之后if (equals) block ，添加:

else {
    found = false;
}

假设你解决了这个问题，这就是你最终的结果。举个例子:

[3] -> [4] -> [4] -> [5] -> [6]

在您的算法中，您将迭代此列表中的每个元素，如下所示:

第 1 遍:

found = false
[3] -> [4] -> [4] -> [5] -> [6]
 ^
 current 
 found = false

第二遍:

found = false
[3] -> [4] -> [4] -> [5] -> [6]
        ^
        current  
        found = true

第三遍:

found = true
[3] -> [4] -> [4] -> [5] -> [6]
               ^
              current  

当你到达这里时，你正在设置 current.next至current.next.next ，这有效地删除了 [5]从列表中，而不是 4。(因此，这也会导致您的 NPE...考虑当您到达列表末尾并且没有 next.next 时的影响)

您想要做的是找到重复节点的索引并调用现有方法以按索引删除元素，或者保留 previous节点来保存之前的节点的值 current当您删除时，设置 previous.setNext(current.getNext())这将有效删除 current .

其次，您已经使用了equals方法Object ，它使用最具辨别力的方法来确定相等性，因为它只会返回 true对于两个比较对象引用同一对象的情况。虽然这不一定是问题，但这可能会导致问题，具体取决于您存储的数据类型。调用equals任何对象上都将默认为 equals 最接近的实现对于该对象表示的实际数据类型，因此如果找不到，它将默认为 Object s 实现，如果对象不相同，几乎总是会给出错误结果。

The equals method for class Object implements the most discriminating possible equivalence relation on objects; that is, for any non-null reference values x and y, this method returns true if and only if x and y refer to the same object (x == y has the value true).

除此之外，您可能想要更改比较对象数据的方式，但我认为这不会真正给您带来太多问题。

最后，您可能想做一些null检查并运行你的循环算法，因为如果重复项位于列表的头部，这个算法将会出现问题，但这应该会让你指向正确的方向。

以下是一种方法的剪辑，可以帮助阐明我所说的内容:

public void removeSecondAppear(Object data)
{
    Node temp = new Node(data);
    Node current = head;
    Node previous = null;

    boolean found = false;

    while(current != null)
    {

        // for the sake of argument, let's say this will return true if you find equal data
        if( current.getData() != null && current.getData().equals(temp.getData()))
        {
            if(found)
            {
                // remove element
                previous.setNext(current.getNext());
                listCount--;
                break;
            }
            else
            {
                found = true;
            }

        }
        else {
            found = false;
        }

        previous = current;
        current = current.getNext();
    }

}

编辑:我已经使用OP的Node编写了LinkedList实现的一小部分。类定义并使用一个小测试来确保我的 removeSecondAppear方法有效。

public class LinkedList {
    private Node head;

    public LinkedList() {
        head = new Node(0);
    }
    public LinkedList(Node node) {
        head = node;
    }

    public void add(Node node) {
        Node ptr = head;
        while ( ptr.getNext() != null ) {
            ptr = ptr.getNext();
        }
        ptr.setNext(node);
    }

    ... /// added removeSecondAppear here, but left out to keep it short(er)

    // provided a print() method
}

使用此测试:

public class Test {
    public static void main(String[] args) {
        LinkedList list = new LinkedList(new Node(1));
        list.add(new Node(2));
        list.add(new Node(4));
        list.add(new Node(4));
        list.add(new Node(5));
        list.print();

        list.removeSecondAppearance(4);
        list.print();
    }
}

我的输出是:

1 2 4 4 5 
1 2 4 5