在双链表中插入节点

Question

我无法理解将新节点连接到双链表的后半部分。我正在编写一个 add 方法，该方法接受要在其后插入新节点的节点。我的困难领域是理解在前一个节点链接被重定向到新节点后如何链接到下一个节点。

所以，这就是我

Chunk<E> newChunk= new Chunk<E>();

    newChunk.next= prevChunk.next;
    prevChunk.next= newChunk;

    newChunk.prev= newChunk.next.prev;
    newChunk.next.prev= newChunk;

的理解，因为 newChunk.next= prevChunk.next 命令复制了 prevChunk.next 的内存地址并将该值设置为 newChunk.next，然后prevChunk.next 被重置以链接到 newChunk。

因此，由于 prevChunk 是此处引用的唯一已在列表中的节点，并且下一个字段已重新路由到 newChunk，因此我在使用这些引用链接到下一个节点时是否走在正确的轨道上？

Answer 1

你是对的，但顺便说一句，大多数双链表不是循环的，因为最后一个节点的下一个不是第一个节点（与第一个节点的前一个不是最后一个节点相同）。
如果“prevChunk”是双链表中的最后一个节点，并且您在 prevChunk 之后添加 newChunk 作为链表中的最后一项，则

NewChunk.prev= newChunk.next.prev;

本质上是将 NewChunk 的前一个元素设置为 null 的前一个元素，这可能不是您想要的for

您可能想检查 previous.next 最初是否为 null。

Answer 2

像这样的东西应该有效。

Chunk<E> newChunk= new Chunk<E>();

    newChunk.next = prevChunk.next;
    newChunk.prev = prevChunk;
    prevChunk.next = newChunk;
    newChunk.next.prev = newChunk;

Answer 3

你那里的东西是正确的。然而，它有点难以理解（因此你的问题）。这是一个更直观的解决方案，应该有效并且更容易理解：

Chunk<E> newChunk = new Chunk<E>();
Chunk<E> nextChunk = prevChunk.next;

prevChunk.next = newChunk;
newChunk.prev = prevChunk;

nextChunk.prev = newChunk;
newChunk.next = nextChunk;

我创建了对链接列表中下一个节点的新引用。这可能与最后一个答案一样有效，因为它创建了新的参考，但应该帮助您理解解决方案。