c++中如何实现双向链表_c++双向链表实现方式-C++-PHP中文网

c++中如何实现双向链表_c++双向链表实现方式

尼克

发布： 2025-09-27 21:32:02

原创

621人浏览过

答案：C++实现双向链表需定义含data、next、prev的节点结构，并用类封装head和tail指针及操作方法，支持push_back、push_front、remove、正反向遍历等操作，通过维护前后指针实现高效插入删除，示例代码展示了基本操作与使用场景。

c++中如何实现双向链表_c++双向链表实现方式

在C++中实现双向链表，核心是定义一个节点结构体（或类），其中包含数据域和两个指针：一个指向下一个节点（next），另一个指向前一个节点（prev）。然后通过类封装链表的操作，如插入、删除、查找和遍历等。

定义双向链表节点和类

每个节点保存数据，并有两个指针分别连接前后节点。使用类来管理整个链表的头尾指针和操作方法。

节点结构包含 data、next 和 prev 指针
链表类维护 head 和 tail 指针，也可只用 head 实现，但维护 tail 可提升尾部操作效率

示例代码：

#include <iostream>
using namespace std;
<p>// 定义节点结构
struct ListNode {
int data;
ListNode<em> next;
ListNode</em> prev;</p><pre class='brush:php;toolbar:false;'>ListNode(int val) : data(val), next(nullptr), prev(nullptr) {}

登录后复制

};

立即学习“C++免费学习笔记（深入）”；

爱图表

AI驱动的智能化图表创作平台

查看详情

// 双向链表类 class DoublyLinkedList { private: ListNode head; ListNode tail;

public: DoublyLinkedList() : head(nullptr), tail(nullptr) {}

// 在链表末尾插入节点
void push_back(int val) {
    ListNode* newNode = new ListNode(val);
    if (!head) {
        head = tail = newNode;
    } else {
        tail->next = newNode;
        newNode->prev = tail;
        tail = newNode;
    }
}

// 在链表头部插入节点
void push_front(int val) {
    ListNode* newNode = new ListNode(val);
    if (!head) {
        head = tail = newNode;
    } else {
        newNode->next = head;
        head->prev = newNode;
        head = newNode;
    }
}

// 删除指定值的节点
bool remove(int val) {
    ListNode* curr = head;
    while (curr) {
        if (curr->data == val) {
            if (curr->prev) {
                curr->prev->next = curr->next;
            } else {
                head = curr->next;  // 当前是头节点
            }

            if (curr->next) {
                curr->next->prev = curr->prev;
            } else {
                tail = curr->prev;  // 当前是尾节点
            }

            delete curr;
            return true;
        }
        curr = curr->next;
    }
    return false;  // 未找到
}

// 打印链表（正向）
void print_forward() {
    ListNode* curr = head;
    while (curr) {
        cout << curr->data << " ";
        curr = curr->next;
    }
    cout << endl;
}

// 打印链表（反向）
void print_backward() {
    ListNode* curr = tail;
    while (curr) {
        cout << curr->data << " ";
        curr = curr->prev;
    }
    cout << endl;
}

// 析构函数：释放所有节点内存
~DoublyLinkedList() {
    ListNode* curr = head;
    while (curr) {
        ListNode* next = curr->next;
        delete curr;
        curr = next;
    }
}

登录后复制

};

立即学习“C++免费学习笔记（深入）”；

基本操作说明

上述实现包含了常用操作，理解其逻辑有助于掌握双向链表的本质。

插入操作：

push_back 在尾部添加，需更新 tail 指针
push_front 在头部添加，需更新 head 指针

删除操作：

需处理四种情况：唯一节点、头节点、尾节点、中间节点
注意指针判空，避免访问非法内存

遍历方向：

从 head 开始 next 遍历为正向
从 tail 开始 prev 遍历为反向

使用示例

测试上面的双向链表实现：

int main() {
    DoublyLinkedList dll;
    dll.push_back(1);
    dll.push_back(2);
    dll.push_front(0);
    dll.print_forward();   // 输出: 0 1 2
    dll.print_backward();  // 输出: 2 1 0
<pre class='brush:php;toolbar:false;'>dll.remove(1);
dll.print_forward();   // 输出: 0 2

return 0;

登录后复制

}

基本上就这些。双向链表比单向链表更灵活，支持前后双向遍历和高效地在任意位置插入删除，但每个节点多一个指针开销。实际开发中可根据需求选择是否需要维护 tail 指针，以及是否加入 size 计数器等优化。

以上就是c++++中如何实现双向链表_c++双向链表实现方式的详细内容，更多请关注php中文网其它相关文章！