在Java中的双向链表中移除对象时出现问题。

huangapple go评论72阅读模式
英文:

Trouble with removing object in DoubleLinkedList in Java

问题

我在处理这个 remove(Object obj) 方法时遇到了困难。我尝试了许多不同的方法,而这是我能够达到的最接近的方法。被删除的项目是在传入对象之前的那个:

public boolean remove(Object obj)
{
    if (!this.contains(obj))
        return false;

    // 如果执行到这里,我们知道列表中某处包含了 obj
    // 在最后返回 true 之前,修改链接。
    else if (head.data.equals(obj))    // 它是否在开头?
    {
        this.removeFirst();
        return true;
    }
    else    // 不在开头,所以遍历列表
    {
        DLLNode<E> doomed = head;
        while (!doomed.data.equals(obj))
            doomed = doomed.next;

        // 现在找到了它,找到它前面的节点
        DLLNode<E> inFront = head;
        while (inFront.next != doomed)
            inFront = inFront.next;

        //
        // 这是问题所在以及我的解释
        //
        // 定位 obj 后面的节点的前一个定位器,将其设置为前面的节点的开头(prev)
        inFront.next.prev = inFront.prev;
        // 定位 obj 前面的节点的后一个定位器,将其设置为前面的节点的结尾(next)
        inFront.prev.next = inFront.next;

        // 还有...如果被删除的是尾部节点,我们必须重置尾部
        if (doomed == tail)
            tail = inFront;
    }
    return true;   // 找到了;链接已被更改
}

在我的测试中,当前的输出是删除与传入对象匹配的节点之前的节点。

谢谢。

编辑:只是为了确保我理解得正确,我的 inFront 变量是在 doomed 变量的左边吗?至少在我编写代码时是这样想的。例如:

DDL:1-->2-->3

我想要 remove(2)

这意味着 -

  • doomed = 2
  • inFront = 1

那么,inFront.next 是 1 的 'next' 节点吗?

编辑 2:我现在明白我认为的是正确的。有了这个认识,我进行了一些调整,并通过将以下内容从:

inFront.next.prev = inFront.prev;
inFront.prev.next = inFront.next;

更改为:

inFront.next = doomed.next.next.prev;

现在,在从左到右读取 DLL 时,与对象匹配的正确节点正在被删除。然而,在从右到左读取 DLL 时,该对象会在相同的位置重新出现。

英文:

I am struggling with this remove(Object obj) method. I have tried many different things, and this is the closest I can get. The item being deleted is the one before the object being passed in:

public boolean remove(Object obj)
{
	if (!this.contains(obj))
		return false;

	//if we get to here, we know that the list contains obj somewhere
	//change the links and return true at the end.
	else if (head.data.equals(obj))    //is it at the front?
	{
		this.removeFirst();
		return true;
	}

	else    //not at front, so traverse the list
	{
		DLLNode&lt;E&gt; doomed = head;
		while (!doomed.data.equals(obj))
			doomed = doomed.next;

		//now that it is found, find the node in front of it
		DLLNode&lt;E&gt; inFront = head;
		while (inFront.next != doomed)
			inFront = inFront.next;

                    //
                    // HERE IS THE PROBLEM &amp; MY EXPLANATION BEHIND IT
                    //
		// locate the prev locator of the following node of the obj and set it equal to the beginning (prev) of the node in front of the obj removed
		inFront.next.prev = inFront.prev;
		// locate the next locator of the preceding node of the obj and set it equal to the end (next) of the node in front of the obj removed
		inFront.prev.next = inFront.next;

		//also...if the one that was deleted was the tail, we must reset the tail
		if (doomed == tail)
			tail = inFront;
	}

	return true;   //found it; links have been changed

}

The current output in my tests is removing the node before the node that matches the object being passed in.

Thank you.

EDIT: Just to make sure I am understanding this correctly, my inFront variable is to left of the doomed variable? At least that is how I have been thinking of it when I write the code. For example:

DDL: 1-->2-->3

I want to remove(2).

That means -

  • doomed = 2
  • inFront = 1

So, inFront.next would be the 'next' node for 1?

EDIT 2: I now understand that what I thought is true. With that I made an adjustment and was able to get the same output by changing the following from:

inFront.next.prev = inFront.prev;
inFront.prev.next = inFront.next;

to

inFront.next = doomed.next.next.prev;

Now, the correct node that matched the object is being deleted when the DLL is read left to right. However, when reading the DLL from right to left, the object reappears in the same position.

答案1

得分: 1

<h3>Edit:</h3>
是的,查找元素的代码是正确的。但在删除部分,您曾认为`inFront`是前一个节点,因此它删除了错误的节点。
现在进行删除操作。在删除之前,您的情况如下:

[![删除之前的图像][1]][1]

现在,您需要将`inFront.next`设置为`doomed.next`:

    inFront.next=doomed.next;
您的列表现在如下所示:

[![在这里输入图像描述][2]][2]

下一步是将`doomed.next.prev`设置为`inFront`:

    doomed.next.prev=inFornt;
最终状态:

[![在这里输入图像描述][3]][3]
由于没有对被删除对象的引用,垃圾收集器将从内存中删除它。


  [1]: https://i.stack.imgur.com/FDqnl.png
  [2]: https://i.stack.imgur.com/H50TH.png
  [3]: https://i.stack.imgur.com/ySFYS.png
英文:

<h3>Edit: </h3>
Yes, the code to find the element is correct. But in the deletion part, you had thought inFront is the previous node, so it was deleting the wrong node.
Now for deletion. Before deleting you have something like this :

在Java中的双向链表中移除对象时出现问题。

Now, you have to set inFront.next to doomed.next:

inFront.next=doomed.next;

Your list looks like this now:

在Java中的双向链表中移除对象时出现问题。

The next step is to set doomed.next.prev to inFront:

doomed.next.prev=inFornt;

The final stat:

在Java中的双向链表中移除对象时出现问题。
Since there is no reference to the doomed object, the Garbage collector will delete it from memory.

答案2

得分: 0

解决了!这是一个愚蠢的错误。我没有考虑一个单独的情况。我明白,如果没有向这个社区提供所有信息,我不能期望任何人能够完全理解我的问题并提供帮助。这个问题是我的问题。为了公开羞愧自己并在将来说服他人提供必要的信息,我将解释问题和解决方案。

我的最初问题是被移除的节点是在所请求对象的前面。用这个方法解决了:

inFront.next = doomed.next;
doomed.next.prev = inFront;

然后,我没有考虑到在列表末尾移除一个对象需要一个特殊情况,以避免出现未被移除或破坏与其他节点的连接等问题。通过创建一个if语句解决了这个问题:

if (doomed != tail) {
    inFront.next = doomed.next;
    doomed.next.prev = inFront;
} else {
    inFront.next = null;
}

谢谢!我会确保将来更好地组织我的问题。

英文:

Solved! It was a stupid mistake. I was not considering a separate case. I understand that without all the information provided to this community, that I cannot expect anyone to be able to understand my problem fully and provide assistance. This one is on me. To publicly shame myself and persuade others in the future to provide necessary information, I will explain the problem and solution.

My initial problem was that the node being removed was the one in front of the requested object. Solved with this:

inFront.next = doomed.next;
doomed.next.prev = inFront;

Then, I was not considering the fact that an object removed at the end of the list would need a special case to avoid issues such as not removing, or destroying connections to other nodes. This was solved by creating an if statement:

if (doomed != tail) {
	inFront.next = doomed.next;
	doomed.next.prev = inFront;
} else {
	inFront.next = null;
}

Thank you! I'll be sure to better structure my questions in the future.

huangapple
  • 本文由 发表于 2020年10月18日 14:11:20
  • 转载请务必保留本文链接:https://go.coder-hub.com/64410266.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定