[数据结构] 双向循环链表的基础操作

ゝ一世哀愁。 2022-10-20 13:41 165阅读 0赞

本篇文章主要说明的是带头双向循环链表的基础操作，如果对链表概念不太清楚的可以点击这篇文章进行了解。[链表的基本结构与操作][Link 1]。

### 目录 ###

*  一. 基本结构
 *  二. 基础操作
 *   *  1. 在指定位置之前插入元素
     *  2. 删除指定位置元素
     *  3. 尾插、头插、尾删、头删
     *  4. 双向链表打印
     *  5. 链表销毁

# 一. 基本结构 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center]

与单链表不同，每一个节点都增加了一个指向前驱的节点，并且首届点和尾节点分别指向开头与结尾，构成双向循环链表。  
  接下来的篇幅，主要讲述双向链表与单链表操作的不同之处。

# 二. 基础操作 #

## 1. 在指定位置之前插入元素 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 1]

void ListInsert(ListNode* pos, LTDataType x)
    { 
    	if (NULL == pos)
    		return;
    
    	ListNode* pNew = BuyNewNode(x);
    	pNew->_prev = pos->_prev;
    	pNew->_next = pos;
    	pos->_prev->_next = pNew;
    	pos->_prev = pNew;
    }

## 2. 删除指定位置元素 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 2]

void ListErase(ListNode* pos)
    { 
    	if (NULL == pos)
    		return;
    
    	pos->_prev->_next = pos->_next;
    	pos->_next->_prev = pos->_prev;
    
    	free(pos);
    }

## 3. 尾插、头插、尾删、头删 ##

这次操作起始是对`head`节点前后进行操作，所以可以复用上述代码。原理相同。

// 双向链表尾插
    // 实则项双向链表的 head 之前插入，所以可以复用ListInsert()代码
    void ListPushBack(ListNode* pHead, LTDataType x)
    { 
    	if (NULL == pHead)
    		return;
    
    	ListInsert(pHead, x);
    }
    
    // 双向链表尾删
    // 删除head之前的元素
    void ListPopBack(ListNode* pHead)
    { 
    	if (NULL == pHead)
    		return;
    
    	ListErase(pHead->_prev);
    }
    
    // 双向链表头插
    // 在head之后插入
    void ListPushFront(ListNode* pHead, LTDataType x)
    { 
    	if (NULL == pHead)
    		return;
    
    	ListInsert(pHead->_next, x);
    }
    
    // 双向链表头删
    void ListPopFront(ListNode* pHead)
    { 
    	if (NULL == pHead)
    		return;
    
    	ListErase(pHead->_next);
    }

## 4. 双向链表打印 ##

因为链表为循环结构，所以要在遇到头节点时结束循环。

// 双向链表打印
    void ListPrint(ListNode* pHead)
    { 
    	ListNode* pCur = pHead->_next;
    
    	while (pCur != pHead)
    	{ 
    		printf("%d->", pCur->_data);
    		pCur = pCur->_next;
    	}
    	printf("\n");
    }

## 5. 链表销毁 ##

// 双向链表销毁
    void ListDestory(ListNode** pHead)
    { 
    	assert(pHead);
    
    	ListNode* pCur = (*pHead)->_next;
    
    	while (pCur != *pHead)
    	{ 
    		(*pHead)->_next = pCur->_next;
    
    		free(pCur);
    		pCur = (*pHead)->_next;
    	}
    
    	free(*(pHead));
    	*pHead = NULL;
    }

[Link 1]: https://blog.csdn.net/weixin_43717520/article/details/115423398?spm=1001.2014.3001.5501
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221020/b91e292e199544d0803703183eb93ee5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221020/733df723fbf9433ea7ce3b6918f2c7a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221020/dccf78f203bc44b092673b97d2f5c068.png