将中间节点插入双向链表[如何]

我似乎在这个任务的圈子。即使画出来似乎也没有给我一个工作的解决方案。有人能帮我找到我的思维过程在哪里崩溃吗？将中间节点插入双向链表[如何]

// method receives node ins to be inserted 
// and node prev in front of which ins should be inserted 
public void insertIntermediate(DLLNode ins, DLLNode prev) 
{ 
    ins.pred = prev ; // update node ins' predecessor information 
    ins.succ = prev.succ ; // update node ins' successor information 
    prev.succ = ins ; // update list's information 
    prev.succ.pred = ins ; // update list's information 
}

[EDIT2]（除去EDIT1以减少混乱）

@Andrew，确定我发现：什么是错误的与上述是线的顺序3 & 4：

第3行导致我无法访问prev.succ.pred。

通过交换两条线我解决了这个问题。感谢提示！

ADD-ON问题：

我碰到虽然另一个奇怪的问题，这就是为什么我失去了这么多的时间来寻找解决方案：如果我再重新插入一个已经存在的元素，由于某种原因，整个事情进入无限循环，当我打印它 ...例如

myList.addBeforeFirst(B) ; 
myList.addBeforeFirst(B) ;

导致一个循环，而：

myList.addBeforeFirst(B) ; 
myList.addBeforeFirst(C) ;

工作正常

这里的方法：

public void addBeforeFirst(DLLNode ins) 
{ 
    ins.succ = first ; 
    ins.succ.pred = ins ; 
    first = ins ; 
}

和节点：

DLLNode B = new DLLNode("Hi", null, null) ; 
DLLNode C = new DLLNode("Salut", null, null) ;

为什么会这样呢？

来源

2011-03-21 raoulbia

这是一个加倍链接列表，是吗？那是什么意思？确保您正在更新全部的相关链接，并按正确顺序排列。另外，确保所有相关的节点都存在。

编辑：

让我们通过您的语句秩序。

开始之前，您有prev，其属性succ指向后继节点。（或者是否可以有例外情况？如果存在，您将如何处理这种例外情况？）应该与prev相同，前提条件是prev.succ指向后继节点。

现在，您的前两条语句设置为ins.pred和ins.succ。这基本上是正确的想法，但看到我上面的问题。

现在，您将prev.succ设置为ins。关注这个声明。你有没有现在丢失的信息？究竟做了以下说明吗？这是你的意图吗？

我认为这是我可以做的最好的事情，而不必完全放弃解决方案。

编辑的无限循环问题：

您遇到的问题是由价值和传递参数通过引用传递参数之间的区别。因为你是通过引用传递的，所以你传递了两次对同一个对象（B）的引用。这意味着你最终做了以下内容：

第一次调用：

B.succ = first; 
B.succ.pred = B; /* why not just first.pred = ins? */ 
first = B;

现在，首先是设置为B.因此，第二个电话，使用B：

B.succ = B; 
B.succ.pred = B; /* so, now B is its own pred and succ */ 
first = B; /* no change here */

所以，现在，首先是B，first.succ是B，first.succ.succ是B等，因此是无限循环。

来源

2011-03-21 22:03:50 Andrew

对我来说，似乎我涵盖了所有四个链接：2之间prev和插件（前进和后退）和2之间插件和prev.succ（前进和后退），所以不知道缺少什么？ – raoulbia 2011-03-21 22:28:39

@Baba我会编辑我的答案，因为这可能会有点冗长的评论。 – Andrew 2011-03-21 22:35:15

嗨安德鲁，看我的编辑 – raoulbia 2011-03-21 23:05:20

将中间节点插入双向链表[如何]

回答

相关问题