制作一个包含头节点和尾节点的链表

Question

我是数据结构的新手。当你创建一个包含头节点和尾节点的链表时，为什么我必须将新节点链接到尾节点？tail.next 链接到 newNode 还不够吗？

像这样：

public void add( Object data ) {
ListNode newNode = new ListNode( data );
    if ( isEmpty() ) {
        head = newNode;
    } else {
        tail.setNext( newNode );
    }
    tail = newNode;
    length = length + 1;
}

或者像这样：

if(head == null) {
    head = tail = newNode;
} else {
    tail.next = newNode;
    tail = newNode;
}

我查阅了 LinkedList 的基础知识，但我仍然不能很好地理解这一点。我不确定这如何让 head 链接到 tail 以及如果用 newNode 替换 tail ，tail 如何保留以前的值。你能向我解释一下吗？太感谢了！

Answer 1

头不与尾相连。您应该将它们视为单独的项目。head 指向列表的开头，tail 指向列表的结尾。假设您只是为了简单起见而添加而不删除。

头和尾开始为空（指向 NULL）。添加第一个 newNode（我们称之为 A）后，头和尾都设置为 A...因为它是唯一的条目，根据定义，它既是开始也是结束。

当您添加第二个节点 (B) 时，头保持不变，当前的 tail.next 设置为 B（它也设置 head.next）。之后尾部设置为 B。

添加第三个节点（C）后，头根本没有改变。但是tail.next被设置为C并且尾部移动到C。所以我们现在有A.next = B，B.next =C并且C.next为NULL。头指向A，尾指向C。