C++如何实现一个双向链表_C++数据结构与双向链表实现-C++-PHP中文网

C++如何实现一个双向链表_C++数据结构与双向链表实现

裘德小鎮的故事

发布： 2025-11-17 18:54:57

原创

616人浏览过

答案：双向链表通过每个节点的prev和next指针实现前后遍历，支持高效的插入删除操作。结构上包含头尾指针，核心操作有头部插入、尾部插入、删除指定值、正向反向遍历及清空链表，需注意空链表等边界情况处理。

c++如何实现一个双向链表_c++数据结构与双向链表实现

实现一个双向链表需要理解其基本结构：每个节点包含数据、指向前一个节点的指针（prev）和指向下一个节点的指针（next）。相比单向链表，双向链表支持前后双向遍历，插入和删除操作更高效，尤其在已知节点位置时。

定义双向链表节点结构

首先定义链表中的节点类。每个节点保存数据值，并维护两个指针：

struct ListNode {
    int data;
    ListNode* prev;
    ListNode* next;
<pre class='brush:php;toolbar:false;'>// 构造函数
ListNode(int value) : data(value), prev(nullptr), next(nullptr) {}

登录后复制

};

实现双向链表类

创建一个管理节点的链表类，包含头指针和尾指针，便于在两端高效操作：

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

class DoublyLinkedList {
private:
    ListNode* head;
    ListNode* tail;
    int size;
<p>public:
DoublyLinkedList() : head(nullptr), tail(nullptr), size(0) {}</p><pre class='brush:php;toolbar:false;'>~DoublyLinkedList();

void push_front(int value);
void push_back(int value);
void pop_front();
void pop_back();
void insert(int index, int value);
void remove(int value);
void display_forward();
void display_backward();
bool empty() const;
int get_size() const;

登录后复制

};

核心操作实现

以下是几个关键成员函数的具体实现：

1. 头部插入

在链表头部添加新节点：

腾讯智影-AI数字人

基于AI数字人能力，实现7*24小时AI数字人直播带货，低成本实现直播业务快速增增，全天智能在线直播

查看详情

void DoublyLinkedList::push_front(int value) {
    ListNode* newNode = new ListNode(value);
    if (!head) {
        head = tail = newNode;
    } else {
        newNode->next = head;
        head->prev = newNode;
        head = newNode;
    }
    size++;
}

登录后复制

2. 尾部插入

在链表末尾追加节点：

void DoublyLinkedList::push_back(int value) {
    ListNode* newNode = new ListNode(value);
    if (!tail) {
        head = tail = newNode;
    } else {
        tail->next = newNode;
        newNode->prev = tail;
        tail = newNode;
    }
    size++;
}

登录后复制

3. 删除指定值的节点

遍历查找并移除第一个匹配的节点：

void DoublyLinkedList::remove(int value) {
    ListNode* current = head;
    while (current) {
        if (current->data == value) {
            if (current == head) {
                pop_front();
            } else if (current == tail) {
                pop_back();
            } else {
                current->prev->next = current->next;
                current->next->prev = current->prev;
                delete current;
                size--;
            }
            return;
        }
        current = current->next;
    }
}

登录后复制

4. 正向与反向遍历输出

利用双向特性，分别从头到尾和从尾到头打印：

void DoublyLinkedList::display_forward() {
    ListNode* current = head;
    while (current) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}
<p>void DoublyLinkedList::display_backward() {
ListNode* current = tail;
while (current) {
std::cout << current->data << " ";
current = current->prev;
}
std::cout << std::endl;
}</p>

登录后复制

内存管理与析构函数

确保资源正确释放，避免内存泄漏：

DoublyLinkedList::~DoublyLinkedList() {
    while (head) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
    tail = nullptr;
    size = 0;
}

登录后复制

基本上就这些。这个实现覆盖了双向链表的基本功能，适合学习和实际应用。注意边界情况处理，比如空链表操作或删除不存在的值。只要理清指针关系，双向链表并不复杂但容易忽略细节。

以上就是C++如何实现一个双向链表_C++数据结构与双向链表实现的详细内容，更多请关注php中文网其它相关文章！