C++双向链表的增删查改操作方法讲解

关于C++双向链表的增删查改操作方法，一般可以分为以下几步：

第一步：定义链表结构体

我们都知道链表是一种动态数据结构，它的每个元素都包含指向前一个元素和后一个元素的指针。因此，在C++中，我们可以用结构体来定义一个链表节点，具体的定义如下：

struct ListNode {
    int val;
    ListNode* prev;
    ListNode* next;
    ListNode(int x) : val(x), prev(nullptr), next(nullptr) {}
};

其中，val是节点的值，prev和next分别指向前一个节点和后一个节点。在这里，我们使用nullptr来初始化指针。

第二步：实现链表的增加操作

链表的增加操作也可以分为头插和尾插两种方式。

头插法

头插法是将新节点插入到链表的头部。具体的实现如下：

void addAtHead(ListNode*& head, int val) {
     ListNode* node = new ListNode(val);
     if (!head) {
         head = node;
     } else {
         node->next = head;
         head->prev = node;
         head = node;
     }
}

第一行代码是创建一个新的节点。如果链表为空，则将这个新节点设置为头节点。如果链表不为空，则将这个新节点插入到头节点的前面，并更新头节点的信息。

尾插法

尾插法是将新节点插入到链表的尾部。具体的实现如下：

void addAtTail(ListNode*& head, int val) {
    ListNode* node = new ListNode(val);
    if (!head) {
        head = node;
    } else {
        ListNode* cur = head;
        while (cur->next) {
            cur = cur->next;
        }
        cur->next = node;
        node->prev = cur;
    }
}

第一行代码同样是创建一个新的节点。如果链表为空，则将这个新节点设置为头节点。如果链表不为空，则从头节点开始遍历到链表尾部，在尾节点的后面加入一个新节点。

第三步：实现链表的删除操作

链表的删除操作也可以分为删除头节点和删除尾节点两种方式。

删除头节点

删除头节点可以直接将头节点的后一个节点作为头节点，并释放原头节点的内存空间。具体的实现如下：

void deleteAtHead(ListNode*& head) {
    if (!head) {
        return;
    }
    ListNode* tmp = head;
    head = head->next;
    if (head) {
        head->prev = nullptr;
    }
    delete tmp;
}

如果链表不为空，则将头节点指针指向第二个节点。由于新的头节点的前面没有节点，因此将它的prev指针置空。最后，释放掉原来的头节点的内存空间。

删除尾节点

删除尾节点可以遍历到尾节点的前一个节点，并将它的next指针置空。然后，释放掉原尾节点的内存空间。具体的实现如下：

void deleteAtTail(ListNode*& head) {
    if (!head) {
        return;
    }
    if (!head->next) {
        delete head;
        head = nullptr;
        return;
    }
    ListNode* cur = head;
    while (cur->next) {
        cur = cur->next;
    }
    cur->prev->next = nullptr;
    delete cur;
}

如果链表只有一个节点，直接释放掉这个节点并将头指针置空。否则从头节点开始遍历到尾节点的前一个节点，并释放掉尾节点的内存空间。

第四步：实现链表的查找操作

链表的查找操作主要是根据节点的值进行查找。我们可以从头节点开始遍历每个节点，如果找到了对应的节点，则返回该节点的指针。否则，返回nullptr。具体的实现如下：

ListNode* search(ListNode* head, int val) {
    while (head) {
        if (head->val == val) {
            return head;
        }
        head = head->next;
    }
    return nullptr;
}

从头节点开始遍历每个节点，如果找到了节点的值等于val，则返回该节点的指针。否则，继续向后遍历，直到链表的末尾都没有找到节点，则返回nullptr。

第五步：实现链表的修改操作

修改链表中的节点可以直接通过访问节点的val来修改。具体的实现如下：

void update(ListNode* head, int oldVal, int newVal) {
    ListNode* node = search(head, oldVal);
    if (node) {
        node->val = newVal;
    }
}

从头节点开始查找节点的值等于oldVal的节点。如果找到了节点，则将该节点的值修改为newVal。

示例说明

示例一

通过头插法构建一个链表，并输出该链表的值。

ListNode* head = nullptr;
addAtHead(head, 1);
addAtHead(head, 2); 
addAtHead(head, 3); 

ListNode* cur = head;
while (cur) {
    cout << cur->val << " ";
    cur = cur->next;
}

输出结果为“3 2 1”。

示例二

通过尾插法构建一个链表，并删除尾节点。

ListNode* head = nullptr;
addAtTail(head, 1);
addAtTail(head, 2); 
addAtTail(head, 3); 

deleteAtTail(head);

ListNode* cur = head;
while (cur) {
    cout << cur->val << " ";
    cur = cur->next;
}

输出结果为“1 2”。