【数据结构】双向带头（哨兵位）循环链表 —详细讲解（赋源码）

avatar
作者
猴君
阅读量:3

欢迎来到我的Blog，点击关注哦💕

前面介绍单向不带头（哨兵位）链表，双向相比于单向而言，存贮，查找，会更加便利。

前言

双向循环列表是一种特殊的数据结构，它结合了双向链表和循环链表的特点。在双向循环列表中，每个节点除了拥有指向下一个节点的指针外，还拥有指向上一个节点的指针。此外，列表的头节点和尾节点通过这些指针相互连接，形成一个闭环。这种结构允许从任何一个节点开始，既可以向前遍历，也可以向后遍历，直到回到起点，从而实现高效的双向遍历。

一、双向带头循环链表的基本介绍

  • 定义节点结构：每个节点包含数据部分和两个指针部分，分别指向前一个节点和后一个节点。

  • 创建头节点：头节点是双向循环列表的起始点，它的前驱指针指向自己，后继指针也指向自己，形成一个闭环。

  • 插入节点：在特定位置插入新节点时，需要更新新旧节点的前驱和后继指针，确保列表的完整性。

  • 删除节点：删除特定节点时，同样需要更新前后节点的指针，避免出现悬空指针。

  • 遍历列表：可以通过前驱指针或后继指针从任意节点开始，向前或向后遍历整个列表。

双向带头链表的操作

常见操作包括初始化、插入、删除、查找和遍历。这些操作通常涉及到对链表节点的指针进行操作，以实现数据的动态管理。

双向带头循环链表基本理解

headAbCDE....

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

2.1 双向带头循环链表的功能

//链表初始化创建哨兵位 ListNode* ListInit(); //连接表增加节点 ListNode* BuyNewNode(ListDataType x); //链表打印 void DlistPrint(ListNode* phead); //链表尾插 void DLlistPushBack(ListNode* phead, ListDataType x); //链表尾删 void DLlistPopBack(ListNode* phead); //链表头插 void DLlistPushFront(ListNode* phead, ListDataType x); //链表头删 void DLlistPopFront(ListNode* phead); //链表查找 ListNode* DListFind(ListNode* phead, ListDataType pos); //链表pos插入 void DListInset(ListNode* pos, ListDataType); //链表pos删除 void DListErase(ListNode* phead, ListNode* pos); //链表销毁 void DListDestory(ListNode* phead);

2.2 定义节点结构体

由于是双向带头，需要定义一个next和prev。

typedef int ListDataType;  typedef struct DList { 	int data; 	struct Dlist* prev; 	struct Dlist* next;  }ListNode;

2.3 链表的增加节点

这里可以相比较于单链表的操作，进行操作。

ListNode* BuyNewNode(ListDataType x) { 	ListNode* newcode = (ListNode*)malloc(sizeof(ListNode)); 	if (newcode == NULL) 	{ 		perror("malloc fail"); 		return NULL; 	}  	newcode->data = x; 	newcode->next = NULL; 	newcode->prev = NULL; 	return newcode;  }

2.4 链表的初始化

这个操作就是带头。

//链表初始化创建哨兵卫 ListNode* ListInit() { 	ListNode* head = BuyNewNode(-1); 	head->next = head; 	head->prev = head; 	return head; }

2.5 链表的遍历

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

2.6 链表的尾插

由于双向链表结构的特殊性，相比于单链表的效率更加高。

操作就是哨兵位的上一个节点，进行插入。

//链表尾插 void DLlistPushBack(ListNode* phead, ListDataType x) { 	assert(phead); 	ListNode* newcode = BuyNewNode(x); 	ListNode* tail = phead->prev; 	tail->next = newcode; 	newcode->prev = tail; 	newcode->next = phead; 	phead->prev = newcode;  }

2,7 链表的尾删

单链表进行尾部删的时候会进行断言，判断链表是否为空，双向链表也是如此，但是进行的操作是哨兵位的上一个节点或者下一个节点是否指向自己。

判断是否为空链表

我们利用bool类型判断真或者假

bool ListEmpty(ListNode* phead) { 	assert(phead); 	return phead->prev == phead; }

尾删操作

//链表尾删 void DLlistPopBack(ListNode* phead) { 	assert(phead); 	assert(!ListEmpty(phead)); 	ListNode* tail = phead->prev; 	ListNode* tailprev = tail->prev;  	tailprev->next = phead; 	phead->prev = tailprev; 	free(tail); 	tail = NULL; }

2.8 链表的头插

记录哨兵位下一个节点，进行头插入。

//链表头插 void DLlistPushFront(ListNode* phead, ListDataType x) { 	assert(phead);  	ListNode* newcode = BuyNewNode(x); 	ListNode* cur = phead->next; 	phead->next = newcode; 	newcode->prev = phead; 	newcode->next = cur; 	cur->prev = newcode; }

2.9 链表的头部删

头删的操作同，尾部删除一样，就是换了哥位置。(但是还是要注意进行判断链表为空的问题)

void DLlistPopFront(ListNode* phead) { 	assert(phead); 	assert(!ListEmpty(phead));  	ListNode* cur = phead->next; 	ListNode* curnext = cur->next; 	phead->next = curnext; 	curnext->prev = phead; 	free(cur); 	cur = NULL;  }

2.10 链表的查找

链表的查找的时候返回写成结构体指针的形式，以便于进行指定位置的插入和删除。

//链表查找 ListNode* DListFind(ListNode* phead, ListDataType pos) { 	assert(phead);  	ListNode* cur = phead->next; 	while (cur != phead && cur->data != pos) 	{ 		if (cur->data == pos) 		{ 			break; 		} 		cur = cur->next; 	} 	return cur; }

2.11 链表指定位置的插入

在这里面不运用二级指针的原因就是我们改变的是结构体的变量，并不是结构体指针。

//链表pos插入 void DListInset( ListNode* pos,ListDataType x) { 	assert(pos); 	 	ListNode* newcode = BuyNewNode(x);  	ListNode* cur = pos->prev;  	cur->next = newcode; 	newcode->prev = cur; 	newcode->next = pos; 	pos->prev = newcode;  }

2.12 链表指定位置的删除

//链表pos删除 void DListErase(ListNode* phead, ListNode* pos) { 	assert(!ListEmpty(phead)); 	assert(pos);  	ListNode* posprev = pos->prev; 	ListNode* posnext = pos->next;  	posprev->next = posnext; 	posnext->prev = posprev; 	free(pos);     //pos = NULL; 	//由于一级指针，NULL改变不了形式参数 	 }

2.13 链表的销毁

//链表销毁 void DListDestory(ListNode* phead) { 	assert(phead);  	ListNode* cur = phead->next;  	while (cur != phead) 	{ 		ListNode* curnext = cur->next; 		free(cur); 		//在循环第一句自动下一步 		cur = curnext; 		 	} 	//释放哨兵位头节点 	//不需要置空，形参数 	free(phead); }

源码

DList.h

#pragma once   #include <stdio.h> #include <assert.h> #include <stdlib.h> #include <stdbool.h>   typedef int ListDataType;  typedef struct DList { 	int data; 	struct Dlist* prev; 	struct Dlist* next;  }ListNode;  //链表初始化创建哨兵卫 ListNode* ListInit(); //连接表增加节点 ListNode* BuyNewNode(ListDataType x); //链表打印 void DlistPrint(ListNode* phead); //链表尾插 void DLlistPushBack(ListNode* phead, ListDataType x); //链表尾删 void DLlistPopBack(ListNode* phead); //链表头插 void DLlistPushFront(ListNode* phead, ListDataType x); //链表头删 void DLlistPopFront(ListNode* phead); //链表查找 ListNode* DListFind(ListNode* phead, ListDataType pos); //链表pos插入 void DListInset(ListNode* pos, ListDataType); //链表pos删除 void DListErase(ListNode* phead, ListNode* pos); //链表销毁 void DListDestory(ListNode* phead);

DList.c

#define  _CRT_SECURE_NO_WARNINGS   1  #include "DList.h"  ListNode* BuyNewNode(ListDataType x) { 	ListNode* newcode = (ListNode*)malloc(sizeof(ListNode)); 	if (newcode == NULL) 	{ 		perror("malloc fail"); 		return NULL; 	}  	newcode->data = x; 	newcode->next = NULL; 	newcode->prev = NULL; 	return newcode;  }  //链表初始化创建哨兵卫 ListNode* ListInit() { 	ListNode* head = BuyNewNode(-1); 	head->next = head; 	head->prev = head; 	return head; }  //链表打印 void DlistPrint(ListNode* phead) { 	ListNode* cur = phead->next; 	printf("<-head->"); 	while (cur != phead) 	{ 		printf("%d<->", cur->data); 		cur = cur->next; 	} 	printf("\n"); }  //链表尾插 void DLlistPushBack(ListNode* phead, ListDataType x) { 	assert(phead); 	ListNode* newcode = BuyNewNode(x); 	ListNode* tail = phead->prev; 	tail->next = newcode; 	newcode->prev = tail; 	newcode->next = phead; 	phead->prev = newcode;  }  //判断链表是不是空 bool ListEmpty(ListNode* phead) { 	assert(phead); 	return phead->prev == phead; }   //链表尾删 void DLlistPopBack(ListNode* phead) { 	assert(phead); 	assert(!ListEmpty(phead)); 	ListNode* tail = phead->prev; 	ListNode* tailprev = tail->prev;  	tailprev->next = phead; 	phead->prev = tailprev; 	free(tail); 	tail = NULL; }  //链表头插 void DLlistPushFront(ListNode* phead, ListDataType x) { 	assert(phead);  	ListNode* newcode = BuyNewNode(x); 	ListNode* cur = phead->next; 	phead->next = newcode; 	newcode->prev = phead; 	newcode->next = cur; 	cur->prev = newcode; }  //链表头删 void DLlistPopFront(ListNode* phead) { 	assert(phead); 	assert(!ListEmpty(phead));  	ListNode* cur = phead->next; 	ListNode* curnext = cur->next; 	phead->next = curnext; 	curnext->prev = phead; 	free(cur); 	cur = NULL;  }  //链表查找 ListNode* DListFind(ListNode* phead, ListDataType pos) { 	assert(phead);  	ListNode* cur = phead->next; 	while (cur != phead && cur->data != pos) 	{ 		if (cur->data == pos) 		{ 			break; 		} 		cur = cur->next; 	} 	return cur; }  //链表pos插入 void DListInset( ListNode* pos,ListDataType x) { 	assert(pos); 	 	ListNode* newcode = BuyNewNode(x);  	ListNode* cur = pos->prev;  	cur->next = newcode; 	newcode->prev = cur; 	newcode->next = pos; 	pos->prev = newcode;  }  //链表pos删除 void DListErase(ListNode* phead, ListNode* pos) { 	assert(!ListEmpty(phead)); 	assert(pos);  	ListNode* posprev = pos->prev; 	ListNode* posnext = pos->next;  	posprev->next = posnext; 	posnext->prev = posprev; 	free(pos); 	//由于一级指针，NULL改变不了形式参数 	 }  //链表销毁 void DListDestory(ListNode* phead) { 	assert(phead);  	ListNode* cur = phead->next;  	while (cur != phead) 	{ 		ListNode* curnext = cur->next; 		free(cur); 		//在循环第一句自动下一步 		cur = curnext; 		 	} 	//释放哨兵位头节点 	//不需要值空，形参数 	free(phead); }

test.c

#define  _CRT_SECURE_NO_WARNINGS   1  #include "DList.h"  void testDlist1() { 	ListNode* plist = ListInit(); 	DLlistPushBack(plist, 1); 	DLlistPushBack(plist, 2); 	DLlistPushBack(plist, 3); 	DLlistPushBack(plist, 4);  	 	ListNode* ret = DListFind(plist, 2);  	//ret->data = (ret->data) * 2; 	DListInset(ret, 40); 	DListErase(plist, ret);  	DLlistPopBack(plist);  	DlistPrint(plist);  } void testDlist2() { 	ListNode* plist = ListInit(); 	DLlistPushFront(plist, 1); 	DLlistPushFront(plist, 2); 	DLlistPushFront(plist, 3); 	DLlistPushFront(plist, 4); 	DLlistPushFront(plist, 5);  	DLlistPopFront(plist); 	DLlistPopFront(plist);    	DlistPrint(plist);  }   int main() { 	testDlist1(); 	//testDlist2();   	return 0; }
相关阅读
  1. 如何查看和设置我的Android N设备的权限？
  2. 如何在安卓手机上自定义应用图标？
  3. 如何在安卓微信中同时听语音和查看图片？
  4. 华为哪些设备将支持升级至安卓7.0？
  5. 微信安卓软件中Q10功能有哪些独特之处？
  6. 安卓用户如何挑选最佳视频播放器应用？
  7. 安卓系统中用户文件目录的确切位置是什么？
  8. 小米4用户如何安全升级到安卓8.0系统？
  9. 如何成功将魅蓝5升级至安卓原生7.0版本？
  10. 16GB存储的安卓手机是否能满足日常需求？

广告一刻

为您即时展示最新活动产品广告消息，让您随时掌握产品活动新动态！