如何从数据结构中的单向链表中删除尾巴

Question

我们不能轻易删除单向链表的最后一个节点。甚至 如果我们直接维护对列表最后一个节点的尾部引用，我们必须能够 访问最后一个节点之前的节点，以便删除最后一个节点。但我们 无法通过跟随尾部的下一个链接到达尾部之前的节点。唯一的 访问此节点的方法是从列表的头部开始并一直搜索 通过列表。但是这样的链路跳跃操作序列可能需要很长时间 时间。

Answer 1

删除单链表中的最后一个节点至少需要 O(n( 个时间复杂度。

但是，这可以通过使用双向链表在 O(常量(中完成。

Answer 2

只需采用从i=0到i<size开始的 for 循环，其中size是该单向链表中的节点数。下面代码中next.getNext().getNext()==null的条件检查下一个节点之后的节点是否有引用null下一个节点引用，即尾部，然后它只是在下一个节点引用中设置null。

请参阅下面的方法。

public void removeLast() {
Node<E> next=head;
for(int i=0; i<size; i++) {
if(next.getNext().getNext()==null) {
next.getNext().setNext(null);
tail=next.getNext();
size--;
}
next=next.getNext();
}
}

注意：getNext()返回下一个节点的引用。

由于getNext()返回Node类型引用，因此我们可以调用next.getNext().getNext()

size保留到目前为止创建的节点计数。