LinkedList的pop_back()方法问题：尾节点删除后前驱节点next未置空

核心问题 #

你当前的pop_back()实现存在两个关键问题：

• 仅删除了mLast节点并置空，但原倒数第二个节点的next指针仍指向已释放的内存（即你所说的垃圾值），会导致后续遍历（如operator<<）触发未定义行为
• 单向链表的特性决定，要找到尾节点的前一个节点必须从表头遍历到表尾，这是你觉得效率低的根本原因

方案1：修复单向链表的pop_back（保证正确性，时间复杂度O(n)） #

如果坚持使用单向链表，必须通过遍历找到倒数第二个节点，才能正确更新指针逻辑。你的尝试方向正确，可优化代码如下：

template<typename T>
inline T LinkedList<T>::pop_back()
{
    if (isEmpty())
        throw std::out_of_range("LinkedList is empty"); // 用异常替代返回NULL，符合C++规范

    T lastValue = mLast->value;

    // 情况1：链表仅含一个节点
    if (mFirst == mLast)
    {
        delete mFirst;
        mFirst = mLast = nullptr;
    }
    // 情况2：链表含多个节点，遍历找倒数第二个节点
    else
    {
        Node* current = mFirst;
        // 找到next指向mLast的节点
        while (current->next != mLast)
        {
            current = current->next;
        }
        delete mLast;
        mLast = current;
        mLast->next = nullptr; // 关键：清空新尾节点的next指针
    }

    decreaseSize();
    return lastValue;
}

方案2：改为双向链表（实现O(1)时间的pop_back） #

要彻底解决效率问题，唯一办法是给节点增加前驱指针，改为双向链表。这样pop_back时可直接通过mLast->prev找到前一个节点，无需遍历：

修改后的核心代码片段 #

template<typename T>
class LinkedList
{
public:
    struct Node
    {
        T value;
        Node* next = nullptr;
        Node* prev = nullptr; // 新增前驱指针
    };

    Node *mFirst = nullptr;
    Node *mLast = nullptr;

    // ... 其他成员保持不变

    template<typename T>
    inline void LinkedList<T>::push_back(const T& value)
    {
        Node *node = new Node{value, nullptr, nullptr};

        if (!isEmpty())
        {
            mLast->next = node;
            node->prev = mLast; // 设置新节点的前驱
            mLast = node;
        }
        else
        {
            mLast = mFirst = node;
        }
        increaseSize();
    }

    template<typename T>
    inline T LinkedList<T>::pop_back()
    {
        if (isEmpty())
            throw std::out_of_range("LinkedList is empty");

        T lastValue = mLast->value;
        Node* prevNode = mLast->prev;

        delete mLast;
        mLast = prevNode;

        // 若链表仅剩的最后一个节点被删除，同步置空mFirst
        if (mLast == nullptr)
        {
            mFirst = nullptr;
        }
        else
        {
            mLast->next = nullptr; // 清空新尾节点的next指针
        }

        decreaseSize();
        return lastValue;
    }
};

该版本的pop_back时间复杂度为O(1)，完全无需遍历，彻底解决效率问题。

关于智能指针的问题 #

你用std::shared_ptr未解决问题，大概率是因为双向链表使用shared_ptr会出现循环引用（节点的next和prev均为shared_ptr，导致节点无法被正确释放）。正确做法是用std::shared_ptr管理next，用std::weak_ptr管理prev：

struct Node
{
    T value;
    std::shared_ptr<Node> next = nullptr;
    std::weak_ptr<Node> prev; // 用weak_ptr避免循环引用
};

后续pop_back时，通过mLast->prev.lock()即可安全获取前驱节点的shared_ptr，既保证内存安全又不会出现循环引用。

内容的提问来源于stack exchange，提问作者Mikel Grenlou