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

Question

我正在学习Java数据结构课程，目前正在学习单链表。在addHead的方法中，为什么我们需要检查tail==null？如果是真的，为什么尾巴=头？

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

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

为了有效地执行此操作，列表维护一个指向其最后一个元素的尾部指针。不使用该指针也可以这样做，但是每次都需要遍历整个列表来查找最后一个元素，将O（1）改为附加O（N）。出于同样的原因，您的实现也有一个大小计数器。

将新元素添加到以前的空列表时，需要将指针调整为指向新创建的单个节点。

请注意，当添加到列表的前面时，您只需在列表之前为空时调整尾部。在所有其他情况下，尾部保持不变，只有头部和大小发生变化。

Answer 2

在头中，是对列表中第一个节点的引用
Intail是对列表中最后一个节点的引用
（尾部引用用于允许在固定时间内向列表末尾添加元素。）

空列表具有头==null和尾==null
具有一个元素的列表具有头==尾，头！=null和tail！=空
包含多个元素的列表具有头！=尾部，头部null和tail！=空。

添加头为新元素创建一个新节点，引用列表中存储在头中的下一个节点（第一个元素为空）。头被指定为新创建的节点的引用。

将第一个元素添加到列表时，if（tail==null）为true。对n的引用已经保存在head中，还需要用tail=head保存在tail中（也可以是：tail=n；）以满足head==tail条件。

将其他元素添加到列表的头（addHead）时，尾不会更改，但应继续指向列表的最后一个节点。