我正在尝试删除单向链表中特定对象的第二次出现。
我的节点有以下代码：
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;
}
我使用相同的 methood，但它在我的方法中无法删除第二个外观。有什么帮助吗？
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;
}
您的问题将在此处找到(在几个地方(：
循环时，您将不断前进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)块之后，添加：
else {
found = false;
}
假设你解决了这个问题，这就是你最终会去的地方。举个例子：
[3] -> [4] -> [4] -> [5] -> [6]
在您的算法中，您将迭代此列表中的每个元素，如下所示：
通行证 1：
found = false
[3] -> [4] -> [4] -> [5] -> [6]
^
current
found = false
通行证 2：
found = false
[3] -> [4] -> [4] -> [5] -> [6]
^
current
found = true
通行证 3：
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的实现，如果对象不同，则几乎总是给出错误的结果。
类对象的 equals 方法实现了最具辨别力的方法 对象上可能的等价关系;也就是说，对于任何非空 引用值 x 和 y，此方法返回 true 当且仅当 x 和 y 引用同一个对象(x == y 的值为 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
添加到 pmac89 的答案中，最好将节点类泛化，以便您可以对数据类型使用正确的.equals()方法：
public class Node<T> {
Node<T> next;
T data;
...
}
从那时起，基本上您可以将Object替换为T，Node替换为Node<T>。创建节点时，请指定其类型。然后，假设你做了一个Node<String>.当您对数据调用.equals()时，它将使用 String.equals() 而不是 Object.equals() 。
正如 pmac89 所说，您不想调用Object.equals()的原因是，您正在检查它们是否是同一对象。您真正要检查的是它们是否具有相同的值。
编辑：
正如 Ryan J 所提到的，如果你的数据是 Object 的子类，它将默认为该类型的equals()实现(如果有的话(。
如果您不熟悉泛型教程，这里是它们：http://docs.oracle.com/javase/tutorial/java/generics/
所以问题是你的 Node 类....
在
public class Node {
...
Object data;
....
}
所以当你打电话时
if(current.getData().equals(temp.getData()))
在你的删除第二出现，它们将不相等。请记住，对象上的 Object.equal(( 是比较内存位置。没有任何列表项彼此相等，只有项本身。
编辑：你也想要
previous.setNext(current.getNext())//哎呀，这里也修复了一个错误!!
编辑2：此外，你没有排除你正在寻找的东西，所以你正在寻找它。要详细说明这一点，请这样想;
我有列表 1、2、3、4、4、5。它找到4次多少次？我猜一次。原因是每个列表项都有一个与另一个列表项不匹配的地址，因为这是说数据是一个在内存中分配位置的对象。因此，当您调用 Object.equals(someOtherObject( 时，您是在询问它们在内存中是否具有相同的位置。它们在内存中没有相同的位置。之所以在 removeSecondShow 期间只在检查中找到 1 秒的外观，是因为您再次浏览整个列表，而不是排除您要查找的节点。