C++带头双向循环链表怎么实现

这篇文章主要介绍"C++带头双向循环链表怎么实现"，在日常操作中，相信很多人在C++带头双向循环链表怎么实现问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答"C++带头双向循环链表怎么实现"的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

与单链表的区别

单向/双向

单向：只有一个ｎｅｘｔ指针，只指向下一位元素

双向：有两个指针，指向上一位和下一位元素，寻找前一节点和后一节点很便利

带头/不带头

带头：在本来的头结点之前还有一个哨兵卫节点作为头节点，它的址域指针指向头节点，值域不做使用
不带头：没有哨兵卫头节点，在尾删尾插等问题中要考虑头结点的情况（局限）

循环/非循环

循环：头结点会与尾节点相连

非循环：头结点不与尾节点相连

代码的实现

接口

// 创建链表（链表初始化）ListNode* ListCreate();//创建节点ListNode* BuyListNode(ListNode* pHead);// 双向链表销毁void ListDestory(ListNode* pHead);// 双向链表打印void ListPrint(ListNode* pHead);// 双向链表尾插void ListPushBack(ListNode* pHead, LTDataType x);// 双向链表尾删void ListPopBack(ListNode* pHead);// 双向链表头插void ListPushFront(ListNode* pHead, LTDataType x);// 双向链表头删void ListPopFront(ListNode* pHead);// 双向链表查找ListNode* ListFind(ListNode* pHead, LTDataType x);// 双向链表在pos的前面进行插入void ListInsert(ListNode* pos, LTDataType x);// 双向链表删除pos位置的节点void ListErase(ListNode* pos);

节点的构造

typedef int LTDataType;typedef struct ListNode{        LTDataType data;        struct ListNode* next;        struct ListNode* prev;}ListNode;

初始化链表

// 创建链表（初始化）ListNode* ListCreate(){        //开辟哨兵卫头结点        ListNode* plist = (ListNode*)malloc(sizeof(ListNode));        if (plist == NULL)//失败打印错误信息并结束进程        {                perror("ListCreat fail:");                exit(-1);        }        plist->next = plist;        plist->prev = plist;        return plist;}

开辟节点

//创建节点ListNode* BuyListNode(LTDataType x){        //创建节点        ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));        if (newnode == NULL)//失败打印错误信息并结束进程        {                perror("creatnode fail:");                exit(-1);        }        newnode->data = x;        //初始化结点        newnode->next = NULL;        newnode->prev = NULL;        return newnode;}

销毁链表

注：动态开辟的链表空间，在不使用后需要将之释放，避免造成内存泄漏

// 双向链表销毁void ListDestory(ListNode* pHead){        //断言传入指针不为NULL        assert(pHead);        ListNode* cur = pHead;        pHead->prev->next = NULL;        while (cur!=NULL)        {                ListNode* next = cur->next;                free(cur);                cur = next;        }        return;}

打印链表

// 双向链表打印void ListPrint(ListNode* pHead){        //断言传入指针不为NULL        assert(pHead);        //创建寻址指针        ListNode* cur = pHead->next;        //循环遍历链表        while (cur != pHead)        {                //打印数据                printf("%d->", cur->data);                //找到下一个节点                cur = cur->next;        }printf("NULL\n");        return;}

尾插链表

// 双向链表尾插void ListPushBack(ListNode* pHead, LTDataType x){        //断言传入指针不为NULL        assert(pHead);        //创建节点        ListNode* newnode = BuyListNode(x);        //找到尾节点        ListNode* tail=pHead->prev;        tail->next = newnode;        newnode->prev = tail;         pHead->prev = newnode;        newnode->next = pHead;}

尾删链表

尾删前记录前一节点的地址

// 双向链表尾删void ListPopBack(ListNode* pHead){        //断言传入指针不为NULL        assert(pHead);        //只剩哨兵卫头结点的情况        if (pHead->prev == pHead)                return;        //记录尾节点及其前一节点        ListNode* tail = pHead->prev;        ListNode* tailprev = tail->prev;        //释放尾节点        free(tail);        //构建尾节点前一节点与哨兵卫头结点的关系        tailprev->next = pHead;        pHead->prev = tailprev;        return;}

头插链表

头插前记录哨兵卫头节点的下一节点

// 双向链表头插void ListPushFront(ListNode* pHead, LTDataType x){        //断言传入指针不为NULL        assert(pHead);        //创建节点        ListNode* newnode = BuyListNode(x);        //记录哨兵卫头结点的下一节点        ListNode* next = pHead->next;        //构建各节点之间的关系        pHead->next = newnode;        newnode->prev = pHead;         newnode->next = next;        next->prev = newnode;        return;}

头删链表

// 双向链表头删void ListPopFront(ListNode* pHead){        //断言传入指针不为NULL        assert(pHead);        //只剩哨兵卫头结点的情况        if (pHead->next == pHead)                return;        //记录哨兵卫头结点下一节点及其的下一节点        ListNode* next = pHead->next;        ListNode* nextNext = next->next;        //释放节点        free(next);        pHead->next = nextNext;        nextNext->prev = pHead;        return;}

查找链表

// 双向链表查找ListNode* ListFind(ListNode* pHead, LTDataType x){        //断言传入指针不为NULL        assert(pHead);        //创建寻址指针        ListNode* cur = pHead->next;        while (cur != pHead)        {                //比较数据                if (cur->data == x)                        return cur;                //找到下一个节点                cur = cur->next;        }        //没找到则返回NULL        return NULL;}

链表pos位置的删除

void ListErase(ListNode* pos){        assert(pos);        ListNode* prev = pos->prev;        ListNode* next = pos->next;        free(pos);        prev->next = next;        next->prev = prev;        return;}

到此，关于"C++带头双向循环链表怎么实现"的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注网站，小编会继续努力为大家带来更多实用的文章！