C语言实现链表【二】带头双向循环链表

青旅半醒 2022-12-29 09:14 218阅读 0赞

# 带头双向循环链表 #

*  ### 结构描述： ###

带头双向循环链表:结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以店会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

![20201221151445231.png][]

// 2、带头+双向+循环链表增删查改实现
    typedef int LTDataType;
    typedef struct ListNode
    {
    	LTDataType _data;
    	struct ListNode* _next;
    	struct ListNode* _prev;
    }ListNode;
    
    typedef struct Linklist
    {
    	struct ListNode* _head;
    }Linklist;

**带头双向循环链表中，链表结构包含一个头节点，但头节点不保存数据，第一个数据节点为head->next，同时每一个数据节点结构包含三部分，一部分为data数据，一部分为prev指向前一节点，另外一部分next指向后一节点，结构虽然复杂，但执行数据操作的过程中发现插入和删除操作的算法时间复杂度均为O（1）**

*  ### 接口声明： ###

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

**下面开始实现每一个接口，完成接口定义：其中接口实现可以按照如下的链表结构来理解其中指针的指向**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70][]

**（1）初始化：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 1][]

// 创建返回链表的头结点.
    ListNode* ListInit(Linklist* plist)
    {
    	
    	plist->_head = (struct ListNode*)malloc(sizeof(struct ListNode));
    	plist->_head->_prev = plist->_head->_next = plist->_head;
    	return plist->_head;
    }

**（2）创建新节点**

//创建新节点
    ListNode* createNode(LTDataType x)
    {
    	struct ListNode* newnode= (struct ListNode*)malloc(sizeof(struct ListNode));
    	newnode->_data = x;
    	newnode->_next = newnode->_prev = NULL;
    	return newnode;
    }

**（3）尾插：**

根据上述示例结构，在尾部插入一个新节点

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 2][]

代码如下：更改四个指针指向即可完成

//尾插
    void ListPushBack(Linklist* plist, LTDataType x)
    {
    	
    	struct ListNode* newnode = createNode(x);
    	struct ListNode* tail = plist->_head->_prev;
    
    	tail->_next = newnode;
    	newnode->_prev = tail;
    
    	plist->_head->_prev = newnode;
    	newnode->_next = plist->_head;
    	
    
    	//ListInsert(plist->_head, x);//头前插入 即尾插
    }

考虑只有头结点情况

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 3][]

**发现以上代码对于只包含头结点的空链表依然适用，尾插不需要对只包含头结点的空链表特殊处理**

**（4）尾删**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 4][]

根据head->\_prev找到尾结点 从而记录尾结点前一节点 释放尾结点，更改四个指针指向

// 双向链表尾删
    void ListPopBack(Linklist* plist)
    {
    	//空链表不能删除，破坏双向带头循环链表结构
    	if (plist->_head == plist->_head->_next)
    		return;
    	struct ListNode* tail = plist->_head->_prev;
    	struct ListNode* prev = tail->_prev;
    	free(tail);
    	prev->_next = plist->_head;
    	plist->_head->_prev = prev;
    	//ListErase(plist->_head->_prev);
    }

考虑只有头结点 是否可以删除尾结点操作

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 5][]

删除后会破坏了双向带头循环链表的结构，所以仅包含头结点的双向带头循环链表无法完成尾删操作

**（5）头插**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 6][]

//头插
    void ListPushFront(Linklist* plist, LTDataType x)
    {
    	struct ListNode* newnode = createNode(x);
    	struct ListNode* next = plist->_head->_next;
    	plist->_head->_next = newnode;
    	newnode->_prev = plist->_head;
    
    	newnode->_next = next;
    	next->_prev = newnode;
    	//ListInsert(plist->_head->_next, x);//头的下一个插入 ，即头插
    }

在头插的过程中，无论是否只有头结点，处理都是一样的 只不过只包含头结点的情况下，head->\_next=head->\_prev=head

**(6)头删**

![2020122116190599.png][]

头删是删除第一个数据节点，如果空链表 无法删除，否则破坏链表结构

// 双向链表头删
    void ListPopFront(Linklist* plist)
    {
    	if (plist->_head == plist->_head->_next)
    		return;
    	
    	struct ListNode* next = plist->_head->_next;
    	struct ListNode* nextnext = next->_next;
    	free(next);
    	nextnext->_prev = plist->_head;
    
    	plist->_head->_next = nextnext;
    	
    	//ListErase(plist->_head->_next);
    
    }

**（7）任意位置插入/删除**

// 双向链表在pos的前面进行插入
    void ListInsert(ListNode* pos, LTDataType x)
    {
    	struct ListNode* newnode = createNode(x);
    	struct ListNode* prev = pos->_prev;
    
    	pos->_prev = newnode;
    	newnode->_next = pos;
    
    	prev->_next = newnode;
    	newnode->_prev = prev;
    }

// 双向链表删除pos位置的节点
    void ListErase(ListNode* pos)
    {
    	if (pos->_next == pos->_prev)
    		return;
    	struct ListNode* next = pos->_next;
    
    	struct ListNode* prev = pos->_prev;
    	free(pos);
    	next->_prev = prev;
    
    	prev->_next = next;
    }

**（8）遍历链表打印**

void ListPrint(Linklist* plist)
    {
    	struct ListNode* cur = plist->_head->_next;
    	while (cur != plist->_head)
    	{
    		printf("%d ", cur->_data);
    		cur = cur->_next;
    	}
    	printf("\n");
    }

**（9）链表销毁**

//销毁链表
    void ListDestory(Linklist* plist)
    {
    	struct ListNode* cur = plist->_head->_next;//此处从第一个数据节点开始
    	while (cur != plist->_head)
    	{
    		struct ListNode* next = cur->_next;
    		free(cur);
    		cur = next;
    	}
    	free(plist->_head);//头结点作为特例删除
    }

**（10）测试代码:**

#include<stdio.h>
    
    #include"linklist.h"
    
    void test()
    {
    	struct Linklist plist;
    	ListInit(&plist);
    	printf("尾插：\n");
    	ListPushBack(&plist,1);
    	ListPushBack(&plist, 2);
    	ListPushBack(&plist, 3);
    	ListPushBack(&plist, 4);
    	ListPushBack(&plist, 5);
    	ListPrint(&plist);
    	printf("尾删：\n");
    	ListPopBack(&plist);
    	ListPrint(&plist);
    	ListPopBack(&plist);
    	ListPrint(&plist);
    	ListPopBack(&plist);
    	ListPrint(&plist);
    	ListPopBack(&plist);
    	ListPrint(&plist);
    	ListPopBack(&plist);
    	ListPrint(&plist);
    	printf("头插：\n");
    	ListPushFront(&plist, 1);
    	ListPushFront(&plist, 2);
    	ListPushFront(&plist, 3);
    	ListPushFront(&plist, 4);
    	ListPushFront(&plist, 5);
    	ListPrint(&plist);
    	printf("头删：\n");
    	ListPopFront(&plist);
    	ListPrint(&plist);
    	ListPopFront(&plist);
    	ListPrint(&plist);
    	ListPopFront(&plist);
    	ListPrint(&plist);
    	ListPopFront(&plist);
    	ListPrint(&plist);
    	ListPopFront(&plist);
    	ListPrint(&plist);
    }
    
    int main()
    {
    	test();
    }

**执行结果如下：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 7][]

[20201221151445231.png]: /images/20221120/df33d34774084d97b7fbea37298e014d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70]: /images/20221120/7c660435ba5641b89bf7ee3fe424b253.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 1]: /images/20221120/c12ca798a89947fe98adbbb63f34f9a9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 2]: /images/20221120/c79bdc3dfae546358cc9965411c74293.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 3]: /images/20221120/92b8e2a8036841fa8b08d24b0bdac0d0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 4]: /images/20221120/d301e1be31bf4c7ba03936fb16c25d73.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 5]: /images/20221120/21afcafd2c144650833b179559709136.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 6]: /images/20221120/af3cd27e5c834d02927cde67346d106e.png
[2020122116190599.png]: https://img-blog.csdnimg.cn/2020122116190599.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/2020122116373797.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx,size_16,color_FFFFFF,t_70