数据结构-带头双向循环链表的实现

前言 

        带头双向循环链表是一种重要的数据结构，它的结构是很完美的，它弥补了单链表的许多不足，让我们一起来了解一下它是如何实现的吧！

1.节点的结构

        它的节点中存储着数据和两个指针，一个指针_prev用来记录前一个节点的地址，另一个指针_next 用来记录后一个节点的地址。

typedef int LTDataType;
typedef struct ListNode
{struct ListNode* _next;struct ListNode* _prev;LTDataType _data;
}ListNode;

2.尾部的插入和删除的实现

        由于这是带头循环的双向链表，所以尾插只需要在它的头结点的_prev 处进行插入，然后重新链接就可以了。如图： 

        如果只有一个头结点，插入也是一样的。

void ListPushBack(ListNode* phead, LTDataType data)//尾插
{assert(phead);ListNode* newNode = BuyListNode(data);//申请新节点ListNode* tail = phead->_prev;//找尾结点//链接新节点和尾结点tail->_next = newNode;newNode->_prev = tail;//与头结点进行链接phead->_prev = newNode;newNode->_next = phead;
}

         尾部的删除，首先需要找到链表的尾和尾的前一个节点，删除尾结点之后，将前一个节点进与头结点进行链接，如图：

void ListPopBack(ListNode* phead)//尾删除
{//确保指针不为空assert(phead);assert(phead->_next != phead);//保留头结点//找尾ListNode* tail = phead->_prev;ListNode* newTail = tail->_prev;//找到新的尾结点//删除旧的尾结点free(tail);//重新链接头尾节点newTail->_next = phead;phead->_prev = newTail;
}

3.头部插入和删除的实现

        头部的插入，删除和尾部的插入，删除类似，需要注意的是删除的不是 头结点，是存储有效数据的第一个节点，插入数据也是在第一个有效数据节点和头结点之间插入。如图：

 

void ListPushFront(ListNode* phead, LTDataType data)//头插
{//确保指针不为空assert(phead);//申请新的节点ListNode* newNode = BuyListNode(data);//进行链接ListNode* realHead = phead->_next;realHead->_prev = newNode;newNode->_next = realHead;phead->_next = newNode;newNode->_prev = phead;
}
void ListPopFront(ListNode* phead)//头删插
{//指针存在assert(phead);//并且确保不能删除头结点assert(phead->_next != phead);//找到真正的头ListNode* realHead = phead->_next;ListNode* realHeadNext = realHead->_next;//删除头节点free(realHead);//重新链接phead->_next = realHeadNext;realHeadNext->_prev = phead;
}

4.任意位置的插入和删除 

        在任意位置进行插入和删除，需要知道节点的指针，插入或者删除节点之后需要 更新节点的链接关系。如图：

 

void ListInsert(ListNode* pos, LTDataType data)//pos位置之前的插入
{assert(pos);//确保指针有效ListNode* newNode = BuyListNode(data);//申请节点//进行链接ListNode* prev = pos->_prev;ListNode* next = pos;prev->_next = newNode;newNode->_prev = prev;newNode->_next = next;next->_prev = newNode;
}
void ListErase(ListNode* pos)//pos位置的删除
{//确保指针有效assert(pos);ListNode* next = pos->_next;ListNode* prev = pos->_prev;//删除pos所指向的节点free(pos);//进行重新链接prev->_next = next;next->_prev = prev;
}

         对任意位置的插入和删除进行测试时，可以通过复用接口来实现，头插尾插，头删尾删都可以调用这两个接口来实现，如下：

void ListPushBack(ListNode* phead, LTDataType data)//尾插
{ListInsert(phead, data);
}
void ListPopBack(ListNode* phead)//尾删除
{ListErase(phead->_prev);
}
void ListPushFront(ListNode* phead, LTDataType data)//头插
{ListInsert(phead->_next,data);
}
void ListPopFront(ListNode* phead)//头删插
{ListErase(phead->_next);
}

5.链表的初始化和删除

        带头的双向循环链表初始化的时候就需要申请内存给头节点。 

ListNode* BuyListNode(LTDataType data)//申请节点
{ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));if (newNode == NULL){printf("申请空间失败\n");exit(-1);}newNode->_data = data;return newNode;
}
void ListInit(ListNode** pphead)//初始化链表
{*pphead = BuyListNode(0);//申请头结点//并且初始化(*pphead)->_next = *pphead;(*pphead)->_prev = *pphead;
}
//清理链表
void ListClear(ListNode* phead)
{assert(phead);//确保链表不为空assert(phead->_next != phead);//除了确保不清理头结点ListNode* cur = phead->_next;while (cur != phead){ListNode* clearNode = cur;cur = cur->_next;free(clearNode);}
}
void ListDestory(ListNode** ppHead)//摧毁链表
{assert(*ppHead);//确保指针不为空ListClear(*ppHead);free(*ppHead);//释放头结点
}

6.查找并修改链表的节点的数据

        查找和修改是一起的，实现查找就可以实现 修改链表的值。

ListNode* ListFind(ListNode* phead, LTDataType data)//查找链表
{assert(phead);ListNode* cur = phead->_next;while (cur != phead){if (cur->_data == data)return cur;cur = cur->_next;}return NULL;//找不到返回NULL
}

void ListTest4()
{//查找和修改的测试ListNode* pHead = NULL;ListInit(&pHead);ListPushFront(pHead, 1);ListPushFront(pHead, 2);ListPushFront(pHead, 3);ListPushFront(pHead, 4);ListPushFront(pHead, 5);ListPushFront(pHead, 6);ListNode* node = ListFind(pHead, 3);//在链表中查找if (node){//修改链表的值node->_data = 90;}ListPrint(pHead);ListDestory(&pHead);
}

7.全部代码

//List.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LTDataType;
typedef struct ListNode
{struct ListNode* _next;struct ListNode* _prev;LTDataType _data;
}ListNode;void ListPushBack(ListNode* phead, LTDataType data);//尾插void ListPopBack(ListNode* phead);//尾删除
void ListPushFront(ListNode* phead,LTDataType data);//头插
void ListPopFront(ListNode* phead);//头删插
ListNode* BuyListNode(LTDataType data);//申请节点
void ListInit(ListNode** pphead);//初始化链表void ListInsert(ListNode* pos, LTDataType data);//pos位置之前的插入void ListErase(ListNode* pos);//pos位置的删除
//清理链表
void ListClear(ListNode* phead);void ListDestory(ListNode** ppHead);//摧毁链表void ListPrint(ListNode* phead);//打印链表
ListNode* ListFind(ListNode* phead, LTDataType data);//查找链表

 //List.c

#include"List.h"
void ListPushBack(ListNode* phead, LTDataType data)//尾插
{assert(phead);ListNode* newNode = BuyListNode(data);//申请新节点ListNode* tail = phead->_prev;//找尾结点//链接新节点和尾结点tail->_next = newNode;newNode->_prev = tail;//与头结点进行链接phead->_prev = newNode;newNode->_next = phead;
}
void ListPopBack(ListNode* phead)//尾删除
{//确保指针不为空assert(phead);assert(phead->_next != phead);//保留头结点//找尾ListNode* tail = phead->_prev;ListNode* newTail = tail->_prev;//找到新的尾结点//删除旧的尾结点free(tail);//重新链接头尾节点newTail->_next = phead;phead->_prev = newTail;
}
void ListPushFront(ListNode* phead, LTDataType data)//头插
{//确保指针不为空assert(phead);//申请新的节点ListNode* newNode = BuyListNode(data);//进行链接ListNode* realHead = phead->_next;realHead->_prev = newNode;newNode->_next = realHead;phead->_next = newNode;newNode->_prev = phead;
}
void ListPopFront(ListNode* phead)//头删插
{//指针存在assert(phead);//并且确保不能删除头结点assert(phead->_next != phead);//找到真正的头ListNode* realHead = phead->_next;ListNode* realHeadNext = realHead->_next;//删除头节点free(realHead);//重新链接phead->_next = realHeadNext;realHeadNext->_prev = phead;
}
ListNode* BuyListNode(LTDataType data)//申请节点
{ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));if (newNode == NULL){printf("申请空间失败\n");exit(-1);}newNode->_data = data;return newNode;
}
void ListInit(ListNode** pphead)//初始化链表
{*pphead = BuyListNode(0);//申请头结点//并且初始化(*pphead)->_next = *pphead;(*pphead)->_prev = *pphead;
}
void ListPrint(ListNode* phead)//打印链表
{assert(phead);ListNode* cur = phead->_next;while (cur != phead){printf("%d ", cur->_data);cur = cur->_next;}printf("\n");
}
void ListInsert(ListNode* pos, LTDataType data)//pos位置之前的插入
{assert(pos);//确保指针有效ListNode* newNode = BuyListNode(data);//申请节点//进行链接ListNode* prev = pos->_prev;ListNode* next = pos;prev->_next = newNode;newNode->_prev = prev;newNode->_next = next;next->_prev = newNode;
}
void ListErase(ListNode* pos)//pos位置的删除
{//确保指针有效assert(pos);ListNode* next = pos->_next;ListNode* prev = pos->_prev;//删除pos所指向的节点free(pos);//进行重新链接prev->_next = next;next->_prev = prev;
}
//清理链表
void ListClear(ListNode* phead)
{assert(phead);//确保链表不为空assert(phead->_next != phead);//除了确保不清理头结点ListNode* cur = phead->_next;while (cur != phead){ListNode* clearNode = cur;cur = cur->_next;free(clearNode);}
}
void ListDestory(ListNode** ppHead)//摧毁链表
{assert(*ppHead);//确保指针不为空ListClear(*ppHead);free(*ppHead);//释放头结点
}
ListNode* ListFind(ListNode* phead, LTDataType data)//查找链表
{assert(phead);ListNode* cur = phead->_next;while (cur != phead){if (cur->_data == data)return cur;cur = cur->_next;}return NULL;//找不到返回NULL
}

//test.c

#include"List.h"
void ListTest1()
{//尾插尾删的测试代码ListNode* pHead = NULL;ListInit(&pHead);ListPushBack(pHead, 1);ListPushBack(pHead, 2);ListPushBack(pHead, 3);ListPushBack(pHead, 4);ListPushBack(pHead, 5);ListPushBack(pHead, 6);ListPrint(pHead);ListPopBack(pHead);ListPopBack(pHead);ListPopBack(pHead);ListPopBack(pHead);ListPopBack(pHead);ListPopBack(pHead);//ListPopBack(pHead);}
void ListTest2()
{//头插头删的测试ListNode* pHead = NULL;ListInit(&pHead);ListPushFront(pHead, 1);ListPushFront(pHead, 2);ListPushFront(pHead, 3);ListPushFront(pHead, 4);ListPushFront(pHead, 5);ListPushFront(pHead, 6);ListPrint(pHead);ListPopFront(pHead);ListPopFront(pHead);ListPopFront(pHead);ListPopFront(pHead);ListPopFront(pHead);ListPopFront(pHead);ListPopFront(pHead);}
void ListTest3()
{//Destory和Clear的测试ListNode* pHead = NULL;ListInit(&pHead);ListPushFront(pHead, 1);ListPushFront(pHead, 2);ListPushFront(pHead, 3);ListPushFront(pHead, 4);ListPushFront(pHead, 5);ListPushFront(pHead, 6);ListDestory(&pHead);
}
int main()
{ListTest3();return 0;
}

 

8.测试代码

void ListTest1()
{//尾插尾删的测试代码ListNode* pHead = NULL;ListInit(&pHead);ListPushBack(pHead, 1);ListPushBack(pHead, 2);ListPushBack(pHead, 3);ListPushBack(pHead, 4);ListPushBack(pHead, 5);ListPushBack(pHead, 6);ListPrint(pHead);ListPopBack(pHead);ListPopBack(pHead);ListPopBack(pHead);ListPopBack(pHead);ListPopBack(pHead);ListPopBack(pHead);//ListPopBack(pHead);}
void ListTest2()
{//头插头删的测试ListNode* pHead = NULL;ListInit(&pHead);ListPushFront(pHead, 1);ListPushFront(pHead, 2);ListPushFront(pHead, 3);ListPushFront(pHead, 4);ListPushFront(pHead, 5);ListPushFront(pHead, 6);ListPrint(pHead);ListPopFront(pHead);ListPopFront(pHead);ListPopFront(pHead);ListPopFront(pHead);ListPopFront(pHead);ListPopFront(pHead);ListPopFront(pHead);}
void ListTest3()
{//Destory和Clear的测试ListNode* pHead = NULL;ListInit(&pHead);ListPushFront(pHead, 1);ListPushFront(pHead, 2);ListPushFront(pHead, 3);ListPushFront(pHead, 4);ListPushFront(pHead, 5);ListPushFront(pHead, 6);ListDestory(&pHead);
}