添加在列表混淆的开头

Question

这是在双向链表开头添加的代码：

public void insertFirst(long dd)  // insert at front of list
{
      Link newLink = new Link(dd);   // make new link

      if( isEmpty() )                // if empty list,
         last = newLink;             // newLink <-- last
      else
         first.previous = newLink;   // newLink <-- old first
      newLink.next = first;          // newLink --> old first
      first = newLink;               // first --> newLink
}

我不明白的是为什么当列表 isEmpty() 时 last 和 first 都被分配给 newLink？那么它是不是看起来像这样，例如3->3（只是一个数字3的例子）。我真的很困惑为什么他们都被分配到新节点。

Answer 1

拿一支sheet和一支笔，你就会明白。

如果您有一个空列表 []，调用 insert(dd) 时会发生以下情况：

Link newLink = new Link(dd);
// first -> null, last -> null, newLink = {value = dd, previous -> null, next -> null}
last = newLink;
// first = null, last -> newLink, newLink = {value = dd, previous -> null, next -> null}, list = chain from first = []
newLink.next = first;
// first -> null, last -> newLink, newLink = {value = dd, previous -> null, next -> first -> null}, list = chain from first = []
first = newLink;
// first -> newLink, last -> newLink, newLink = {value = dd, previous -> null, next -> null}, list = chain from first = [newLink]

Answer 2

newLink 将被分配到 first 因为你在你的 else 中没有块 ({...})，所以只有 first.previous = newLink 将有条件地执行，以下语句将是无条件的。

请注意，在这两种情况下，您实际上都希望 first 指向 newLink，否则您将无法从头开始迭代。

Answer 3

我将我的回答分为两个合乎逻辑的原因，其中一个或两个 将回答您的疑问。

1) 现在来回答你的问题 "When inserting a number to an empty list why do we declare the first Node as both head & tail?"

第二轮插入数字有很多歧义。 会先插入下一个数字吗？或者最后？还是在特定位置？ 以下代码片段将回答您的问题，

Line 1: insertFirst(3); //Sets Node containing 3 as both head and tail. No magic tricks

现在可以根据用户的选择调用以下函数之一：

a) Line 2: insertFirst(4);
//Sets Node containing 4 as head and the previous head(3) as it's dual link.
//Notice that there is no need to update the tail as Node containing 3 is already a tail.
b) Line 2: insertLast(4);
//Sets Node containing 4 as tail and the previous tail(3) as it's dual link.
//Notice that there is no need to update the head as Node containing 3 is already a head.

这样，通过将第一个节点指定为 head 和 tail.

，可以轻松解决即将到来的歧义

2) 首先，它是一个双向链表，而不是循环链表 正如你在问题中所展示的 single node(3) 作为 3<>3 将 head 和 tail 描述为单独的节点。请注意，head 和 tail 指的是同一个包含值 3 的节点对象。创建双向链表时，您不必在头部和尾部之间设置任何链接，反之亦然。

DLL 中的双向链接以双边 angular 括号的形式直观表示如下：

head<>node1<>node2<>node3<>tail

注意头部和尾部，都没有连接到 DLL 中的任何链接。如果这部分回答了你的疑问，问题本身就有缺陷。但是，如果您进一步质疑如何在循环列表中维护显示节点的轨迹，请使用 size 变量，该变量会在调用每个函数时自行更新。

添加在列表混淆的开头

Adding in the beginning of the list confusion

java

doubly-linked-list