数据结构与算法—双向链表

目录

一、链表的分类

二、双向链表原理

三、实现带头双向链表 

1、声明链表结构体 

2、初始化链表

3、创建新节点

4、打印链表

5、头插&尾插

头插 

尾插

6、头删&尾删

头删

尾删

7、 查找节点

8、 指定节点前插入

9、 删除指定节点

10、销毁链表

完整版

Lisy.h 声明

List.c函数

text.c测试代码

---

一、链表的分类

1. 无头单向非循环链表 ：结构简单，一般不会单独用来存数据。实际中更多是作为 其他数据结构的子结构 ，如 哈希桶、图的邻接表 等等。另外这种结构在 笔试面试 中出现很多。

2. 带头双向循环链表 ：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多 优势 ，实现反而 简单了 ，后面我们代码实现了就知道了。

二、双向链表原理

 我们来对比单向链表的结构体，看一下与双向链表的结构体有什么区别：（左单向，右双向）

1. 我们可以看出双向链表比单向链表多了一个结构体指针prev，它的作用是存储前一个结点的地址。
2. 双向链表的每个节点既可以找到前一个节点，也可以找到后一个节点，
3. 此外头节点和尾节点比较特殊，头节点的prev指向尾节点，尾节点的next指向头节点。
4. 如果链表只有头节点（也叫哨兵位），那么它的prev和next都指向自己。 

三、实现带头双向链表 

1、声明链表结构体 

typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;

• 首先构建链表结构体，将链表结点的data数据类型设置别名LTDataType，方便后续修改。
• 定义结构体名称的别名为LTNode。 
• 指针next指向该节点的下一个节点，
• 指针prev指向该节点的前一个节点。
• LTDataType类型的data用于存值。

2、初始化链表

LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(-1);
	phead->prev = phead;
	phead->next = phead;
	return phead;
}

• 函数的目的是创建一个空的双向链表并返回指向链表头部的指针。
• 通过BuyLTNode( )函数为头节点开辟空间，头节点的data值为-1。（后续讲解）
• 初始化时，prev和next均指向头节点。
• 返回值为指针phead。

创建结构体指针，将初始化函数的返回值赋值给结构体指针，即为初始化完成，代码如下：

LTNode* plist = LTInit();

  这里也可以用二级指针接收链表地址初始化链表。

void LTInit(LTNode** phead)
{
	assert(phead);
	* phead = BuyLTNode(-1);
	(*phead)->prev = *phead;
	(*phead)->next = *phead;
	(*phead)->data = 0;
}

使用该函数初始化时，使用方法也有变化：

LTNode* plist;
LTInit(&plist);

3、创建新节点

LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL) {
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->prev = NULL;
	newnode->next = NULL;
	return newnode;
}

•  使用malloc为新节点newnode开辟结构体LTNode大小的空间。
• 开辟失败perror打印错误信息，函数提前结束。
• 为新节点的data赋值为参数x的值，prev、next置空。
• 返回新节点指针。

4、打印链表

void LTPrint(LTNode* phead)
{
	assert(phead);
	printf("guard<==>");
	LTNode* cur = phead->next;
	while (cur != phead) {
		if(cur!=phead->prev)
			printf("%d<==>", cur->data);
		else
			printf("%d\n", cur->data);
		cur = cur->next;
	}
}

• assert检查链表是否为空，为空则报错。
• 打印字符串 "guard<==>"，用于表示链表的头节点。
• 指针cur指向头节点下一个节点，也就是第一个节点。
• while循环的结束条件为cur指向头节点，双向链表尾部不为空，则循环遍历结束条件为尾结点的next指向头节点时。
• 当cur不指向最后一个节点，打印节点之间的连接符号<==>。

5、头插&尾插

《头插&尾插 和 头删&尾删》我们都可以通过后续的指定位置前插入函数和删除函数实现， 这里进行讲解为了更好得熟悉理解双向链表。

头插 

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyLTNode(x);
	LTNode* first = phead->next;
//下面两块代码的顺序可以颠倒，因为使用指针first储存了原来链表第一个元素的地址
	newnode->next = first;
	first->prev = newnode;
 
	phead->next = newnode;
	newnode->prev = phead;
}

• assert检查链表是否为空，为空则报错。
• 为新节点newnode开辟空间。
• 指针first指向链表原第一个节点。
• 将新节点的next指向原第一个节点，原第一个节点的prev指向新节点。
• 头节点的next指向新节点，新节点的prev指向头节点。

 当然下面这种形式也对，只是后两个代码块不能调换顺序，具体原因大家可以画图试一下。

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyLTNode(x);
 
	newnode->next = phead->next;
	phead->next->prev = newnode;
 
	newnode->prev = phead;
	phead->next = newnode;
}

尾插

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyLTNode(x);
	LTNode* tail = phead->prev;
	
	newnode->next = phead;
	phead->prev = newnode;
 
	tail->next = newnode;
	newnode->prev = tail;
}

• assert检查链表是否为空，为空则报错。
• 为新节点newnode开辟空间。
• 指针tail指向尾节点，直接通过头节点phead的prev即可找到尾节点。
• 新节点的next指向头节点，头节点的prev指向新节点。
• 原尾节点的next指向新节点，新节点的prev指向尾节点。

6、头删&尾删

头删

bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}
 
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
 
	LTNode* first = phead->next;
	LTNode* second = first->next;
 
	second->prev = phead;
	phead->next = second;
	free(first);
}

• 借助LTEmpty函数判断链表是否只有头节点，只有头节点则不进行删除。
• 第一个assert检查链表是否为空，为空则报错。
• 第二个assert通过LTEmpty函数返回值判断是否可以进行删除。
• 定义两个指针first和second分别指向第一个节点和第二个节点。
• 将第二个节点的prev指向头节点。
• 头节点的next指向第二个节点。
• 释放第一个节点的空间。

尾删

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
 
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
 
	free(tail);
	tailPrev->next = phead;
	phead->prev = tailPrev;
 
}

• 第一个assert检查链表是否为空，为空则报错。
• 第二个assert通过LTEmpty函数返回值判断是否可以进行删除。
• 定义两个指针tail和tailPrev，分别指向尾节点和尾节点的前一个节点。
• 释放尾节点的空间。
• tailPrev的next指向头节点。
• 头节点的prev指向tailPrev（新的尾节点）。

7、 查找节点

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead) {
		if (cur->data == x)
			return cur;
 
		cur = cur->next;
	}
	return NULL;
}

• assert检查链表是否为空，为空则报错。
• 指针cur指向第一个节点。
• 循环遍历链表，节点的data值为x时，返回该节点的地址。
• 找不到则返回NULL。

8、指定节点前插入

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
 
	LTNode* prev = pos->prev;
	LTNode* newnode = BuyLTNode(x);
 
	prev->next = newnode;
	newnode->prev = prev;
 
	newnode->next = pos;
	pos->prev = newnode;
}

• assert检查节点是否为空，为空则报错。
• 指针prev指向pos节点的前一个节点。
• 为新节点newnode开辟空间，节点的data值为x。
• 将prev的next指向新节点，新节点的prev指向prev。
• 新节点的next指向pos，pos的prev指向新节点。

9、删除指定节点

void LTErase(LTNode* pos)//可以判断phead是否等于哨兵位
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
	
	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
}

• assert检查节点是否为空，为空则报错。
• 定义两个指针posPrev和posNext分别指向 pos的前一个节点和 pos后一个节点。
• 前一个节点posPrev的next指向posNext。
• 后一个节点posNext的prev指向posPrev
• 释放pos节点的空间。

10、销毁链表

void LTDestroy(LTNode** phead)
{
	assert(phead);
	assert(*phead);
	LTNode* cur = (*phead)->next;
	while (cur != *phead) {
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(*phead);
	*phead = NULL;
}

• assert检查链表是否为空，为空则报错。
• 检查链表头指针 *phead 是否为非空，为空则报错。
• 指针cur指向第一个节点，循环内通过cur遍历每个节点。
• next指针记录cur下一个节点，将cur的空间释放，cur更新为next，指向下一个节点。

• 在循环结束后，链表中的所有节点都已经被销毁，最后一步是释放链表头指针 *phead 所占用的内存。

• *phead = NULL 最后，将链表头指针设置为 NULL，以确保不再引用链表，避免悬挂指针或野指针的问题。

完整版

完整版代码我保留了注释，方便读者学习，以下代码的功能经测试没有问题，放心使用。 

Lisy.h 声明

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
 
typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;
 
//初始化链表
LTNode* LTInit();
//void LTInit(LTNode** phead);
 
//打印链表
void LTPrint(LTNode* phead);
 
//头插&尾插
void LTPushFront(LTNode* phead, LTDataType x);
void LTPushBack(LTNode* phead, LTDataType x);
 
//头删&尾删
void LTPopFront(LTNode* phead);
void LTPopBack(LTNode* phead);
 
//查找值为x的节点，返回节点地址
LTNode* LTFind(LTNode* phead, LTDataType x);
 
//在指定节点前插入
void LTInsert(LTNode* pos, LTDataType x); 
 
//删除指定节点
void LTErase(LTNode* pos);
 
//销毁链表
void LTDestroy(LTNode** phead);

List.c函数

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
 
//创建新节点
LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL) {
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->prev = NULL;
	newnode->next = NULL;
	return newnode;
}
 
//初始化链表
LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(-1);
	phead->prev = phead;
	phead->next = phead;
	return phead;
}
//void LTInit(LTNode** phead)
//{
//	assert(phead);
//	* phead = BuyLTNode(-1);
//	(*phead)->prev = *phead;
//	(*phead)->next = *phead;
//	(*phead)->data = 0;
//}
 
//打印链表
void LTPrint(LTNode* phead)
{
	assert(phead);
	printf("guard<==>");
	LTNode* cur = phead->next;
	while (cur != phead) {
		if(cur!=phead->prev)
			printf("%d<==>", cur->data);
		else
			printf("%d\n", cur->data);
		cur = cur->next;
	}
}
 
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	LTInsert(phead->next, x);
}
 
//void LTPushFront(LTNode* phead, LTDataType x)
//{
//	assert(phead);
//	LTNode* newnode = BuyLTNode(x);
//	LTNode* first = phead->next;
//	//下面两块代码的顺序可以颠倒，因为使用指针first储存了原来链表第一个元素的地址
//	newnode->next = first;
//	first->prev = newnode;
//
//	phead->next = newnode;
//	newnode->prev = phead;
//}
 
//void LTPushFront(LTNode* phead, LTDataType x)
//{
//	assert(phead);
//	LTNode* newnode = BuyLTNode(x);
//
//	newnode->next = phead->next;
//	phead->next->prev = newnode;
//
//	newnode->prev = phead;
//	phead->next = newnode;
//}
 
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
 
	LTInsert(phead, x);
}
//void LTPushBack(LTNode* phead, LTDataType x)
//{
//	assert(phead);
//	LTNode* newnode = BuyLTNode(x);
//	LTNode* tail = phead->prev;
//	
//	newnode->next = phead;
//	phead->prev = newnode;
//
//	tail->next = newnode;
//	newnode->prev = tail;
//}
 
//监测链表是否为空
bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}
 
//头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
 
	LTErase(phead->next);
}
 
//void LTPopFront(LTNode* phead)
//{
//	assert(phead);
//	assert(!LTEmpty(phead));
//
//	LTNode* first = phead->next;
//	LTNode* second = first->next;
//
//	second->prev = phead;
//	phead->next = second;
//	free(first);
//}
 
 
//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
 
	LTErase(phead->prev);
}
 
//void LTPopBack(LTNode* phead)
//{
//	assert(phead);
//	assert(!LTEmpty(phead));
//	//LTErase(phead->prev);
//
//	LTNode* tail = phead->prev;
//	LTNode* tailPrev = tail->prev;
//
//	free(tail);
//	tailPrev->next = phead;
//	phead->prev = tailPrev;
//
//}
 
 
 
 
//查找值为x的节点，返回节点地址
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead) {
		if (cur->data == x)
			return cur;
 
		cur = cur->next;
	}
	return NULL;
}
 
//在指定节点前插入，与LTFind搭配使用
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
 
	LTNode* prev = pos->prev;
	LTNode* newnode = BuyLTNode(x);
 
	prev->next = newnode;
	newnode->prev = prev;
 
	newnode->next = pos;
	pos->prev = newnode;
}
 
// 删除指定节点
void LTErase(LTNode* pos)//可以判断phead是否等于哨兵位
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
	
	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
}
 
//销毁链表
void LTDestroy(LTNode** phead)
{
	assert(phead);
	assert(*phead);
	LTNode* cur = (*phead)->next;
	while (cur != *phead) {
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(*phead);
	*phead = NULL;
}

text.c测试代码

#include "List.h"
 
void test1() {
	/*LTNode* plist;
	LTInit(&plist);*/
 
	LTNode* plist = LTInit();
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
	LTPushBack(plist, 888);
	LTPushBack(plist, 888);
	LTPopFront(plist);
	LTPopBack(plist);
	LTNode* pos = LTFind(plist, 888);
	LTInsert(pos, 999);
 
	LTErase(pos);
 
	LTPrint(plist);
	LTDestroy(&plist);
}
 
int main()
{
	test1();
	return 0;
}