带头结点的双向循环链表

目录

带头结点的双向循环链表

 1.存储定义

2.结点的创建

3.结点的初始化

4.尾插结点

5.尾删结点

6.头插结点

7.头删结点 

8.查找并返回结点

9.在pos结点前插入结点

10.删除pos结点

11.打印链表

 12.销毁链表

13.头插结点2.0版

 14.尾插结点2.0版

---

前言：

当我们使用单链表时，想要去找到前面的前驱结点的时候，我们发现了受到限制，因为当时的结点只能去找后面的结点。

于是，就到了这里的带头结点的双向循环链表。

如图：

首先给出  双向链表的定义：是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。

那双向循环链表就是最后一个结点的next指向头结点，头结点的前驱指向尾结点。

带头结点的双向循环链表

 1.存储定义

typedef int CLDataType;typedef  struct ListNode
{CLDataType val;struct ListNode* next; //存放后面结点的指针struct ListNode* pre;  //存放前面结点的指针
}ListNode;

2.结点的创建

结点的创建，刚开始创建头结点我们一般会采用二级指针的方式，这里我们采用使用函数返回值的形式来避免野指针问题。

//创建链表
ListNode* CreateNode(CLDataType x) 
{//这里采用返回值的形式进行创建结点ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL) {perror("malloc");exit(-1);}newnode->val = x;newnode->pre = NULL;newnode->next = NULL;return newnode;
}

 如果是刚开始创建的头节点的话：

3.结点的初始化

这个时候就能体现带头结点双向循环链表的好处了

ListNode* InitNode() 
{ListNode* phead = CreateNode(-1);//让头节点的前驱和后继结点都指向自己phead->next = phead;	phead->pre = phead;return phead;
}

 因为修改了头结点，所以接着使用函数返回值的形式。

注意：初始化时，头结点的前驱和后继指针都指向自己。如图：

4.尾插结点

之前的单链表尾插需要遍历整个链表去找尾结点，但是，这里是带头结点的双向循环链表，只需去找头结点的前驱结点就找到了尾结点。

//尾插结点
void ListPushBack(ListNode* phead, CLDataType x) 
{assert(phead);ListNode* newnode = CreateNode(x);ListNode* tail = phead->pre;tail->next = newnode; //之前的尾结点的后继指针指向新结点newnode->pre = tail;  //新结点的前驱指向之前的尾结点newnode->next = phead; //新结点的后继指针指向头结点phead->pre = newnode;  //头结点的前驱指向

 当链表中只有一个头结点的时候，tail指向自己。

 再继续尾插时，仍是这样。

5.尾删结点

 一般都是先找到尾节结点，然后再去找到尾结点的前一个结点Pre。Pre指向头结点，头结点的前驱指向Pre。之后再删去尾节结。

//尾删结点
void ListPopBack(ListNode* phead)
{assert(phead);assert(phead->next != phead); //避免只有一个头结点ListNode* tail = phead->pre;ListNode* Pre = tail->pre; //用来记录尾结点的前一个结点Pre->next = phead;phead->pre = Pre;free(tail);tail = NULL;
}

注意：当只有一个头结点的情况时，说明已经没有链表结点。所以不能进行删除。进而这里采用，assert( phead->next != phead) 来避免此情况。

6.头插结点

和单链表的头插相似，用next指针记录头结点的下一个结点。先让新结点与next指针指向的结点建立连接，再与头结点建立连接。

//头插结点
void ListPushFront(ListNode* phead,CLDataType x) 
{assert(phead);ListNode* newnode = CreateNode(x);ListNode* next = phead->next; //记录头结点后的第一个结点newnode->next = next;next->pre = newnode;phead->next = newnode;newnode->pre = phead;
}

7.头删结点 

这里需要注意的是避免只有一个头结点的情况下，删除结点，这样使用同尾删结点一样的方法，通过断言 assert(phead->next != phead);

//头删结点
void ListPopFront(ListNode* phead) 
{assert(phead);assert(phead->next != phead);phead->next = phead->next->next;phead->next->next->pre = phead;
}

8.查找并返回结点

这里采用cur指针去遍历链表，找到就返回结点，没有找到就返回空。

//查找并返回结点
ListNode* ListFind(ListNode* phead, CLDataType x) 
{assert(phead);ListNode* cur = phead->next;while (cur != phead) {if (cur->val == x){return cur;}cur = cur->next;}return NULL;
}

9.在pos结点前插入结点

因为是带头结点的双向循环链表，这样就可以直接进行插入。

//在pos前面插入结点
void ListInsert(ListNode* pos, CLDataType x) 
{assert(pos);ListNode* newnode = CreateNode(x);//注意顺序//先让后驱建立连接newnode->next = pos;pos->pre->next = newnode;//再前驱建立连接newnode->pre = pos->pre;pos->pre = newnode;
}

10.删除pos结点

 修改pos的前驱和后继

//删除pos位置的结点
void ListErase(ListNode* pos) 
{assert(pos);pos->pre->next = pos->next;pos->next->pre = pos->pre;
}

11.打印链表

//打印链表
void ListPrint(ListNode* phead) 
{assert(phead);ListNode* cur = phead->next;printf("phead<==>");while (cur != phead) {printf("%d<==>", cur->val);cur = cur->next;}printf("\n");
}

 12.销毁链表

//销毁链表
void ListDestory(ListNode* phead) 
{assert(phead);ListNode* cur = phead->next;while (cur != phead){ListNode* next = cur->next;free(cur);cur = next;}free(phead);phead = NULL;
}

13.头插结点2.0版

这里我们借助 在pos结点前插入结点 的接口。

头插结点，那就是把pos结点变为 phead->next 的结点。这样结点的插入就模拟了头插结点，从而减少了一写代码的工作量。

//头插结点2.0
void ListushFront(ListNode* phead, CLDataType x)
{assert(phead);ListNode* newnode = CreateNode(x);ListNode* next = phead->next; //记录头结点后的第一个结点ListInsert(next,x); //这里的next相当于pos结点
}

例如  ：在 1结点 前插入 结点25

 

 14.尾插结点2.0版

根据带头结点的双向循环链表的特性，再借助前面的 在pos结点前插入结点（ListInsert） 的接口

这时我们会想到的就是 尾插结点不是在尾结点的后面进行插入的吗，而ListInsert是在pos前面进行结点的插入。 这时就采用  在头结点的前进行插入结点，从而达到尾插结点的特性。

//尾插结点
void ListPushBack(ListNode* phead, CLDataType x)
{assert(phead);ListNode* newnode = CreateNode(x);ListInsert(phead,x);
}