C++双向链表的增删查改操作方法源码分析

发布时间：2023-03-25 10:19:44 作者：iii
来源：亿速云阅读：145

C++双向链表的增删查改操作方法源码分析

引言

双向链表（Doubly Linked List）是一种常见的数据结构，它由一系列节点组成，每个节点包含数据域和两个指针域，分别指向前驱节点和后继节点。与单向链表相比，双向链表在插入、删除等操作上更加灵活，但同时也增加了内存开销。本文将详细分析C++中双向链表的增删查改操作的实现方法，并通过源码进行解析。

1. 双向链表的基本结构

首先，我们定义一个双向链表的节点结构：

struct Node {
    int data;       // 数据域
    Node* prev;     // 前驱指针
    Node* next;     // 后继指针

    Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

在这个结构中，data存储节点的数据，prev指向前一个节点，next指向下一个节点。

2. 双向链表的插入操作

2.1 在链表头部插入节点

在链表头部插入节点时，我们需要更新新节点的next指针指向当前的头节点，并更新头节点的prev指针指向新节点。

void insertAtHead(Node*& head, int val) {
    Node* newNode = new Node(val);
    if (head == nullptr) {
        head = newNode;
    } else {
        newNode->next = head;
        head->prev = newNode;
        head = newNode;
    }
}

2.2 在链表尾部插入节点

在链表尾部插入节点时，我们需要遍历链表找到尾节点，然后更新尾节点的next指针指向新节点，同时更新新节点的prev指针指向尾节点。

void insertAtTail(Node*& head, int val) {
    Node* newNode = new Node(val);
    if (head == nullptr) {
        head = newNode;
    } else {
        Node* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->prev = temp;
    }
}

2.3 在指定位置插入节点

在指定位置插入节点时，我们需要找到该位置的前一个节点，然后更新新节点的prev和next指针，同时更新前一个节点和后一个节点的指针。

void insertAtPosition(Node*& head, int val, int position) {
    if (position == 0) {
        insertAtHead(head, val);
        return;
    }

    Node* newNode = new Node(val);
    Node* temp = head;
    for (int i = 0; i < position - 1 && temp != nullptr; ++i) {
        temp = temp->next;
    }

    if (temp == nullptr) {
        std::cerr << "Position out of range" << std::endl;
        return;
    }

    newNode->next = temp->next;
    if (temp->next != nullptr) {
        temp->next->prev = newNode;
    }
    temp->next = newNode;
    newNode->prev = temp;
}

3. 双向链表的删除操作

3.1 删除头节点

删除头节点时，我们需要更新头指针指向下一个节点，并释放原头节点的内存。

void deleteAtHead(Node*& head) {
    if (head == nullptr) {
        std::cerr << "List is empty" << std::endl;
        return;
    }

    Node* temp = head;
    head = head->next;
    if (head != nullptr) {
        head->prev = nullptr;
    }
    delete temp;
}

3.2 删除尾节点

删除尾节点时，我们需要遍历链表找到尾节点，然后更新尾节点的前一个节点的next指针，并释放尾节点的内存。

void deleteAtTail(Node*& head) {
    if (head == nullptr) {
        std::cerr << "List is empty" << std::endl;
        return;
    }

    if (head->next == nullptr) {
        delete head;
        head = nullptr;
        return;
    }

    Node* temp = head;
    while (temp->next != nullptr) {
        temp = temp->next;
    }

    temp->prev->next = nullptr;
    delete temp;
}

3.3 删除指定位置的节点

删除指定位置的节点时，我们需要找到该节点的前一个节点，然后更新前一个节点的next指针和后一个节点的prev指针，并释放该节点的内存。

void deleteAtPosition(Node*& head, int position) {
    if (head == nullptr) {
        std::cerr << "List is empty" << std::endl;
        return;
    }

    if (position == 0) {
        deleteAtHead(head);
        return;
    }

    Node* temp = head;
    for (int i = 0; i < position && temp != nullptr; ++i) {
        temp = temp->next;
    }

    if (temp == nullptr) {
        std::cerr << "Position out of range" << std::endl;
        return;
    }

    if (temp->next != nullptr) {
        temp->next->prev = temp->prev;
    }
    if (temp->prev != nullptr) {
        temp->prev->next = temp->next;
    }
    delete temp;
}

4. 双向链表的查找操作

查找操作通常是通过遍历链表来找到指定值的节点。

Node* search(Node* head, int val) {
    Node* temp = head;
    while (temp != nullptr) {
        if (temp->data == val) {
            return temp;
        }
        temp = temp->next;
    }
    return nullptr;
}

5. 双向链表的修改操作

修改操作通常是通过查找操作找到指定节点，然后更新其数据域。

void update(Node* head, int oldVal, int newVal) {
    Node* node = search(head, oldVal);
    if (node != nullptr) {
        node->data = newVal;
    } else {
        std::cerr << "Value not found" << std::endl;
    }
}

6. 双向链表的遍历操作

遍历操作是双向链表的基本操作之一，用于访问链表中的每个节点。

void traverse(Node* head) {
    Node* temp = head;
    while (temp != nullptr) {
        std::cout << temp->data << " ";
        temp = temp->next;
    }
    std::cout << std::endl;
}

7. 双向链表的完整示例

下面是一个完整的双向链表示例，展示了如何实现增删查改操作。

#include <iostream>

struct Node {
    int data;
    Node* prev;
    Node* next;

    Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

void insertAtHead(Node*& head, int val) {
    Node* newNode = new Node(val);
    if (head == nullptr) {
        head = newNode;
    } else {
        newNode->next = head;
        head->prev = newNode;
        head = newNode;
    }
}

void insertAtTail(Node*& head, int val) {
    Node* newNode = new Node(val);
    if (head == nullptr) {
        head = newNode;
    } else {
        Node* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->prev = temp;
    }
}

void insertAtPosition(Node*& head, int val, int position) {
    if (position == 0) {
        insertAtHead(head, val);
        return;
    }

    Node* newNode = new Node(val);
    Node* temp = head;
    for (int i = 0; i < position - 1 && temp != nullptr; ++i) {
        temp = temp->next;
    }

    if (temp == nullptr) {
        std::cerr << "Position out of range" << std::endl;
        return;
    }

    newNode->next = temp->next;
    if (temp->next != nullptr) {
        temp->next->prev = newNode;
    }
    temp->next = newNode;
    newNode->prev = temp;
}

void deleteAtHead(Node*& head) {
    if (head == nullptr) {
        std::cerr << "List is empty" << std::endl;
        return;
    }

    Node* temp = head;
    head = head->next;
    if (head != nullptr) {
        head->prev = nullptr;
    }
    delete temp;
}

void deleteAtTail(Node*& head) {
    if (head == nullptr) {
        std::cerr << "List is empty" << std::endl;
        return;
    }

    if (head->next == nullptr) {
        delete head;
        head = nullptr;
        return;
    }

    Node* temp = head;
    while (temp->next != nullptr) {
        temp = temp->next;
    }

    temp->prev->next = nullptr;
    delete temp;
}

void deleteAtPosition(Node*& head, int position) {
    if (head == nullptr) {
        std::cerr << "List is empty" << std::endl;
        return;
    }

    if (position == 0) {
        deleteAtHead(head);
        return;
    }

    Node* temp = head;
    for (int i = 0; i < position && temp != nullptr; ++i) {
        temp = temp->next;
    }

    if (temp == nullptr) {
        std::cerr << "Position out of range" << std::endl;
        return;
    }

    if (temp->next != nullptr) {
        temp->next->prev = temp->prev;
    }
    if (temp->prev != nullptr) {
        temp->prev->next = temp->next;
    }
    delete temp;
}

Node* search(Node* head, int val) {
    Node* temp = head;
    while (temp != nullptr) {
        if (temp->data == val) {
            return temp;
        }
        temp = temp->next;
    }
    return nullptr;
}

void update(Node* head, int oldVal, int newVal) {
    Node* node = search(head, oldVal);
    if (node != nullptr) {
        node->data = newVal;
    } else {
        std::cerr << "Value not found" << std::endl;
    }
}

void traverse(Node* head) {
    Node* temp = head;
    while (temp != nullptr) {
        std::cout << temp->data << " ";
        temp = temp->next;
    }
    std::cout << std::endl;
}

int main() {
    Node* head = nullptr;

    insertAtHead(head, 10);
    insertAtHead(head, 20);
    insertAtTail(head, 30);
    insertAtPosition(head, 40, 1);

    traverse(head); // 输出: 20 40 10 30

    deleteAtHead(head);
    deleteAtTail(head);
    deleteAtPosition(head, 1);

    traverse(head); // 输出: 40

    update(head, 40, 50);
    traverse(head); // 输出: 50

    return 0;
}

结论

本文详细介绍了C++中双向链表的增删查改操作的实现方法，并通过源码进行了详细解析。双向链表在插入和删除操作上具有较高的灵活性，但同时也增加了内存开销。通过掌握这些基本操作，可以更好地理解和应用双向链表这一数据结构。

C++双向链表的增删查改操作方法源码分析

C++双向链表的增删查改操作方法源码分析

引言

1. 双向链表的基本结构

2. 双向链表的插入操作

2.1 在链表头部插入节点

2.2 在链表尾部插入节点

2.3 在指定位置插入节点

3. 双向链表的删除操作

3.1 删除头节点

3.2 删除尾节点

3.3 删除指定位置的节点

4. 双向链表的查找操作

5. 双向链表的修改操作

6. 双向链表的遍历操作

7. 双向链表的完整示例

结论

相关阅读