Data Structure--双向循环链表大部分基本接口的实现(仔细讲解)

àì夳堔傛蜴生んèń 2022-10-29 11:30 156阅读 0赞

# 双向循环链表 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]  
对于双向循环链表就是两个点:  
**1.元素之间相互指向**  
**2.头结点和末尾元素互相指向**  
只要满足这两个条件,就可以叫做双向循环链表  
这里又因为是双向的,所以对于双向循环链表来说,他有两个节点**prev**和**next** ,只有这样,才能进行相互指向,才能实现,很详细了,具体我来通过代码的实现来让大家具体理解.

//双向带头循环链表的节点
    typedef struct ListNode{ 
    
    	LDataType _data;
    	struct ListNode* _next;		//下一个节点的起始位置
    	struct ListNode* _prev;		//上一个节点的起始位置
    }ListNode;
    
    //双向带头循环链表
    typedef struct List{ 
    	struct ListNode* _head;
    }List;

# 接口声明 #

先写接口声明,在详细进行讲解

//1.创建一个新的双向循环链表
    ListNode* createListNode(LDataType val);
    //2.初始化
    void listInit(List*lst);
    //3.尾插
    void listPushBack(List* lst, LDataType val);
    //4.尾删
    void listPopBack(List* lst);
    //5.打印
    void printList(List* lst);
    //6.头插
    void listPushFront(List* lst,LDataType val);
    //7.头删
    void listPopFront(List* lst);
    //8.删除指定节点
    void listErase(List* lst, struct ListNode* node);
    //9.指定插入位置
    void listInsert(List* lst, struct ListNode* node, LDataType val);
    //10.销毁链表
    listDestory(List* lst);

# 接口实现 #

#### 1.创建一个新的双向循环链表 ####

因为对于双向链表的创建,我们也需要进行空间的申请,所以我们直接将其封装成一个函数,在进行插入函数的时候直接进行调用,就不用了每次都进行空间的申请,比较方便,也体现了封装的思想.

ListNode* createListNode(LDataType val){ 
    	
    	struct ListNode* node = (struct ListNode*)malloc(sizeof(ListNode));	//动态内存的申请
    	node->_data = val;	//赋予值
    	node->_next = NULL;	//为空
    	node->_prev = NULL;	//为空
    
    	return node;	//返回申请的
    }

#### 2.初始化 ####

初始化也比较简单,和**int i=0**;比较类似,就是申请一个空间,将0赋予即可

void listInit(List*lst){ 
    	
    	if (lst == NULL)	//判空
    		return;
    	//空链表
    	lst->_head = createListNode(0);		//创建空链表
    	lst->_head->_next = lst->_head->_prev = lst->_head;		//节点互相指向
    }

#### 3.尾插 ####

注意1位头结点 有234三个元素  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 1]  
1.添加新元素  
2.改变头结点和其他的指向即可

void listPushBack(List* lst, LDataType val){ 
    
    	if (lst == NULL)	//判空 
    		return;	
    
    	struct ListNode* last = lst->_head->_prev;		//因为是循环的,头结点之前也就是末尾
    	struct ListNode* newNode = createListNode(val);	//新元素
    	//_head .....last newNode 
    	last->_next = newNode;
    	newNode->_prev = last;		//按顺序互相交换,具体理解
    	
    	newNode->_next = lst->_head;
    	lst->_head->_prev = newNode;	//同上
    }

#### 4.尾删 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 2]  
1.只用改变其中两个节点的位置  
2.释放空间

void listPopBack(List* lst){ 
    	
    	if (lst == NULL)	//空链表判断
    		return;
    	
    	if (lst->_head->_next == lst->_head)	//不能删除头结点
    		return;
    	
    	struct ListNode* last = lst->_head->_prev;	//创建最后的节点
    	struct ListNode* prev = last->_prev;	//头结点
    
    	free(last);		//释放
    
    	lst->_head->_prev = prev;		//执行红色箭头的两个操作
    	prev->_next = lst->_head;
    
    }

#### 5.打印 ####

void printList(List* lst){ 
    
    	struct ListNode* cur = lst->_head->_next;	//指向下一个
    	
    	while (cur != lst->_head){ 		//循环
    		printf("%d ",cur->_data);	//打印
    		cur = cur->_next;			//循环指向
    	}
    	printf("\n");
    }

#### 6.头插 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 3]  
1.记住原来头结点之后的位置  
2.运用逻辑思维还原红色的四条线

void listPushFront(List* lst,LDataType val){ 
    
    	if (lst == NULL)
    		return;
    
    	struct ListNode* next = lst->_head->_next;	//记住地址
    	struct ListNode* newNode = createListNode(val);	//创建
    	
    	//head newNode next
    	lst->_head->_next = newNode;		//四条红线的还原
    	newNode->_prev = lst->_head;
    
    	newNode->_next = next;
    	next->_prev = newNode;
    }

#### 7.头删 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 4]  
1.记住3的地址  
2.改为红色箭头  
3.释放空间

void listPopFront(List* lst){ 
    	
    	if (lst == NULL||lst->_head->_next==lst->_head)		//判空
    		return;
    
    	struct ListNode* next = lst->_head->_next;		//记住地址
    	struct ListNode* nextnext = next->_next;
    	//head cur next
    	nextnext->_prev = lst->_head;	//红色剪头执行
    	lst->_head->_next = nextnext;
    	free(next);		//释放空间
    }

#### 8.删除指定节点 ####

对于删除指定节点和上面类似,也是记住后面的地址,然后用两条红色的线就可以解决,再对永建释放就可以了

void listErase(List* lst, struct ListNode* node){ 
    	
    	//不能删除head结点
    	if (lst==NULL||lst->_head == node)
    		return;
    
    	//prev node next
    	struct ListNode* prev = node->_prev;		//红线,比较简单,自己画图
    	struct ListNode* next = node->_next;
    
    	prev->_next = next;
    	next->_prev = prev;
    
    	free(node);		//释放
    }

#### 9.指定插入位置 ####

指定插入也一样,改变四条红线就可以,像上面的一样

void listInsert(List* lst, struct ListNode* node, LDataType val){ 
    
    	if (lst == NULL)		//判空
    		return;
    
    	struct ListNode* prev = node->_prev;		//要删除的后置节点地址
    	struct ListNode* newNode = createListNode(val);	//创建
    
    	//prev newNode node
    	prev->_next = newNode;	//执行四条红线
    	newNode->_prev = prev;
    
    	newNode->_next = node;
    	node->_prev = newNode;
    }

#### 10.销毁链表 ####

销毁很简单,循环遍历,进行释放就可以,最后在释放头结点

listDestory(List* lst){ 
    	
    	if (lst){ 
    		if (lst->_head){ 
    			struct ListNode* cur = lst->_head->_next;		//记住要删除的下一个节点,方便释放
    			while (cur != lst->_head){ 		//循环
    				
    				struct ListNode* next = cur->_next;
    				free(cur);		//释放
    				cur = next;		//下一个
    			}
    			free(lst->_head);	//循环完释放头结点
    		}
    	}
    }

今天的代码总的还可以,其实双向循环的效率要比其他的高很多,看着线条很多,其实所利用的复杂度大多数为**O(1)**,所以也是最常用的,大家一起加油!!!多敲代码!!!

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]: /images/20221024/bfa8f6fad5cc4ccca96317e8ece728bd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 1]: /images/20221024/e18c65a32006439c942b9d1364de5113.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 2]: /images/20221024/4182c1c7de674f0885b1803cdbe15270.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 3]: /images/20221024/8f05e876bc84459dbffa07ff47226bc2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 4]: /images/20221024/168555fe2500438e917a08bae4edacd1.png