单链表的特征就是：单向、不带头、非循环，你们可以叫它三无链表hhh，单向就是说链表的所有节点都是只有一个指针next，它只能链接一个节点的地址或者NULL；不带头就是没有哨兵位头节点，这个之后介绍；非循环就是链表中节点之间没有环相连。其次在上篇博客里还实现了单链表的初始化、申请新节点、头插头删、尾插尾删、在某个指定位置的插入删除等功能实现。

而今天实现的双向链表与单链表完全相反，接下来就带着大家来看一看。

一.双向链表

A.双向链表的含义

双向链表：Double List Node，它的特征为：带头+双向+循环。

带头：就是哨兵位头节点，哨兵位头节点是用动态申请（malloc、calloc、realloc）下的一个节点，它的里面绝不存储有效数据，即它不可以作为节点进行存值，但可以存储节点的地址，它最大的优势就是让链表的起始指针永远指向哨兵位头节点，由哨兵位头节点去插入或删除节点，这样做就不会修改链表起始指针，也就用不到二级指针；而单链表中没有哨兵头节点，所以常常要改变起始指针的指向，使用二级指针接收实参，才能去改变实参！！！

双向：单链表只有一个指针，所以一个节点只能链接一个地址；而双链表的节点中有两个指针地址，既可以链接它前面的节点地址，也可以链接它后面的节点地址，十分方便。

循环：便是双链表中头尾使用环去链接，链表的最后一个节点不会指向NULL，而是与头节点相互链接，便组成了循环。

如上图：双向链表的head结点就是哨兵位头节点，它用于指向第一个结点地址，而每个结点的后指针都相互指向下一个结点的前指针。

注：这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

B.双向链表的实现

1.双向链表的结构

共有三部分：一个数据域，两个指针域


typedef int DLTDataType;//重命名int结构用于双向链表，使用双向链表就用这种新结构，使用普通变量还是            
                        //使用int类型，重定义只是做一个区分而已。
 
typedef struct DListNode {	
	DLTDataType data;			//数据域
	struct DListNode* prev;		//前指针
	struct DListNode* next;		//后指针
}DLNode;//重定义结构体类型名称

2.链表的初始化

初始化图解：

函数代码：


//链表初始化
void DListInit(DLNode* phead) {
	DLNode* guard = (DLNode*)malloc(sizeof(DLNode));//哨兵位头节点
	if (guard == NULL) {
		prerror("malloc fail\n");
		return -1;
	}
	guard->prev = guard;
	guard->next = guard;
	return guard;
}

初始化便是要创建哨兵位头节点，因为哨兵位头节点不存储有效数据，且该开始两指针并不知道指向谁，所以根据双向链表循环的特性，就让该结点的两个指针自己指向自己。

3.动态申请节点函数

函数代码：


//动态申请节点函数
DLNode* BuyDLTNode( DLTDataType x) {
    
	DLNode* node = (DLNode*)malloc(sizeof(DLNode));
    //刚申请下的堆区空间有可能开辟失败，所以要进行检查
	if (node == NULL) {
		perror("malloc fail\n");
		return -1;
	}
//开辟好后就赋值
	node->data = x;
	node->prev = NULL;
	node->next = NULL;
	return node;
}

因为刚开辟下节点，还没有进行链接，所以先暂时让两指针存空。

4.打印双向链表函数

打印链表就是遍历每一个节点，因为双向链表为循环，尾节点不指向NULL，头尾相连，所以需要新的限制条件——哨兵位头节点，哨兵位头节点不存储有效数据，所以遍历指针只要遇到哨兵节点就会停止，即打印完毕！

函数代码：


//打印
void DListPrint(DLNode* phead) {
	assert(phead);
	DLNode* cur = phead->next;
	printf("guard<=>\n");
	while (cur != phead) {
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

5.尾部插入节点

图解：

情况一：

情况一讲解：之前对于单链表的尾插实现时需要进行找尾才能插入节点（需要遍历cur!=NULL才行），但是双向链表的尾插不同，它不需要遍历寻找，如图1，phead作为头指针，永远指向哨兵头，而哨兵头的prev指针却是与尾部节点d3相连（头尾组成循环相连），那么尾节点就一定是哨兵头的prev指向地址，所以不需要遍历，可以轻易的找到！

情况二：

情况一与情况二原理相同。

函数代码：


//链表尾插
void DListPushBack(DLNode* phead, DLTDataType x) {
	assert(phead);
	DLNode* tail = phead->prev;//找到尾  尾节点指针处在哨兵位头节点的prev
	DLNode* newnode = BuyDLTNode(x);//新节点
	//改变顺序
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

测试：


void TestDlist1() {
	DLNode* plist1=DListInit();
	//传参时，不需要传plist1的地址，因为函数不会改变plist1的指向，因为plist1永远指向哨兵位头节点，
	//使用哨兵位头节点进行改变，所以用plist传递，用一级指针接收就行
	DListPushBack(plist1, 1);
	DListPushBack(plist1, 2);
	DListPushBack(plist1, 3);
	DListPushBack(plist1, 4);
	DListPrint(plist1);
}
 
int main() {
	TestDlist1();
	return 0;
}

结果：

注：phead就等价于哨兵位头节点！

6.头插函数

图解：

函数代码：


//头插
void DListPushFront(DLNode* phead,DLTDataType x) {
	assert(phead);
	DLNode* first = phead->next;
	DLNode* newnode = BuyDLTNode(x);
	newnode->next = first;
	newnode->prev = phead;
	phead->next = newnode;
	first->prev = newnode;
}

测试：

7.尾删函数

图解：

情况一：当链表有多个节点时

情况二：当链表只有一个节点时，尾删后，哨兵位头节点的两个指针就会自己指向自己

函数代码：

关于头尾部的删除，需要进行检查链表是否为空，所以，我封装了一个检查函数：


//暴力检查
bool DListEmpty(DLNode* phead) {
	assert(phead);
	return phead->next == phead;
}

注：bool类型的返回值为true、false两种，若是phead->next==phead说明链表为空，那么assert(!DListEmpty(phead)==assert(NULL);函数就报错，且停止下面语句的执行；若是 phead->next !=phead说明链表不为空，那么assert(!DListEmpty(phead)这条语句就不起作用，检查通过，继续下面语句的执行。


//尾删
void DListPopBack(DLNode* phead) {
	assert(phead);
	//暴力检查
	assert(!DListEmpty(phead));
	DLNode* tail = phead->prev;
	DLNode* last = tail->prev;
	//改变顺序
	last->next = phead;
	phead->prev = last;
	//释放尾节点
	free(tail);
	tail = NULL;
 }

测试：

8.头删函数

图解：

函数代码：


//头删
void DListPopFront(DLNode* phead) {
	assert(phead);
	//暴力检查
	assert(!DListEmpty(phead));
	DLNode* first = phead->next;
	DLNode* second = first->next;
	phead->next = second;
	second->prev = phead;
	free(first);
	first = NULL;
}

测试：

9.链表查找函数

查找函数可以用来查找某个节点，还可以通过对查找到的节点进行修改、对指定位置的增删功能实现。

函数代码：


//链表查找
DLNode* DListFind(DLNode* phead, DLTDataType x) {
	assert(phead);
	DLNode* cur = phead->next;
	//遍历查找
	while (cur != phead){
		if (cur->data == x) {
			return cur;//找到了，返回
		}
		cur = cur->next;//继续往后找
	}
	return NULL;//找不到，返回空
}

测试：

10.在链表指定的位置前插入函数

图解：

函数代码：


//链表在指定位置pos前插入函数
void DListInsert(DLNode* pos, DLTDataType x) {
	//指定的位置不可以为空
	assert(pos);
	DLNode* last = pos->prev;
	DLNode* newnode = BuyDLTNode(x);
	last->next = newnode;
	newnode->prev = last;
	newnode->next = pos;
	pos->prev = newnode;
}

测试：

注：在某个位置前插入节点时，总要先找到pos的位置，然后才可以使用Insert函数！

11.在链表的pos位置处删除节点

图解：

函数代码：


//链表在指定位置pos处删除节点
void DListErase(DLNode* pos) {
	assert(pos);
	DLNode* later = pos->next;
	DLNode* last = pos->prev;
	last->next = later;
	later->prev = last;
	free(pos);
	pos = NULL;
}

测试：

12.求链表的长度函数

这个函数与打印函数原理相同，都是通过指针遍历每一个节点去统计节点个数。

函数代码：


//求链表的长度函数
size_t DListSize(DLNode* phead) {
	assert(phead);
	size_t n = 0;
	DLNode* cur = phead->next;
	while (cur != phead) {
		n++;
		cur = cur->next;
	}
	return n;
}

测试：

13.释放链表空间

函数代码：


//释放空间
void DListDestory(DLNode* phead) {
	assert(phead);
	DLNode* cur = phead->next;
	//以遍历节点的方式，一个一个的释放
	while (cur != phead) {
		DLNode* later = cur->next;
		free(cur);
		cur = NULL;
	}
	//释放完后，再把哨兵位头节点也释放掉
	free(phead);
	phead = NULL;
}

完整代码：

Test.c:


#define _CRT_SECURE_NO_WARNINGS 1
#include"DList.h"
 
//尾插
void TestDlist1() {
	DLNode* plist1=DListInit();
	//传参时，不需要传plist1的地址，因为函数不会改变plist1的指向，因为plist1永远指向哨兵位头节点，
	//使用哨兵位头节点进行改变，所以用plist传递，用一级指针接收就行
	printf("尾插\n");
	DListPushBack(plist1, 1);
	DListPushBack(plist1, 2);
	DListPushBack(plist1, 3);
	DListPushBack(plist1, 4);
	DListPrint(plist1);
 
	//尾删
	printf("\n尾删\n");
	printf("尾删第一次：");
	DListPopBack(plist1);
	DListPrint(plist1);
 
	printf("尾删第二次：");
	DListPopBack(plist1);
	DListPrint(plist1);
 
	printf("尾删第三次：");
	DListPopBack(plist1);
	DListPrint(plist1);
 
	printf("尾删第四次：");
	DListPopBack(plist1);
	DListPrint(plist1);
 
}
 
//头插
void TestDlist2() {
	DLNode* plist2 = DListInit();
	printf("头插\n");
	DListPushFront(plist2, 10);
	DListPushFront(plist2, 20);
	DListPushFront(plist2, 30);
	DListPushFront(plist2, 40);
	DListPrint(plist2);
 
	//头删
	printf("\n头删\n");
	printf("头删第一次：");
	DListPopFront(plist2);
	DListPrint(plist2);
 
	printf("头删第二次：");
	DListPopFront(plist2);
	DListPrint(plist2);
 
	printf("头删第三次：");
	DListPopFront(plist2);
	DListPrint(plist2);
 
	printf("头删第四次：");
	DListPopFront(plist2);
	DListPrint(plist2);
 
}
 
//查找，修改
void TestDlist3() {
	DLNode* plist3 = DListInit();
	printf("头插\n");
	DListPushFront(plist3, 10);
	DListPushFront(plist3, 20);
	DListPushFront(plist3, 30);
	DListPushFront(plist3, 40);
	DListPrint(plist3);
 
	DLNode* find = DListFind(plist3, 20);
	if (find) {
		printf("找到了\n");
		find->data = 999;
		printf("修改节点数值成功\n");
		DListPrint(plist3);
	}
	else {
		printf("没找到\n");
		return -1;
	}
}
 
//在某个位置pos前插入
void TestDlist4() {
	DLNode* plist4 = DListInit();
	printf("尾插\n");
	DListPushBack(plist4, 100);
	DListPushBack(plist4, 200);
	DListPushBack(plist4, 300);
	DListPushBack(plist4, 400);
	DListPrint(plist4);
 
	//在某个位置前插入
	//DLNode* find = DListFind(plist4, 100);//找个pos位置
	//if (find) {
	//	printf("找到了\n");
	//	DListInsert(find, 2999);
	//	DListPrint(plist4);
	//}
	//else {
	//	return -1;
	//}
 
 
	DLNode* find2 = DListFind(plist4, 400);//找个pos位置
	if (find2) {
		printf("找到了\n");
		DListInsert(find2, 6999);
		DListPrint(plist4);
	}
	else {
		return -1;
	}
}
 
//在某个位置pos删除节点
void TestDlist5() {
	DLNode* plist5 = DListInit();
	printf("尾插\n");
	DListPushBack(plist5, 100);
	DListPushBack(plist5, 200);
	DListPushBack(plist5, 300);
	DListPushBack(plist5, 400);
	DListPrint(plist5);
 
	//在某个位置删除
	DLNode* find = DListFind(plist5, 100);//找个pos位置
	if (find) {
		printf("找到了\n");
		DListErase(find);//删除值为100的节点
		DListPrint(plist5);
	}
	else {
		return -1;
	}
 
 
	//DLNode* find2 = DListFind(plist5, 400);//找个pos位置
	//if (find2) {
	//	printf("找到了\n");
	//	DListInsert(find2, 6999);
	//	DListPrint(plist5);
	//}
	//else {
	//	return -1;
	//}
}
 
 
void TestDlist6() {
	DLNode* plist6 = DListInit();
	size_t count = DListSize(plist6);//刚开始链表的长度为0
	printf("当前链表的长度为:%zu\n",count);
	
	DListPushBack(plist6, 100);
	DListPushBack(plist6, 200);
	DListPushBack(plist6, 300);
	DListPushBack(plist6, 400);
	DListPrint(plist6);
 
	count= DListSize(plist6);
	printf("当前链表的长度为:%zu", count);
 
 }
int main() {
	//TestDlist1();
	//TestDlist2();
	//TestDlist3();
	//TestDlist4();
	//TestDlist5();
	TestDlist6();
	return 0;
}

DList.c代码：


#define _CRT_SECURE_NO_WARNINGS 1
#include"DList.h"
 
//链表初始化
DLNode* DListInit() {
	DLNode* guard = (DLNode*)malloc(sizeof(DLNode));//哨兵位头节点
	if (guard == NULL) {
		perror("malloc fail\n");
		return -1;
	}
	guard->prev = guard;
	guard->next = guard;
	return guard;
}
 
//动态申请节点函数
DLNode* BuyDLTNode( DLTDataType x) {
	DLNode* node = (DLNode*)malloc(sizeof(DLNode));
	if (node == NULL) {
		perror("malloc fail\n");
		return -1;
	}
	node->data = x;
	node->prev = NULL;
	node->next = NULL;
	return node;
}
 
//链表尾插
void DListPushBack(DLNode* phead, DLTDataType x) {
	assert(phead);
	DLNode* newnode = BuyDLTNode(x);//新节点
	DLNode* tail=phead->prev;//找到尾节点指针处在哨兵位头节点的prev
	//改变顺序
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}
 
//打印
void DListPrint(DLNode* phead) {
	assert(phead);
	DLNode* cur = phead->next;
	printf("guard<=>");
	while (cur != phead) {	//遍历
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
 
//头插
void DListPushFront(DLNode* phead,DLTDataType x) {
	assert(phead);
	//找到头节点
	DLNode* first = phead->next;
	DLNode* newnode = BuyDLTNode(x);
	//改变顺序
	newnode->next = first;
	newnode->prev = phead;
	phead->next = newnode;
	first->prev = newnode;
}
 
//暴力检查
bool DListEmpty(DLNode* phead) {
	assert(phead);
	return phead->next == phead;
}
 
 
//尾删
void DListPopBack(DLNode* phead) {
	assert(phead);
	//暴力检查
	assert(!DListEmpty(phead));
	DLNode* tail = phead->prev;
	DLNode* last = tail->prev;
	//改变顺序
	last->next = phead;
	phead->prev = last;
	//释放尾节点
	free(tail);
	tail = NULL;
 }
 
//头删
void DListPopFront(DLNode* phead) {
	assert(phead);
	//暴力检查
	assert(!DListEmpty(phead));
	DLNode* first = phead->next;
	DLNode* second = first->next;
	phead->next = second;
	second->prev = phead;
	free(first);
	first = NULL;
}
 
//链表查找
DLNode* DListFind(DLNode* phead, DLTDataType x) {
	assert(phead);
	DLNode* cur = phead->next;
	//遍历查找
	while (cur != phead){
		if (cur->data == x) {
			return cur;//找到了，返回
		}
		cur = cur->next;//继续往后找
	}
	return NULL;//找不到，返回空
}
 
//链表在指定位置pos前插入函数
void DListInsert(DLNode* pos, DLTDataType x) {
	//指定的位置不可以为空
	assert(pos);
	DLNode* last = pos->prev;
	DLNode* newnode = BuyDLTNode(x);
	last->next = newnode;
	newnode->prev = last;
	newnode->next = pos;
	pos->prev = newnode;
}
 
//链表在指定位置pos处删除节点
void DListErase(DLNode* pos) {
	assert(pos);
	DLNode* later = pos->next;
	DLNode* last = pos->prev;
	last->next = later;
	later->prev = last;
	free(pos);
	pos = NULL;
}
 
//求链表的长度函数
size_t DListSize(DLNode* phead) {
	assert(phead);
	size_t n = 0;
	DLNode* cur = phead->next;
	while (cur != phead) {
		n++;
		cur = cur->next;
	}
	return n;
}
 
//释放空间
void DListDestory(DLNode* phead) {
	assert(phead);
	DLNode* cur = phead->next;
	//以遍历节点的方式，一个一个的释放
	while (cur != phead) {
		DLNode* later = cur->next;
		free(cur);
		cur = NULL;
	}
	//释放完后，再把哨兵位头节点也释放掉
	free(phead);
	phead = NULL;
}

DList.h头文件代码：


#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
 
typedef int DLTDataType;//重命名int结构用于双向链表，使用双向链表就用这种新结构，使用普通变量还是使用
						//int类型，重定义只是做一个区分而已。
 
typedef struct DListNode {	
	DLTDataType data;			//数据域
	struct DListNode* prev;		//前指针
	struct DListNode* next;		//后指针
}DLNode;//重定义结构体类型名称
 
//链表初始化
DLNode* DListInit();
 
//链表尾插
void DListPushBack(DLNode* phead, DLTDataType x);
 
//打印
void DListPrint(DLNode* phead);
 
//头插
void DListPushFront(DLNode* phead, DLTDataType x);
 
//尾删
void DListPopBack(DLNode* phead);
 
//头删
void DListPopFront(DLNode* phead);
 
//链表查找
DLNode* DListFind(DLNode* phead, DLTDataType x);
 
//链表在指定位置pos前插入函数
void DListInsert(DLNode* pos, DLTDataType x);
 
//链表在指定位置pos处删除节点
void DListErase(DLNode* pos);
 
//求链表的长度函数
size_t DListSize(DLNode* phead);
 
//释放空间
void DListDestory(DLNode* phead);

以上就是对双向链表的讲解和功能实现了。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/655435