C++链表append方法实现疑问：尾指针优化vs遍历追加谁更高效？

你的想法没有问题——仅为追加元素就遍历整个链表的做法确实效率低下，而你实现的带尾指针的链表append方法，在时间复杂度上有着本质的优势：

两种实现的时间复杂度对比 #

• 遍历到末尾的append：每次追加元素都需要从表头开始遍历，直到找到最后一个节点，时间复杂度为 O(n)（n为链表长度）。链表越长，这个操作耗时就越长。
• 带尾指针的append：通过维护的尾指针tail_可以直接定位到链表的最后一个节点，不需要遍历，时间复杂度为 O(1)，无论链表多长，追加操作的耗时都是恒定的。

你实现的代码里的小问题 #

仔细看你的append方法，最后几行有多余的操作：

tail_->next = node;
Node* temporary = tail_;
tail_ = node;
node = temporary;

这里的temporary变量和最后一行的node = temporary完全没有意义，因为node是局部变量，执行完这行后就会被销毁。正确的写法应该简化为：

tail_->next = node;
tail_ = node;

另外，当你追加第一个元素时，只设置了head_ = node，但tail_依然是nullptr，第二次追加时会进入第二个if分支，这部分逻辑是对的，但其实可以优化成更简洁的写法：

void append(const_reference data){
    Node* node = new Node;
    node->data = data;
    node->next = nullptr; 

    if(head_ == nullptr){
        head_ = node;
        tail_ = node; // 直接同时设置head和tail
        return;
    }
    
    tail_->next = node;
    tail_ = node;
}

这样可以避免第二个if分支的判断，逻辑更清晰。

两种实现的适用场景 #

遍历到末尾的append实现，一般只适用于没有维护尾指针的极简链表结构，这种结构节省了一个指针的存储空间，但牺牲了追加操作的效率。而维护尾指针的链表是更实用的设计，用极小的空间开销换来了O(1)的追加效率，在大多数需要频繁追加元素的场景下，都是更优的选择。

内容的提问来源于stack exchange，提问作者Eric Cardozo