对于addHead方法，为什么要检查尾==是否为空？

Question

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

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

在head中是对列表中第一个节点的引用。

在tail中是对列表中最后一个节点的引用。

( tail引用用于允许在固定时间内将元素添加到列表的末尾。)

空列表包含head == null和tail == null。

包含一个元素的列表包含head == tail、head != null和tail != null。

具有多个元素的列表具有head != tail、head != null和tail != null。

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

当向列表中添加第一个元素时，if(tail == null)是真的。对n的引用已经保存在head中，并且还需要用tail = head; (也可能：tail = n;)保存在tail中，以满足head == tail条件。

当向列表的head (addHead)添加其他元素时，tail不会更改，但是应该继续指向列表的最后一个节点。

Answer 2

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

为了有效地工作，列表维护一个指向其最后一个元素的tail指针。在没有指针的情况下可以这样做，但是每次都需要遍历整个列表来查找最后一个元素，将O(N)替换为O(1)。出于同样的原因，您的实现也有一个size计数器。

向以前空的列表中添加一个新元素时，需要调整tail指针，使其指向新创建的单个节点。

请注意，当添加到列表的前面时，您只需在列表之前为空时调整tail。在所有其他情况下，tail保持在原来的位置，只有head和size发生变化。