链表(二) 双链表操作详解

淩亂°似流年 2024-03-23 17:43 108阅读 0赞

#### 文章目录 ####

*  四、双向带头循环链表的实现
 *   *  List.h
     *  List.c
     *   *  创建返回链表的头结点
         *  双向链表打印
         *  双向链表尾插
         *  双向链表尾删
         *  双向链表头插
         *  双向链表头删
         *  双向链表查找
         *  双向链表在pos的前面进行插入
         *  双向链表删除pos位置的节点
 *  五、单链表与双链表比较

**什么是链表及单链表的实现请跳转：** [链表(一) 单链表操作详解][Link 1]  
![在这里插入图片描述][0a0b64f66f694aac8d21cac49eb62eec.png]

## 四、双向带头循环链表的实现 ##

![在这里插入图片描述][0eeeb91fbf8847a8b6a885048a749862.png]

![在这里插入图片描述][c639336fd5d74e93866edb8385a0ad61.png]  
**代码结构设计：**

*  List.h: 存放链表结构及需要用到的头文件，函数声明等
 *  List.c: 各种操作函数的具体实现

### List.h ###

#pragma once
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    
    // 带头+双向+循环链表增删查改实现
    
    typedef int LTDataType;
    
    typedef struct ListNode
    {
        
    	LTDataType data;
    	struct ListNode* next;
    	struct ListNode* prev;
    }ListNode;
    
    // 创建返回链表的头结点.
    ListNode* ListCreate();
    // 双向链表打印
    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);

### List.c ###

#include "List.h"
    
    //创建节点,此函数用于方便创建节点
    ListNode* ListBuy(int x)
    {
        
    	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    	if (node == NULL)
    	{
        
    		perror("malloc fail");
    		exit(-1);
    	}
    
    	node->data = x;
    	node->next = NULL;
    	node->prev = NULL;
    
    	return node;
    }

#### 创建返回链表的头结点 ####

ListNode* ListCreate()
    {
        
    	ListNode* head = ListBuy(0);
    
    	head->next = head;
    	head->prev = head;
    
    	return head;
    }

![在这里插入图片描述][e8239b3e81fa4623bd77b2f1cb79c32b.png]

#### 双向链表打印 ####

void ListPrint(ListNode* pHead)
    {
        
    	assert(pHead);
    	ListNode* cur = pHead->next;
    	printf("head <=> ");
    
    	while (cur != pHead)
    	{
        
    		printf("%d <=> ", cur->data);
    		cur = cur->next;
    	}
    	printf("\n");
    }

#### 双向链表尾插 ####

void ListPushBack(ListNode* pHead, LTDataType x)
    {
        
    	assert(pHead);
    
    	ListNode* newNode = ListBuy(x);
    	ListNode* tail = pHead->prev;
    
    	tail->next = newNode;
    	newNode->prev = tail;
    
    	pHead->prev = newNode;
    	newNode->next = pHead;
    }

![在这里插入图片描述][da5e8b9d081d4956b16ec912080fd355.png]

#### 双向链表尾删 ####

void ListPopBack(ListNode* pHead)
    {
        
    	assert(pHead);
    	assert(pHead->next!=pHead);
    
    	ListNode* tail = pHead->prev;
    	ListNode* tailPrev = tail->prev;
    	free(tail);
    
    	tailPrev->next = pHead;
    	pHead->prev = tailPrev;
    }

![在这里插入图片描述][6a34e360b1df4860805dfd668d8e34ad.png]

#### 双向链表头插 ####

void ListPushFront(ListNode* pHead, LTDataType x)
    {
        
    	assert(pHead);
    
    	ListNode* first = pHead->next;
    	ListNode* newNode = ListBuy(x);
    
    	pHead->next = newNode;
    	newNode->prev = pHead;
    
    	newNode->next = first;
    	first->prev = newNode;
    }

![在这里插入图片描述][f84788933ef1484fa7ace4d9e76e377f.png]

#### 双向链表头删 ####

void ListPopFront(ListNode* pHead)
    {
        
    	assert(pHead);
    	assert(pHead->next!=pHead);
    
    	ListNode* first = pHead->next;
    	ListNode* second = pHead->next->next;
    	free(first);
    
    	pHead->next = second;
    	second->prev = pHead;
    }

![在这里插入图片描述][0a24ee408db24817890c2023cdf0b83e.png]

#### 双向链表查找 ####

ListNode* ListFind(ListNode* pHead, LTDataType x)
    {
        
    	assert(pHead);
    
    	ListNode* cur = pHead->next;
    
    	while (cur != pHead)
    	{
        
    		if (cur->data == x)
    		{
        
    			return cur;
    		}
    		cur = cur->next;
    	}
    	return NULL;
    }

#### 双向链表在pos的前面进行插入 ####

void ListInsert(ListNode* pos, LTDataType x)
    {
        
    	assert(pos);
    
    	ListNode* posPrev = pos->prev;
    	ListNode* newNode = ListBuy(x);
    
    	posPrev->next = newNode;
    	newNode->prev = posPrev;
    
    	newNode->next = pos;
    	pos->prev = newNode;
    }

![在这里插入图片描述][9a6e9cf2e1a649b99dc9417377fabd53.png]

#### 双向链表删除pos位置的节点 ####

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

![在这里插入图片描述][271e1b3599bf457b8920a380a006c779.png]

## 五、单链表与双链表比较 ##

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>单链表</th> 
   <th>双链表</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>存储空间</td> 
   <td>物理上一定连续</td> 
   <td>逻辑上连续，物理上不一定</td> 
  </tr> 
  <tr> 
   <td>随机访问</td> 
   <td>支持 ：O(1)</td> 
   <td>不支持 ：O(n)</td> 
  </tr> 
  <tr> 
   <td>任意位置插入删除元素</td> 
   <td>可能需要搬移元素，效率低：O(N)</td> 
   <td>只需修改指针指向</td> 
  </tr> 
  <tr> 
   <td>插入</td> 
   <td>动态顺序表，空间不够时需要扩容</td> 
   <td>没有容量的概念</td> 
  </tr> 
  <tr> 
   <td>应用场景</td> 
   <td>元素高效存储+频繁访问</td> 
   <td>任意位置插入和删除频繁</td> 
  </tr> 
  <tr> 
   <td>缓存利用率</td> 
   <td>高</td> 
   <td>低</td> 
  </tr> 
 </tbody> 
</table>

[Link 1]: https://blog.csdn.net/zcxyywd/article/details/131993161?spm=1001.2014.3001.5501
[0a0b64f66f694aac8d21cac49eb62eec.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/cdacc35c703b44c585399c8ffcd7fa6d.png
[0eeeb91fbf8847a8b6a885048a749862.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/ebac34067e5c4798bace04cca3409cef.png
[c639336fd5d74e93866edb8385a0ad61.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/dc46b5374e884adfa683f755a88fbaf1.png
[e8239b3e81fa4623bd77b2f1cb79c32b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/3929e85741d34c10ba2796ac1cb32578.png
[da5e8b9d081d4956b16ec912080fd355.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/989234f0371647368cd8fa4699698474.png
[6a34e360b1df4860805dfd668d8e34ad.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/82ecaaf9a63745c9b1fd002d66bf1b7b.png
[f84788933ef1484fa7ace4d9e76e377f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/114b60aacb0c46bf873d6b625a8808f7.png
[0a24ee408db24817890c2023cdf0b83e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/67bddda7dbeb43448e8907184f195f81.png
[9a6e9cf2e1a649b99dc9417377fabd53.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/3a6e64ef4ddf493785067b1338e213a7.png
[271e1b3599bf457b8920a380a006c779.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/b93c9dfa38d843fc89ec8d11f2517cf5.png