对于 addHead 方法，为什么要检查 tail == null？

Question

我正在学习 Java 数据结构课程，目前正在学习单向链表。在addHead的方法中，为什么我们需要检查tail == null？当为真时，为什么 tail = head？

public void addHead(T d){
  Node<T> n = new Node<>(d, head);
  head = n;
  size++
  if(tail == null)
   tail = head;
}

完整代码在这里：https://venus.cs.qc.cuny.edu/~ryba/cs313/linkedList/LinkedList.java

Answer 1

您的列表实现还允许追加到末尾。

为了使这项工作高效，列表维护了一个指向其最后一个元素的 tail 指针。没有那个指针也可以做到这一点，但是你每次都需要遍历整个列表来找到最后一个元素，从而附加 O(N) 而不是 O(1)。出于同样的原因，您的实现也有一个 size 计数器。

当您向先前为空的列表添加新元素时，tail 指针需要调整为指向新创建的单个节点。

注意，添加到列表前面时，只需要在之前列表为空时调整tail即可。在所有其他情况下，tail 保持原样，只有 head 和 size 发生变化。

Answer 2

In head 是对列表中第一个节点的引用。
In tail 是对列表中最后一个节点的引用。
（tail 引用用于允许在常数时间内将元素添加到列表的末尾。）

空列表有 head == null 和 tail == null。
只有一个元素的列表有 head == tail、head != null 和 tail != null。
包含一个以上元素的列表有 head != tail、head != null 和 tail != null。

addHead 为新元素 d 创建一个新节点 n，并引用存储在 head 中的列表中的下一个节点（其中对于第一个元素为空）。 head 被分配给新创建的节点 n.

的引用

将第一个元素添加到列表时，if(tail == null) 为真。对 n 的引用已经保存在 head 中，还需要用 tail = head;（也可能：tail = n;）保存在 tail 中以实现 head == tail条件。

当向列表的head添加额外的元素时（addHead），那么tail没有改变，但应该继续指向列表的最后一个节点.

对于 addHead 方法，为什么要检查 tail == null？

For addHead method why check if tail == null?

java

singly-linked-list