C++实现一个封装的双链表的完整代码_C/C++

一、双链表的基本概念

双链表是一种由一组节点构成的线性数据结构，其中每个节点包含三部分：

数据域：存储节点的数据。
前驱指针：指向前一个节点。
后继指针：指向下一个节点。

与单链表相比，双链表中的每个节点有两个指针，可以双向遍历，方便插入和删除操作。

在 c++ 中，我们通过类的封装特性来实现双链表，利用指针来动态管理节点的内存空间，保证数据的灵活性和高效性。

二、双链表类的设计

我们将通过一个简单的 c++ 类来实现双链表，该类包含基本的双链表操作，如插入、删除、查找、修改等。

1. 双链表类的成员变量

我们定义了一个 dlist 类，包含以下成员变量：

phead：指向双链表头节点的指针。

2. 构造函数和析构函数

双链表类的构造函数负责初始化成员变量，析构函数负责释放动态分配的内存。

#include<iostream>
using namespace std;

// 节点类型声明
struct node
{
    int date;
    node* last;  // 前驱节点
    node* next;  // 后继节点
};

class dlist
{
private:
    // 成员变量
    node* phead;

public:
    // 构造函数
    dlist() : phead(nullptr) {}

    // 析构函数
    ~dlist()
    {
        while (phead != null)
        {
            popfront();
        }
    }

    // 创建节点
    node* createnode(int x)
    {
        node* node = new node;
        node->date = x;
        node->last = null;
        node->next = null;
        return node;
    }

    // 打印链表
    void printlist()
    {
        node* cur = phead;
        while (cur)
        {
            cout << cur->date << "<-->";  // 双向箭头表示双链表
            cur = cur->next;
        }
        cout << "null" << endl;
    }

    // 头插法
    void pushfront(int x)
    {
        node* newnode = createnode(x);
        if (phead == null)
        {
            phead = newnode;
        }
        else
        {
            newnode->next = phead;
            phead->last = newnode;
            phead = newnode;
        }
    }

    // 尾插法
    void pushback(int x)
    {
        node* newnode = createnode(x);
        if (phead == null)
        {
            phead = newnode;
        }
        else
        {
            node* tail = phead;
            while (tail->next != null)
            {
                tail = tail->next;
            }
            tail->next = newnode;
            newnode->last = tail;
        }
    }

    // 头删法
    void popfront()
    {
        if (phead == null)
        {
            cout << "链表为空，无法进行删除操作！" << endl;
        }
        else
        {
            node* del = phead;
            phead = del->next;
            if (phead != null)
            {
                phead->last = null;
            }
            delete del;
            del = null;
        }
    }

    // 尾删法
    void popback()
    {
        if (phead == null)
        {
            cout << "链表为空，无法进行删除操作！" << endl;
        }
        else
        {
            if (phead->next == null)  // 只有一个节点
            {
                delete phead;
                phead = null;
            }
            else
            {
                node* tail = phead;
                while (tail->next != null)
                {
                    tail = tail->next;
                }
                tail->last->next = null;
                delete tail;
                tail = null;
            }
        }
    }
     //指定元素后插入
    void insertafter(int v, int x)
    {
        node* node = phead;
        while (node != null && node->date != v)
        {
            node = node->next;
        }

        if (node == null)
        {
            cout << "未找到值为 " << v << " 的节点，无法插入!" << endl;
            return;
        }

        node* newnode = createnode(x);
        newnode->last = node;
        newnode->next = node->next;

        if (node->next != null)
        {
            node->next->last = newnode;
        }

        node->next = newnode;
    }

    // 根据值删除节点
    void popvalue(int value)
    {
        if (phead == null)
        {
            cout << "链表为空，无法进行删除操作！" << endl;
            return;
        }
        node* cur = phead;
        while (cur != null)
        {
            if (cur->date == value)
            {
                // 删除节点
                if (cur->last != null)
                {
                    cur->last->next = cur->next;
                }
                else
                {
                    // 删除的是头节点
                    phead = cur->next;
                }

                if (cur->next != null)
                {
                    cur->next->last = cur->last;
                }
                delete cur;
                cur = null;
                cout << "删除节点 " << value << " 成功！" << endl;
                return;
            }
            cur = cur->next;
        }
        cout << "未找到值为 " << value << " 的节点！" << endl;
    }
};

int main()
{
    dlist ls1;
    ls1.pushback(1);
    ls1.pushback(2);
    ls1.pushback(3);
    ls1.pushback(4);
    ls1.pushback(5);
    ls1.printlist();

    ls1.popfront();
    ls1.popback();
    ls1.pushfront(9);
    ls1.printlist();

    ls1.insertafter(9,7);
    ls1.printlist();

    ls1.popvalue(4);
    ls1.printlist();
    return 0;
}