java - 在列表开头添加混淆

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

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

1) 现在回答你的问题，因为它听起来“当将数字插入到空列表时，为什么我们将第一个节点声明为 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 的同一 Node 对象。创建双向链表时，您不必在头部和尾部之间设置任何链接，反之亦然。

DLL 中的双向链接以双边尖括号的形式直观地表示，如下所示:

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

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