C++ 实现封装的双链表：双链表的操作与实践

C++ 实现封装的双链表：双链表的操作与实践

双链表是链表的一种变种，除了每个节点指向下一个节点外，还多了一个指向前一个节点的指针。由于双链表可以从两端进行遍历，它的插入和删除操作更为灵活。本文将详细介绍如何使用 C++ 语言实现一个封装的双链表类，深入探讨双链表的核心操作，并展示完整的代码示例。

一、双链表的基本概念

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

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

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

在 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;
}

三、双链表操作实现

1. PushFront：在链表的头部插入新元素。
2. PushBack：在链表的尾部插入新元素。
3. PopFront：删除链表的头元素。
4. PopBack：删除链表的尾元素。
5. InsertAfter：在指定节点之后插入新节点。
6. PopValue：根据节点值删除该节点。

四、总结

通过面向对象的方式实现双链表，我们能够更加方便和安全地进行双链表操作。封装了内存管理、节点操作等的类，使得双链表的使用更加直观并且易于维护。双链表的优势在于其灵活的插入和删除操作，特别适合需要频繁变更数据结构的场景。

希望本篇博客能够帮助你更好地理解和使用 C++ 实现的双链表。如果你有任何问题，欢迎留言讨论！