C++双向LinkedList类push_back与insertBefore方法故障排查咨询

1. push_back 方法问题 #

存在的问题： #

• 函数开头无差别申请了Node<T>内存，若触发addFirstNode分支，该内存会直接泄露
• 非首次插入时，仅修改了新节点的前驱指针和尾指针，没有修改原尾节点的后继指针，导致链表节点链断裂，只能保留最后一次插入的节点

修复后代码： #

template<class T>
void LinkedList<T>::push_back(T item) {
    if(head == nullptr)
    {
        addFirstNode(item);
        return;
    }
    Node<T> *n = new Node<T>;
    n->data = item;
    n->next = nullptr;
    n->previous = tail;
    tail->next = n; // 新增：更新原尾节点的后继指针
    tail = n;
}

2. insertBefore 方法问题 #

存在的问题： #

• 匹配逻辑仅判断temp->next->data是否等于key，无法匹配头节点本身就是key的场景
• 循环终止条件为temp->next != nullptr，无法匹配尾节点为key的场景
• 头节点更新逻辑写在匹配temp->next为key的分支内，此时新节点的前驱永远是temp，不可能为空，该段逻辑永远不会生效

修复后代码： #

template<class T>
void LinkedList<T>::insertBefore(T item, T key) {
    if(head == nullptr)
    {
        std::cout << "List is empty" << std::endl;
        return;
    }
    // 优先判断头节点是否为key
    if(head->data == key)
    {
        Node<T> *n = new Node<T>;
        n->data = item;
        n->next = head;
        n->previous = nullptr;
        head->previous = n;
        head = n;
        return;
    }
    Node<T> *temp = head;
    // 遍历所有节点匹配key
    while(temp != nullptr)
    {
        if(temp->data == key)
        {
            Node<T> *n = new Node<T>;
            n->data = item;
            n->next = temp;
            n->previous = temp->previous;
            temp->previous->next = n;
            temp->previous = n;
            return;
        }
        temp = temp->next;
    }
    std::cout << key << " is not on the list.";
}

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