如何在双向链表的第一个节点之前插入新节点？

Question

我正在研究如何在双向链表的第一个节点之前插入新节点。我对该操作所需的辅助节点以及执行该操作的步骤序列感到困惑。我将不胜感激有关如何解决此问题的提示，即我的 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 ;
}

[编辑]

我听从了亚伦的建议并做了一张图，我有了一点改进，因为我不再得到 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 的帖子，我现在明白为什么你们中的一些人可能会对我的标题和尾部谈话感到困惑。这是我从这里得到的：“为了简化编程，在双向链表的两端添加特殊节点很方便：在列表头之前添加一个 header 节点，和列表尾部后面的 trailer 节点。这些“虚拟”节点不存储任何元素” source

因此，对于初学者来说，我似乎需要找到一种方法来正确实现这些虚拟节点，然后才能添加任何内容并进行正确的引用。这些虚拟节点似乎需要不同的节点构造函数？它们可以由 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 的观点，即虚拟标头和尾节点并不是解决此问题的好方法。但正如一本已出版的关于此事的书中提到的那样，它至少值得探索。这是我的新代码（不使用虚拟节点）：

...

// 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 ;
}

这需要微调，因为我还没有设置任何向后链接，但这是一个很好的起点。为了确保其正常工作（至少以正向方式），我添加了打印语句以在添加节点时打印出第一个和最后一个元素。事实上，它们已正确更新：

Hi
first: hi
last: hi

Ciao Hi
first: Ciao
last: hi

Moin Ciao Hi
first: Moin
last: hi

Answer 1

不要在大脑中完成这一切，而是坐下来五分钟，在纸上绘制数据结构（DLL 和 2-3 个节点）。

留下一个间隙，并在其下方画出已插入节点后的外观。

用记号笔标记您需要进行的所有更改。给每个变化一个数字。

现在坐下来实施每一项改变。

这听起来很乏味，但它将帮助您深入了解正在发生的事情。这样，您只需执行一次此操作。

如果您更喜欢纸和剪刀类型，请拿几段绳子，剪掉节点并将便利贴粘在绳子的末端。现在您可以使用字符串作为模型元素之间的“引用”。

Answer 2

看来您的大部分困惑都围绕 header 的工作原理。它只是对列表中第一个节点的引用。此外，不需要“辅助”节点。

让我们按顺序查看需要执行的步骤：

第 1 步：设置要插入的节点的 pred。

由于该节点将成为第一个节点，因此它后面将没有节点，因此您可以说 v.pred = null;

第 2 步： 设置 succ您要插入的节点的 。

我们的新节点需要指向旧的第一个节点。这就是混乱的地方。您执行以下操作：

v.succ = header.succ ； // 将新节点 succ 指向当前第一个节点

但是 header 是什么？它是对第一个节点的引用。通过说 header.succ 您是在说您想要第一个节点的后继节点，即第二个节点。当您看到 header 时，只需想到“第一个节点”，您就会想到：

v.succ = header;

第 3 步： 指向旧节点第一个节点回到新节点

您已经正确执行了此步骤（记住，认为 header 是“第一个节点”）：

header.succ = v ; //将标头指向新节点

第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() 来为将要使用列表的用户处理这个问题。