【数据结构与算法】数据结构初阶：详解顺序表和链表（五）—

🔥个人主页：艾莉丝努力练剑

❄专栏传送门：《C语言》、《数据结构与算法》、C语言刷题12天IO强训、LeetCode代码强化刷题

🍉学习方向：C/C++方向

⭐️人生格言：为天地立心，为生民立命，为往圣继绝学，为万世开太平

前言：本篇文章，我们继续来看顺序表和链表相关的知识点，在初阶的数据结构与算法阶段，我们把知识点分成三部分，复杂度作为第一部分，顺序表和链表、栈和队列、二叉树为第二部分，排序为第二部分，我们之前已经介绍完了第一部分：算法复杂度，本文我们继续学习第二部分中的顺序表和链表部分内容啦。

再次提醒：为什么我们要学那么多的数据结构？这是因为没有一种数据结构能够去应对所有场景。我们在不同的场景需要选择不同的数据结构，所以数据结构没有谁好谁坏之分，而评估数据结构的好坏要针对场景，如果在一种场景下我们需要频繁地对头部进行插入删除操作，那么这个时候我们用链表；但是如果对尾部进行插入删除操作比较频繁，那我们用顺序表比较好。

因此，不同的场景我们选择不同的数据结构。

正文

四、双向链表

（一）链表的分类

链表并不是一个具体的结构，链表的结构非常多样，下面情况组合起来就有8(2*2*2)种链表结构：

1、带头或者不带头

带头链表中的头节点，不存储任何有效的数据，只用来占位子，“哨兵位” 。

在前面介绍单链表的时候，有的地方博主也会表述成“头节点”，这个称呼是为了方便uu们理解，实际上把单链表中第一个节点称为“头节点”是错误的表述。

2、单向或者双向

3、循环或者不循环

虽然有这么多的链表结构，但是我们实际中最常用的还是两种结构：单链表和双向链表。

（二）带头双向循环链表节点的概念与结构

1、概念

注意：这里的“带头”跟前面我们说的“头结点”是两个概念，实际前面的在单链表阶段称呼并不严谨，但是为了uu们更好的理解就直接称为单链表的头结点。

2、结构

带头链表里的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是在这里“放哨的”。

双向链表中由一个一个的节点组成，这里的节点有三个组成部分——

struct ListNode
{
	int data;
	struct ListNode* next;//指向后一个节点的指针
	struct ListNode* prev;//指向前一个节点的指针
}

3、双向链表为空

双向链表为空——指向自己

（三）实现双向链表

1、初始化

（1）List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>

//定义双向链表结构
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;//指向后一个节点的指针
	struct ListNode* prev;//指向前一个节点的指针
}LTNode;

//要改变头节点plist——要用二级指针
//初始化
void LTInit(LTNode** pphead);

（2）List.c：

#define  _CRT_SECURE_NO_WARNINGS  1

#include"List.h"

//初始化
void LTInit(LTNode** pphead)
{
	*pphead = (LTNode*)malloc(sizeof(LTNode));
	if (*pphead == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	(*pphead)->data = -1;
	(*pphead)->next = (*pphead)->prev = *pphead;
}

（3）test.c：

#define  _CRT_SECURE_NO_WARNINGS  1

#include"List.h"

void test01()
{
	LTNode* plist = NULL;
	LTInit(&plist);
}

int main()
{
	test01();
	return 0;
}

调试一下，打开监视，进入函数（F11）——

像这样，初始化就完成了——

补充：博主并不建议把LTNode* plist改成LTNode plist（不用**），很多教材是这样写的，看起来很困难，还存在一个误导的作用。本身大家对指针的理解就很困难了，如果我们这样一会儿加一个一级指针一会儿定义成LTNode，那大家后续去使用是很混乱的，所以不建议这样使用。

而且关键是后面我们基本用到的都是一级指针，只需要一个*就好了，所以建议大家如果教材中有上面这种写法，不要用，我们就搞一个二级指针就好了。

2、打印

List.c：

//打印
void LTPrint(LTNode* phead)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d -> ", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

test.c：

	LTPrint(plist);

3、遍历

4、判断链表是否为空

List.c：

//判断链表是否为空
bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}

5、增删查改功能的实现

增

（1）尾插

哨兵位在双向链表始终不会发生改变——

plist本来指向0x100，有了值之后plist指向0x800。

List.c：

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	//phead phead->prev newnode
	newnode->prev = phead->prev;
	newnode->next = phead;

	phead->prev->next = newnode;
	phead->prev = newnode;
}

test.c：

void test01()
{
	LTNode* plist = NULL;
	LTInit(&plist);

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
}

int main()
{
	test01();
	return 0;
}

尾插的时间复杂度：O(1) 。

打开监视，观察一下尾插——

（2）头插

List.c：

//头插
void LTPushFront(LTNode* phead, LTDataType x) 
{
	assert(phead);

	LTNode* newnode = LTBuyNode(x);
	//phead newnode phead->next
	newnode->next = phead->next;
	newnode->prev = phead;

	phead->next->prev = newnode;
	phead->next;
}

test.c：

void test01()
{
	LTNode* plist = NULL;
	LTInit(&plist);

	//LTPushBack(plist, 1);
	//LTPushBack(plist, 2);
	//LTPushBack(plist, 3);
	//LTPushBack(plist, 4);
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
}

int main()
{
	test01();
	return 0;
}

头插的时间复杂度：O(1) 。

打开监视看一下——

（3）在指定位置之前插入数据

pos不可能指向phead，因为phead不存储任何有效数据（LTFind找不到）。

List.c：

//在pos位置之前插入节点
void LTInsertBefore(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* newnode = LTBuyNode(x);
	//pos->prev newnode pos
	newnode->prev = pos->prev;
	newnode->next = pos;

	pos->prev->next = newnode;
	pos->prev = newnode;
}

test.c：

void test01()
{
	LTNode* plist = NULL;
	LTInit(&plist);

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);

	LTNode* pos = LTFind(plist,1);

	LTInsertBefore(pos, 100);
	LTPrint(plist);
}

int main()
{
	test01();
	return 0;
}

在指定位置之前插入数据时间复杂度：O(N)。

测试一下——

（4）在指定位置之后插入数据

List.c：

//在pos位置之后插入节点
void LTInsert(LTNode* pos, LTDataType x)//任意位置的插入
{
	assert(pos);

	LTNode* newnode = LTBuyNode(x);
	//pos newnode pos->next
	newnode->prev = pos;
	newnode->next = pos->next;

	pos->next->prev = newnode;
	pos->next = newnode;
}

test.c：

void test01()
{
	LTNode* plist = NULL;
	LTInit(&plist);

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);

	LTNode* pos = LTFind(plist,2);

	LTInsert(pos, 100);
	LTPrint(plist);
}

int main()
{
	test01();
	return 0;
}

在指定位置之后插入数据时间复杂度：O(1)。

这里如果给个这个位置——

LTNode* pos = LTFind(plist,4);

就相当于尾插，头插行不行呢？头插是在头节点之后插入，不行，这里只能给1。

删

（1）尾删

List.c：

//尾删
void LTPopBack(LTNode* phead)
{
	assert(!LTEmpty(phead));

	LTNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;

	free(del);
	del = NULL;
	//其实置不置为空都没关系，这里执行到这里程序已经结束了，不会再用到del了
	//这样写无非是养成一个好习惯
}

这里其实置不置为空都没关系，这里执行到这里程序已经结束了，不会再用到del了，我们这样写无非是养成一个好习惯而已。

test.c：

void test01()
{
	LTNode* plist = NULL;
	LTInit(&plist);

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
	//LTPushFront(plist, 1);
	//LTPushFront(plist, 2);
	//LTPushFront(plist, 3);
	//LTPushFront(plist, 4);

	LTPopBack(plist);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);
}

int main()
{
	test01();
	return 0;
}

尾删的时间复杂度：O(1) 。

这里再删一次就会断言报错了（我们的期望）。

（2）头删

List.c：

//头删
void LTPopFront(LTNode* phead)
{
	assert(!LTEmpty(phead));

	LTNode* del = phead->next;
	del->next->prev = phead;
	phead->next = del->next;

	free(del);
	del = NULL;
}

test.c：

void test01()
{
	LTNode* plist = NULL;
	LTInit(&plist);

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);

	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
}

int main()
{
	test01();
	return 0;
}

头删的时间复杂度：O(1) 。

再删一次就会断言报错。

（3）删除pos位置节点

这里没有传phead。

List.c：

//删除pos位置的节点
void LTErase(LTNode* pos)
{
	assert(pos);
	//pos->prev pos pos->next
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;

	free(pos);
	pos = NULL;
}

test.c：

void test01()
{
	LTNode* plist = NULL;
	LTInit(&plist);

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);

	LTNode* pos = LTFind(plist,2);

	LTErase(pos);
	LTPrint(plist);
}

int main()
{
	test01();
	return 0;
}

查

（1）查找

如果找到了，把这个节点的指针返回，既然是查找，无非就是遍历；

如果没找到，返回一个NULL就好了。

List.c：

//在双向链表里面查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//未找到
	return NULL;
}

test.c：

void test01()
{
	LTNode* plist = NULL;
	LTInit(&plist);

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);

	LTNode* pos = LTFind(plist,4);
	if (pos)
	{
		printf("找到了！\n");
	}
	else
	{
		printf("未找到!\n");
	}
}

int main()
{
	test01();
	return 0;
}

测试一下——

我们来测试一下查找一个链表中没有的值——

改

（1）修改

修改就很简单了，我们不做过多介绍。

List.c：

//修改
void LTChange(LTNode* pos, LTDataType x)
{
	assert(pos);
	pos->data = x;
}

test.c：

#include"List.h"

void test01()
{
	LTNode* plist = NULL;
	LTInit(&plist);

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);

	LTNode* pos = LTFind(plist,2);

	//修改
	LTChange(pos, 100);
	LTPrint(plist);}

int main()
{
	test01();
	return 0;
}

6、销毁链表

哨兵位phead也要销毁，传二级指针**pphead。

List.c：

//销毁
void LTDestory(LTNode** pphead)
{
	LTNode* pcur = (*pphead)->next;
	while(pcur != *pphead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	//销毁头节点
	free(*pphead);
	*pphead = NULL;
}

test.c：

void test01()
{
	LTNode* plist = NULL;
	LTInit(&plist);

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);

	LTNode* pos = LTFind(plist,2);

	LTErase(pos);
	LTPrint(plist);

	//销毁
	LTDestory(&plist);
}

int main()
{
	test01();
	return 0;
}

打开监视观察一下——

7、完整代码

（1）List.h

#pragma once
#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;

//要改变头节点plist——要用二级指针
//初始化
void LTInit(LTNode** pphead);
//销毁
void LTDestory(LTNode** pphead);

//在双向链表中，增删查改都不会改变哨兵位节点
//所以我们要用一级指针，因为我们不改变phead——plist指针
//尾插
void LTPushBack(LTNode* phead, LTDataType x);

//头插
void LTPushFront(LTNode* phead, LTDataType x);

//尾删
void LTPopBack(LTNode* phead);

//判断链表是否为空
bool LTEmpty(LTNode* phead);

//打印
void LTPrint(LTNode* phead);

//头删
void LTPopFront(LTNode* phead);

//在双向链表里面查找
LTNode* LTFind(LTNode* phead, LTDataType x);

//在pos位置之前插入节点
void LTInsertBefore(LTNode* pos, LTDataType x);

//在pos位置之后插入节点
void LTInsert(LTNode* pos, LTDataType x);//任意位置的插入

//删除pos位置的节点
void LTErase(LTNode* pos);

//修改
void LTChange(LTNode* pos, LTDataType x);

（2）List.c：

#define  _CRT_SECURE_NO_WARNINGS  1

#include"List.h"

LTNode* LTBuyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = newnode->prev = newnode;

	return newnode;
}

//第一版初始化
void LTInit(LTNode** pphead)
{
	//*pphead = (LTNode*)malloc(sizeof(LTNode));
	//if (*pphead == NULL)
	//{
	//	perror("malloc fail!");
	//	exit(1);
	//}
	//(*pphead)->data = -1;
	//(*pphead)->next = (*pphead)->prev = *pphead;
	*pphead = LTBuyNode(-1);//申请一个哨兵位节点
}

//销毁
void LTDestory(LTNode** pphead)
{
	LTNode* pcur = (*pphead)->next;
	while(pcur != *pphead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	//销毁头节点
	free(*pphead);
	*pphead = NULL;
}

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	//phead phead->prev newnode
	newnode->prev = phead->prev;
	newnode->next = phead;

	phead->prev->next = newnode;
	phead->prev = newnode;
}

//头插
void LTPushFront(LTNode* phead, LTDataType x) 
{
	assert(phead);

	LTNode* newnode = LTBuyNode(x);
	//phead newnode phead->next
	newnode->next = phead->next;
	newnode->prev = phead;

	phead->next->prev = newnode;
	phead->next;
}

//打印
void LTPrint(LTNode* phead)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d -> ", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

//判断链表是否为空
bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}

//尾删
void LTPopBack(LTNode* phead)
{
	assert(!LTEmpty(phead));

	LTNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;

	free(del);
	del = NULL;
	//其实置不置为空都没关系，这里执行到这里程序已经结束了，不会再用到del了
	//这样写无非是养成一个好习惯
}

//头删
void LTPopFront(LTNode* phead)
{
	assert(!LTEmpty(phead));

	LTNode* del = phead->next;
	del->next->prev = phead;
	phead->next = del->next;

	free(del);
	del = NULL;
}

//在双向链表里面查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//未找到
	return NULL;
}

//在pos位置之前插入节点
void LTInsertBefore(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* newnode = LTBuyNode(x);
	//pos->prev newnode pos
	newnode->prev = pos->prev;
	newnode->next = pos;

	pos->prev->next = newnode;
	pos->prev = newnode;
}

//在pos位置之后插入节点
void LTInsert(LTNode* pos, LTDataType x)//任意位置的插入
{
	assert(pos);

	LTNode* newnode = LTBuyNode(x);
	//pos newnode pos->next
	newnode->prev = pos;
	newnode->next = pos->next;

	pos->next->prev = newnode;
	pos->next = newnode;
}

//删除pos位置的节点
void LTErase(LTNode* pos)
{
	assert(pos);
	//pos->prev pos pos->next
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;

	free(pos);
	pos = NULL;
}

//修改
void LTChange(LTNode* pos, LTDataType x)
{
	assert(pos);
	pos->data = x;
}

（3）test.c：

#define  _CRT_SECURE_NO_WARNINGS  1

#include"List.h"

void test01()
{
	LTNode* plist = NULL;
	LTInit(&plist);

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
	//LTPushFront(plist, 1);
	//LTPushFront(plist, 2);
	//LTPushFront(plist, 3);
	//LTPushFront(plist, 4);
	// 
	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	//
	//LTPopFront(plist);
	//LTPrint(plist);
	//LTPopFront(plist);
	//LTPrint(plist);
	//LTPopFront(plist);
	//LTPrint(plist);
	//LTPopFront(plist);
	//LTPrint(plist);
	//LTPopFront(plist);
	//LTPrint(plist);
	LTNode* pos = LTFind(plist,2);
	//if (pos)
	//{
	//	printf("找到了！\n");
	//}
	//else
	//{
	//	printf("未找到!\n");
	//}
	// 
	//LTInsertBefore(pos, 100);
	//LTPrint(plist);
	//LTInsert(pos, 100);
	//LTPrint(plist);
	//LTErase(pos);
	//LTPrint(plist);
	//修改
	LTChange(pos, 100);
	LTPrint(plist);

	//销毁
	LTDestory(&plist);
}

int main()
{
	test01();
	return 0;
}

8、优化版代码（考虑接口的一致性）

我们的程序是要给使用用户使用的。

考虑到接口的一致性，即一级指针就全部一级指针，二级指针就全部二级指针，一会儿一级指针一会儿又二级指针，会增加使用用户的记忆成本。

（1）初始化优化版

List.c：

//优化版初始化
LTNode* LTInit()
{
	LTNode* phead = LTBuyNode(-1);
	return phead;
}

test.c：

void test01()
{
	//LTNode* plist = NULL;
	//LTInit(&plist);
	LTNode* plist = LTInit();//创建一个指针来接收初始化的返回值

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);

	LTNode* pos = LTFind(plist,2);

	//修改
	LTChange(pos, 100);
	LTPrint(plist);

	//销毁
	LTDestory(&plist);
}

int main()
{
	test01();
	return 0;
}

现在初始化优化完了，满足了接口的一致性。

（2）销毁优化版

List.c：

//优化版销毁
void LTDestroy(LTNode* phead)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	//销毁头结点
	free(phead);
	phead = NULL;
}

空间全部释放完plist会变野指针，最后实参会变成一个随机数，我们要把实参手动置为空。

test.c：

void test01()
{
	//LTNode* plist = NULL;
	//LTInit(&plist);
	LTNode* plist = LTInit();//创建一个指针来接收初始化的返回值

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);

	LTNode* pos = LTFind(plist,2);

	//修改
	LTChange(pos, 100);
	LTPrint(plist);


	//优化版销毁
	LTDestroy(plist);
	plist = NULL;
}

int main()
{
	test01();
	return 0;
}

优化的部分就是原先用了二级指针的初始化和销毁。

9、优化后的完整代码

（1）List.h

#pragma once
#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;

//优化版初始化
LTNode* LTInit();

//优化版销毁——为了保持接口一致性
void LTDestroy(LTNode* phead);

//在双向链表中，增删查改都不会改变哨兵位节点
//所以我们要用一级指针，因为我们不改变phead——plist指针
//尾插
void LTPushBack(LTNode* phead, LTDataType x);

//头插
void LTPushFront(LTNode* phead, LTDataType x);

//尾删
void LTPopBack(LTNode* phead);

//判断链表是否为空
bool LTEmpty(LTNode* phead);

//打印
void LTPrint(LTNode* phead);

//头删
void LTPopFront(LTNode* phead);

//在双向链表里面查找
LTNode* LTFind(LTNode* phead, LTDataType x);

//在pos位置之前插入节点
void LTInsertBefore(LTNode* pos, LTDataType x);

//在pos位置之后插入节点
void LTInsert(LTNode* pos, LTDataType x);//任意位置的插入

//删除pos位置的节点
void LTErase(LTNode* pos);

//修改
void LTChange(LTNode* pos, LTDataType x);

（2）List.c：

#define  _CRT_SECURE_NO_WARNINGS  1

#include"List.h"

LTNode* LTBuyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = newnode->prev = newnode;

	return newnode;
}

//优化版初始化
LTNode* LTInit()
{
	LTNode* phead = LTBuyNode(-1);
	return phead;
}

//优化版销毁
void LTDestroy(LTNode* phead)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	//销毁头结点
	free(phead);
	phead = NULL;
}

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	//phead phead->prev newnode
	newnode->prev = phead->prev;
	newnode->next = phead;

	phead->prev->next = newnode;
	phead->prev = newnode;
}

//头插
void LTPushFront(LTNode* phead, LTDataType x) 
{
	assert(phead);

	LTNode* newnode = LTBuyNode(x);
	//phead newnode phead->next
	newnode->next = phead->next;
	newnode->prev = phead;

	phead->next->prev = newnode;
	phead->next;
}

//打印
void LTPrint(LTNode* phead)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d -> ", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

//判断链表是否为空
bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}

//尾删
void LTPopBack(LTNode* phead)
{
	assert(!LTEmpty(phead));

	LTNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;

	free(del);
	del = NULL;
	//其实置不置为空都没关系，这里执行到这里程序已经结束了，不会再用到del了
	//这样写无非是养成一个好习惯
}

//头删
void LTPopFront(LTNode* phead)
{
	assert(!LTEmpty(phead));

	LTNode* del = phead->next;
	del->next->prev = phead;
	phead->next = del->next;

	free(del);
	del = NULL;
}

//在双向链表里面查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//未找到
	return NULL;
}

//在pos位置之前插入节点
void LTInsertBefore(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* newnode = LTBuyNode(x);
	//pos->prev newnode pos
	newnode->prev = pos->prev;
	newnode->next = pos;

	pos->prev->next = newnode;
	pos->prev = newnode;
}

//在pos位置之后插入节点
void LTInsert(LTNode* pos, LTDataType x)//任意位置的插入
{
	assert(pos);

	LTNode* newnode = LTBuyNode(x);
	//pos newnode pos->next
	newnode->prev = pos;
	newnode->next = pos->next;

	pos->next->prev = newnode;
	pos->next = newnode;
}

//删除pos位置的节点
void LTErase(LTNode* pos)
{
	assert(pos);
	//pos->prev pos pos->next
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;

	free(pos);
	pos = NULL;
}

//修改
void LTChange(LTNode* pos, LTDataType x)
{
	assert(pos);
	pos->data = x;
}

（3）test.c：

#define  _CRT_SECURE_NO_WARNINGS  1

#include"List.h"

void test01()
{
	LTNode* plist = LTInit();//创建一个指针来接收初始化的返回值

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
	//LTPushFront(plist, 1);
	//LTPushFront(plist, 2);
	//LTPushFront(plist, 3);
	//LTPushFront(plist, 4);
	// 
	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	//
	//LTPopFront(plist);
	//LTPrint(plist);
	//LTPopFront(plist);
	//LTPrint(plist);
	//LTPopFront(plist);
	//LTPrint(plist);
	//LTPopFront(plist);
	//LTPrint(plist);
	//LTPopFront(plist);
	//LTPrint(plist);
	LTNode* pos = LTFind(plist,2);
	//if (pos)
	//{
	//	printf("找到了！\n");
	//}
	//else
	//{
	//	printf("未找到!\n");
	//}
	// 
	//LTInsertBefore(pos, 100);
	//LTPrint(plist);
	//LTInsert(pos, 100);
	//LTPrint(plist);
	//LTErase(pos);
	//LTPrint(plist);
	//修改
	LTChange(pos, 100);
	LTPrint(plist);

	//优化版销毁
	LTDestroy(plist);
	plist = NULL;
}

int main()
{
	test01();
	return 0;
}

五、顺序表和链表的对比分析

详见下图——

结尾

那么到这里，我们【初阶数据结构】中的【顺序表与链表】这一part就全部介绍完了，内容不少，大家要及时回顾、消化。

顺序表、链表的数据结构和下面我们将要介绍的栈和队列密不可分，马虎不得。

往期回顾：

【数据结构与算法】数据结构初阶：详解顺序表和链表（四）——单链表（下）

【数据结构与算法】数据结构初阶：详解顺序表和链表（三）——单链表（上）

本期内容需要回顾的C语言知识如下面的截图中所示（指针博主写了6篇，列出来有水字数嫌疑了，就只放指针第六篇的网址，博主在指针（六）把指针部分的前五篇的网址都放在【往期回顾】了，点击【传送门】就可以看了）。

大家如果对前面部分的知识点印象不深，可以去上一篇文章的结尾部分看看，博主把需要回顾的知识点相关的博客的链接都放在上一篇文章了，上一篇文章的链接博主放在下面了：

【数据结构与算法】数据结构初阶：详解顺序表和链表（三）——单链表（上）

结语：本篇文章到这里就结束了，对数据结构的双向链表知识感兴趣的友友们可以在评论区留言，博主创作时可能存在笔误，或者知识点不严谨的地方，大家多担待，如果大家在阅读的时候发现了行文有什么错误欢迎在评论区斧正，再次感谢友友们的关注和支持！

【数据结构与算法】数据结构初阶：详解顺序表和链表（五）——双向链表

目录

正文

四、双向链表

（一）链表的分类

1、带头或者不带头

2、单向或者双向

3、循环或者不循环

（二）带头双向循环链表节点的概念与结构

1、概念

2、结构

3、双向链表为空

（三）实现双向链表

1、初始化

2、打印

3、遍历

4、判断链表是否为空

5、增删查改功能的实现

增

（1）尾插

（2）头插

（3）在指定位置之前插入数据

（4）在指定位置之后插入数据

删

（1）尾删

（2）头删

（3）删除pos位置节点

查

（1）查找

改

（1）修改

6、销毁链表

7、完整代码

8、优化版代码（考虑接口的一致性）

（1）初始化优化版

（2）销毁优化版

9、优化后的完整代码

（1）List.h

（2）List.c：

（3）test.c：

五、顺序表和链表的对比分析

结尾

网站公告

今日签到

热门文章

最新发布