无法理解双向链表head与tail赋值，remove函数失效求助

问题描述 #

我搞不懂双向链表的head和tail属性该怎么赋值，实现remove函数一直不正常。肯定是LinkedList::insert()和LinkedList::remove()里的head、tail处理出问题了。

在LinkedList::remove()里，current变量不知道该赋啥值：用head的话会拿到前一个节点的值；用head.next直接抛异常。还有previous指针的用法也有问题，同样会引发异常。查过相关案例，但没找到解决办法。

相关代码 #

Node头文件 #

#pragma once

class Node
{
public:
    int data;
    Node* next;
    Node* previous;
};

LinkedList头文件 #

class LinkedList
{
private:
    int length;
    Node* head;
    Node* tail;

public:
    LinkedList();
    void remove(int deleted);
    void insert(int data);
    void display();
    int getLength();
};

LinkedList实现文件 #

#include <iostream>
#include "LinkedList.h"
#include "Node.h"

using namespace std;

//Define variables used in the class
LinkedList::LinkedList()
{
    length = 0;
    head = NULL;
    tail = NULL;
}

//Define the remove function
void LinkedList::remove(int deletedNode)
{ 
    struct Node* current = head;
    while (current)
    {
        if (current->data == deletedNode)
        {
            if (current->next == NULL)
            {
                current->previous->next = NULL;
                current = NULL;
            }
            else if (head == NULL)
            {
                current->next->previous = NULL;
                current = NULL;
            }
            else
            {
                current->previous->next = current->next;
                current->next->previous = current->previous;
                current = NULL;
            }
        }
        current = current->next;
    }
}

//Define insert function
void LinkedList::insert(int num1)
{
    Node* node = new Node(); //Create new node
    node->data = num1; //Assign new number to node's data variable
    node->next = head; //Assign the current contents of the head variable to the new node's next pointer
    node->previous = tail; //Assign the current contents of the tail variable to the new node's previous pointer
    head = node; //Assign the new node to the head variable
    tail = node->previous;

    length++; //Increase the list's length by one
}

//Define display function
void LinkedList::display()
{
    Node* curr = this->head;
    int i = 1;
    while (curr)
    {
        cout << "Value of node #" << i << " is " << curr->data << endl;
        curr = curr->next;
        i++;
    }
}

//Define getLength function
int LinkedList::getLength()
{
    return length;
}

主函数文件 #

#include <iostream>
#include "LinkedList.h"
#include "Node.h"
#include <time.h>

using namespace std;

int main()
{
    int userRemove = 1;

    LinkedList list;

    // Define & start clock
    clock_t start, end;
    start = clock();

    for (int i = 1; i < 101; i++)
    {
        list.insert(rand() % 101);
    }

    // Display list
    list.display();

    // End clock
    end = clock();

    //Display duration it took to display list
    cout << endl << "It took " << (end - start) << " milliseconds to list & display all nodes." << endl;

    //Display total number of nodes
    int len = list.getLength();
    cout << endl << "# of nodes = " << len << endl;

    //Ask user for node number to remove
    while (userRemove != 0)
    {
        cout << endl << "Please enter the number of the node you wish to delete or press '0' to exit: " << endl;
        cin >> userRemove;
        list.remove(userRemove);
        cout << endl << "The first node containing " << userRemove << " has been removed." << endl;
        //Display list and list length after removal
        list.display();
        cout << endl << "# of nodes = " << len << endl;
    }
}

错误分析与修复 #

1. insert函数的核心错误 #

原insert函数的head/tail赋值逻辑完全错误，导致链表结构混乱：

• 新节点插在头部时，previous应该是nullptr（头部节点没有前驱），而不是tail
• 原链表不为空时，需要把原head节点的previous指向新节点，否则双向链表的前驱链断裂
• tail的赋值逻辑错误，原代码把tail设为node->previous（也就是空），正确逻辑是：如果链表原本为空，新节点同时是head和tail；否则tail保持不变

修改后的insert函数：

void LinkedList::insert(int num1)
{
    Node* node = new Node();
    node->data = num1;
    node->next = head;
    node->previous = nullptr; // 头部节点无前驱

    if (head != nullptr) {
        head->previous = node; // 原head的前驱指向新节点
    } else {
        tail = node; // 空链表时，新节点同时是tail
    }

    head = node; // 更新head为新节点
    length++;
}

2. remove函数的核心错误 #

原remove函数存在多个逻辑漏洞，导致空指针异常和链表结构错误：

• 判断顺序错误：应该先判断是否是head节点，再判断是否是tail节点
• 删除节点时未更新head/tail指针，导致后续遍历出错
• 未释放删除节点的内存，造成内存泄漏
• 找到目标节点后未退出循环，继续遍历会访问空指针
• 未处理删除节点后length减1的逻辑

修改后的remove函数：

void LinkedList::remove(int deletedNode)
{
    if (head == nullptr) {
        return; // 空链表直接返回
    }

    Node* current = head;
    while (current) {
        if (current->data == deletedNode) {
            // 情况1：删除的是head节点
            if (current == head) {
                head = current->next;
                if (head != nullptr) {
                    head->previous = nullptr;
                } else {
                    tail = nullptr; // 删除最后一个节点时，tail也要置空
                }
            }
            // 情况2：删除的是tail节点
            else if (current == tail) {
                tail = current->previous;
                tail->next = nullptr;
            }
            // 情况3：删除中间节点
            else {
                current->previous->next = current->next;
                current->next->previous = current->previous;
            }

            delete current; // 释放内存
            length--; // 长度减1
            break; // 找到第一个匹配节点后退出循环
        }
        current = current->next;
    }
}

3. 主函数的小问题 #

原主函数中len只初始化了一次，删除节点后不会更新，导致显示的长度始终是初始值。修改主函数中显示长度的部分：

// 替换原有的长度输出代码
cout << endl << "# of nodes = " << list.getLength() << endl;

验证效果 #

修改后，插入节点时链表的head和tail会正确维护，删除节点时无论删除头部、尾部还是中间节点，都不会出现空指针异常，链表结构保持完整，长度也会正确更新。

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