数据结构——双向链表

目录

一、链表的分类

 (1)单向或双向​编辑

（2）带头或不带头​编辑

（3）循环或不循环​编辑

 （4）补充

二、实现双向链表

（1）List.h

(2)List.c

(3)注意

三、顺序表和链表的比较

 四、写在最后

一、链表的分类

链表的结构多种多样，包括：带头或不带头、单向或双向、循环或不循环，组合起来有8种情况（2x2x2）:

 (1)单向或双向

（2）带头或不带头

（3）循环或不循环

 （4）补充

①虽然链表有多种结构，但是最常用的是单链表（不带头单向不循环链表）、双向链表（带头双向循环链表）；

②带头指的是头结点，这里的头结点和我们之前说的是两个概念，实际上在前面的称呼并不严谨。头结点实际为“哨兵位”，哨兵位不存储有效数据，作用为“放哨的”；

③双向链表的结构

二、实现双向链表

（1）List.h

#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h>  //定义双向链表的结点的结构 typedef int LTDatatype; typedef struct ListNode { 	LTDatatype data; 	struct ListNode* next; 	struct ListNode* prev; }LTNode;  //初始化 void LTInit1(LTNode** pphead); LTNode* LTInit2();  //打印 void LTPrint(LTNode* phead);  //插入 void LTPushFront(LTNode* phead, LTDatatype x); void LTPushBack(LTNode* phead, LTDatatype x);  //判断链表是否为空 bool LTEmpty(LTNode* phead);  //删除 void LTPopFront(LTNode* phead); void LTPopBack(LTNode* phead);  //查找数据位置 LTNode* LTFind(LTNode* phead, LTDatatype x);  //在指定位置之后插入数据 void LTInit(LTNode* pos, LTDatatype x);   //删除指定位置的数据 void LTErase(LTNode* pos);  //销毁 void LTDestroy(LTNode** pphead); void LTDestroy2(LTNode* phead);//需要手动将plist置为空

(2)List.c

#include "List.h"  LTNode* LTBuyNode(LTDatatype x) { 	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); 	//如果申请不成功 	if (newnode == NULL) 	{ 		perror("malloc fail!\n"); 		exit(1);//退出 	} 	newnode->data = x; 	newnode->next = newnode->prev = newnode; 	//由于双向链表是循环的，所以指向自身而非NULL 	return newnode;//注意返回新结点 }  //初始化 void LTInit1(LTNode** pphead) { 	//创建哨兵位 	*pphead = LTBuyNode(-1); }  LTNode* LTInit2() { 	LTNode* phead = LTBuyNode(-1); 	return phead; }  //打印 void LTPrint(LTNode* phead) { 	LTNode* pcur = phead->next; 	while (pcur != phead) 	{ 		printf("%d->", pcur->data); 		pcur = pcur->next; 	} 	printf("\n"); }  //插入 void LTPushFront(LTNode* phead, LTDatatype x) { 	assert(phead); 	LTNode* newnode = LTBuyNode(x); 	newnode->next = phead->next; 	newnode->prev = phead; 	phead->next->prev = newnode; 	phead->next = newnode; }   void LTPushBack(LTNode* phead, LTDatatype x) { 	assert(phead); 	LTNode* newnode = LTBuyNode(x); 	newnode->next = phead; 	newnode->prev = phead->prev; 	phead->prev->next = newnode; 	phead->prev = newnode; }  //判断链表是否为空 bool LTEmpty(LTNode* phead) { 	assert(phead); 	return phead->next == phead; }   //删除 void LTPopFront(LTNode* phead) { 	assert(phead); 	assert(!LTEmpty(phead));//判断链表不为空 	LTNode* del = phead->next; 	phead->next = del->next; 	del->next->prev = phead; 	free(del); 	del = NULL; } void LTPopBack(LTNode* phead) { 	assert(phead); 	assert(!LTEmpty(phead));//判断链表不为空 	LTNode* del = phead->prev; 	del->prev->next = phead; 	phead->prev = del->prev; 	free(del); 	del = NULL; } //查找数据位置 LTNode* LTFind(LTNode* phead, LTDatatype x) { 	LTNode* pcur = phead->next; 	while (pcur != phead) 	{ 		if (pcur->data == x) 		{ 			return pcur; 		} 		pcur = pcur->next; 	} 	return NULL; }   //在指定位置之后插入数据 void LTInit(LTNode* pos, LTDatatype x) { 	assert(pos); 	LTNode* newnode = LTBuyNode(x); 	newnode->next = pos->next; 	newnode->prev = pos; 	pos->next->prev = newnode; 	pos->next = newnode; }  //删除指定位置的数据 void LTErase(LTNode* pos) { 	assert(pos); 	pos->prev->next = pos->next; 	pos->next->prev = pos->prev; 	free(pos); 	pos = NULL; }  //销毁 void LTDestroy(LTNode** pphead) { 	assert(pphead && *pphead); 	LTNode* pcur = (*pphead)->next; 	while (pcur != *pphead) 	{ 		LTNode* Next = pcur->next; 		free(pcur); 		pcur = Next; 	} 	free(*pphead); 	*pphead = NULL; 	pcur = NULL;//记得将pcur置为空，否则如果后续使用，它为野指针 }   void LTDestroy2(LTNode* phead) { 	assert(phead); 	LTNode* pcur = phead->next; 	while (pcur != phead) 	{ 		LTNode* Next = pcur->next; 		free(pcur); 		pcur = Next; 	} 	free(phead); 	phead = NULL; 	pcur = NULL; }

(3)注意

1.双向链表是循环的，在创建新结点时，新结点的next、prev指针要指向自身。因为如果链表为空，此时链表只有头节点，要想构成循环，其next、prev指针必须指向自身；

2.除初始化和销毁的函数传入的是二级指针外，其他函数的形参均为一级指针，为了保持接口的一致性，给它们传入一级指针作为优化。但美中不足的是，对于链表的销毁，还需在调用函数后将实参置为空；

3.插入时需要创建新结点，删除时需要判断链表是否为空。

三、顺序表和链表的比较

 四、写在最后

我们的链表终于完结啦，撒花~~

敬请期待栈和队列！