时间戳

首页 > 解决方案 > 如何从数据结构中的单链表中删除尾部

data-structures - 如何从数据结构中的单链表中删除尾部

问题描述

我们不能轻易删除单链表的最后一个节点。即使我们维护一个直接指向链表最后一个节点的尾引用，我们也必须能够访问最后一个节点之前的节点才能删除最后一个节点。但是我们无法通过从尾部跟随下一个链接到达尾部之前的节点。访问该节点的唯一方法是从列表的头部开始，一直搜索列表。但是这样一系列的链接跳跃操作可能需要很长时间。

标签： data-structureslinked-listsingly-linked-list

解决方案

只需使用一个 for 循环，从i=0up to i<sizewheresize是该单链表中的节点数。下面代码中的条件next.getNext().getNext()==null检查下一个节点之后的节点是否具有null对下一个节点引用的引用，即tail然后它只是设置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保持到目前为止创建的节点数。

推荐阅读