我正在研究如何在双向链表的第一个节点之前插入一个新节点.我对此操作所需的辅助节点以及执行操作的步骤顺序感到困惑.我会很感激如何解决这个问题,即我的insertBeforeFirst方法有什么问题.现在,该方法导致nullPointerException,我发现很难解决.(注意:这是以前帖子的后续内容.)
public DLL()
{
header = null ;
tail = null ;
}
...
DLL myList = new DLL() ;
DLLNode A = new DLLNode("Hello", null, null) ;
DLLNode B = new DLLNode("Hi", null, null) ;
...
myList.addFirst(A) ;
myList.insertBeforeFirst(B)
...
public void addFirst(DLLNode v)
{
v.pred = header ;
v.succ = tail ;
header = v ;
tail = v ;
}
...
public void insertBeforeFirst(DLLNode v)
{
DLLNode aux = v ;
aux.succ = header.succ ;
header = aux ;
DLLNode aux2 = aux.succ ;
aux2.pred = v ;
}
[编辑]
我已经按照Aaron的建议做了一个绘图,我有一点改进,因为我不再得到nullPointerException但是新模式是在第一个节点之后而不是之前插入的.所以我的绘画技巧也需要一些抛光我认为:)
public void insertBeforeFirst(DLLNode v)
{
v.succ = header.succ ; // point new node succ to current first node
header.succ = v ; //point header to new node
DLLNode aux = header.succ ; // auxiliary node for backward insertion
aux.pred = v ; // point auxiliary's pred backward to new node
}
[EDIT2]
看看MahlerFive的帖子,我现在看到为什么有些人可能会被我的标题和尾巴说话弄糊涂.我从这里得到它:"为了简化编程,在双向链表的两端添加特殊节点是很方便的:在列表头部之前的标题节点,以及紧跟在列表尾部之后的预告节点这些"虚拟"节点不存储任何元素" 源"
因此,对于启动器,我需要找到一种方法来正确实现这些虚拟节点,然后才能添加任何内容并进行正确的引用.这些DUMMY节点似乎需要一个不同的Node构造函数？它们可以由DLL默认构造函数实例化吗？
[EDIT3]
@MahlerFive,DLL构造函数将如下所示:
public DLL()
{
DLLNode Header = new DLLNode(null, null, null) ;
DLLNode Tail = new DLLNode(null, Header, null) ;
Header.succ = Tail ;
}
和我的方法类似,虽然我现在得到一个nullPointerException:
// insert z before v
public void addBeforeFirst(DLLNode v, DLLNode z)
{
DLLNode aux = v.pred ;
z.pred = aux ;
z.succ = v ;
v.pred = z ;
aux.succ = z ;
}
[EDIT4]
我正在取得进展.(很有感觉!)我同意MahlerFive的观点,DUMMY Header和Tail节点并不是解决这个问题的好方法.但正如已发表的关于此事的书中提到的那样,至少值得探讨.这是我的新代码(不使用虚拟节点):
...
// DLL Constructor
public DLL()
{
first = null ;
last = null ;
}
...
// example insert call
// B is the node in front of which i want to insert
l.insert("Ciao", B) ;
...
public void insert(String elem, DLLNode pred)
{
// make ins a link to a newly-created node with element elem,
// predecessor null, and successor null.
DLLNode ins = new DLLNode(elem, null, null) ;
// Insert ins at the insertion point in the
// forward SLL headed by first.
ins.pred = first ;
ins.succ = first ;
// let first be the the new node
first = ins ;
}
这需要微调,因为我还没有设置任何后向链接,但这是一个很好的起点.为了确保这个工作正常(至少在前进的方式),我添加了print语句,以便在我添加节点时打印出第一个和最后一个元素.确实他们已正确更新:
Hi
first: hi
last: hi
Ciao Hi
first: Ciao
last: hi
Moin Ciao Hi
first: Moin
last: hi
不要在你的大脑中完成这一切,坐下来五分钟,DLL在纸上绘制数据结构(和2-3对节点).
留下一个空白,在下面,绘制已经插入的节点的外观.
使用记号笔标记您需要进行的所有更改.给每个更改一个数字.
现在坐下来实施每个变化.
这听起来很乏味但它会帮助您深入了解正在发生的事情.这样,您只需要执行一次此操作.
如果您更喜欢纸和剪刀类型,请获取字符串,切出节点并将其粘贴到字符串的末尾.现在,您可以将字符串用作模型元素之间的"引用".
看来您的大部分困惑都在于如何header运作。它只是对列表中第一个节点的引用。此外，不需要“辅助”节点。
让我们按顺序看看您需要执行的步骤：
第 1 步：设置pred要插入的节点的 。
由于该节点将成为第一个节点，因此它后面将没有节点，所以你可以说v.pred = null;
步骤 2：设置succ要插入的节点的 。
我们的新节点需要指向旧的第一个节点。这就是混乱的地方。您执行以下操作：
v.succ = header.succ ; // point new node succ to current first node
但什么是header？它是对第一个节点的引用。通过说header.succ你是说你想要第一个节点的后继者，这是第二个节点。当你看到header“第一个节点”时，你会想到：
v.succ = header;
步骤3：将旧的第一个节点指向新节点
您已经正确执行了此步骤（请记住，认为 header 是“第一个节点”）：
header.succ = v ; //point header to new node
第 4 步：现在将新节点设为标头
header = v;
编辑（回应您的编辑#3）： 关于整个方法存在一些问题，我将在最后提出，但现在先将这些问题放在一边，并假设您需要以这种方式设置列表......
假设您将列表的第一个节点 (Header.succ) 作为 v 传递，让我们采取相同的步骤：
第 1 步：设置pred要插入的节点的 。
您希望新节点指向 Header。
v.pred = Header;
步骤 2：设置succ要插入的节点的 。
您希望新节点指向旧的第一个节点，即Header.succ
v.succ = Header.succ;
步骤3：将旧的第一个节点指向新节点
确保首先检查第一个节点是否存在（在我的第一篇文章中忘记了这一点）！
if (Header.succ != null) {
Header.succ.pred = v; // Header.succ is the first node, and you want to set its pred reference
}
第 4 步：现在将新节点设为第一个节点
Header.succ = v;
请注意，您甚至不需要，z因为您可以使用 到达第一个节点Header.succ。这意味着您不需要它作为参数。
现在，除了这些之外，您还应该考虑一些问题：
具有 pred 引用和数据字段的标头有什么意义？Tail 具有 succ 引用和数据字段有什么意义？
如果您想使用此链表并插入项目，那么只需为每个项目调用 add() 而不是 addFirst() 和 addBeforeFirst() 不是更好吗？如果你可以使用remove()方法，那么你必须跟踪列表是否为空，或者不知道要调用哪个方法，addFirst()或addBeforeFirst()，这有点难看。最好编写一个更通用的 add() 来为将要使用列表的用户处理这个问题。