数据结构初阶：详解双链表

🔥个人主页：胡萝卜3.0

🎬作者简介：C++研发方向学习者

📖个人专栏：  《C语言》《数据结构》 《C++干货分享》

⭐️人生格言：不试试怎么知道自己行不行

目录

一、链表的分类

1.1 带头或者不带头

1.2 单向或者双向

1.3 循环或者不循环

二、双向链表

2.1 概念

2.2 结构

三、双向链表的实现

3.1 双向链表的结构

3.2 双向链表的初始化

3.3 打印

3.4 判断链表是否为空

3.5 增删查改功能的实现

3.5.1 尾插

3.5.2 头插

3.5.3 尾删

3.5.4 头删

3.5.5 查找

3.5.6 在指定位置之前插入数据

3.5.6 在指定位置之后插入数据

3.5.7 删除指定位置上的数据

3.5.8 删除指定位置之前的数据

3.5.9 删除指定位置之后的数据

3.5.10 修改指定位置上的数据

3.5.11 销毁链表

四、完整代码

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

5.1 初始化优化

5.2 销毁优化

5.3 优化后完整代码

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

一、链表的分类

链表的结构非常多样，以下情况组合起来就有8种（2 x 2 x 2）链表结构：

1.1 带头或者不带头

带头链表中的头结点，不存储任何有效数据，只是用来占位子，我们称它为“哨兵位”

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

1.2 单向或者双向

1.3 循环或者不循环

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

ok，接下来我们一起来学习双链表的相关知识。

二、双向链表

2.1 概念

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

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

2.2 结构

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

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

当我们没有向链表中插入任何数据之前，这个链表是一个空链表，那双链表的空链表和单链表的空链表是一样的吗？

ok，当然是不一样的，双向链表是带头双向循环链表，如果仅仅是一个空节点，那就不满足这个概念了，那双向链表为空怎么表示呢？

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

三、双向链表的实现

3.1 双向链表的结构

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

//双链表的结构
typedef int LTNDataType;
typedef struct ListNode
{
	LTNDataType data;//存储数据
	struct ListNode* prev;//指针保存上一个节点的地址
	struct ListNode* next;//指针保存的是下一个结点的地址
}ListNode;

3.2 双向链表的初始化

这时候就会有人想问了，在学习单链表时，我们并没有实现初始化的操作，为什么到了双链表，要实现初始化操作呢？

在双向链表中的头结点实际为“哨兵位”，哨兵位结点不存储任何有效元素，只是站在这里“放哨的”，双向链表为空——指向自己，那我们是不是要给这个头结点向操作系统申请空间，并在申请空间时，让prev和next指针指向自己，这样才可以实现双向循环。

代码

（1）List.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//双链表的结构
typedef int LTNDataType;
typedef struct ListNode
{
	LTNDataType data;//存储数据
	struct ListNode* prev;//指针保存上一个节点的地址
	struct ListNode* next;//指针保存的是下一个结点的地址
}ListNode;

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

（2）List.c

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

（3）test.c

#define  _CRT_SECURE_NO_WARNINGS  1
 
#include"List.h"
 
void test01()
{
	ListNode* plist = NULL;
	ListInit(&plist);
}
 
int main()
{
	test01();
	return 0;
}

3.3 打印

要实现打印的操作，那我们就要遍历链表：

代码：

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

pcur为头结点的下一个结点，当pcur!=phead时，继续遍历链表，当pcur==phead时，跳出循环，停止遍历。

3.4 判断链表是否为空

当双链表为空时，仅仅只有一个头结点，那就是头结点中的next指针指向头结点。

代码

//判断链表是否为空
bool ListEmpty(ListNode* phead)
{
	assert(phead);
	//头结点的next指针指向自己，说明链表为空
	return phead->next == phead;
}

3.5 增删查改功能的实现

3.5.1 尾插

在尾插的操作中，哨兵位没有发生改变。

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

代码：
List.c

//创建空间
ListNode* ListBuyNode(LTNDataType num)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = num;
	newnode->prev = newnode->next = newnode;
	return newnode;
}
//尾插
void ListPushBack(ListNode* phead, LTNDataType num)
{
	assert(phead);
	//为新节点创建空间
	ListNode* newnode = ListBuyNode(num);
	//先改变newnode的指向
	newnode->prev = phead->prev;
	newnode->next = phead;
	phead->prev->next = newnode;
	phead->prev = newnode;
}

test.c

void test01()
{
	ListNode* plist = NULL;
	ListInit(&plist);
	//尾插
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPushBack(plist, 5);
	ListPushBack(plist, 6);
	ListPrint(plist);
}
int main()
{
    test01();
    return 0;
}

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

3.5.2 头插

List.c

//创建空间
ListNode* ListBuyNode(LTNDataType num)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = num;
	newnode->prev = newnode->next = newnode;
	return newnode;
}
//头插
//在头结点的后面插入
void ListPushFront(ListNode* phead, LTNDataType num)
{
	assert(phead);
	//为新结点创建空间
	ListNode* newnode = ListBuyNode(num);
	newnode->prev = phead;
	newnode->next = phead->next;
	phead->next->prev = newnode;
	phead->next = newnode;
}

test.c

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
void test01()
{
	ListNode* plist = NULL;
	ListInit(&plist);
	ListNode* plist = ListInit();
	//尾插
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPushBack(plist, 5);
	ListPushBack(plist, 6);
	ListPrint(plist);
	//头插
	ListPushFront(plist, 1);
	ListPushFront(plist, 0);
	ListPrint(plist);
}
int main()
{
	test01();
	return 0;
}

时间复杂度为：O（1）

3.5.3 尾删

List.c

//判断链表是否为空
bool ListEmpty(ListNode* phead)
{
	assert(phead);
	//头结点自己指向自己，说明链表为空
	return phead->next == phead;
}
//尾删
void ListPopBack(ListNode* phead)
{
	//判断双链表是否为空
	assert(!ListEmpty(phead));
	ListNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;
	free(del);
	del = NULL;
}

3.5.4 头删

头删删除的是头结点后面的一个结点，而不是头结点

List.c

//判断链表是否为空
bool ListEmpty(ListNode* phead)
{
	assert(phead);
	//头结点自己指向自己，说明链表为空
	return phead->next == phead;
}

//头删
void ListPopFront(ListNode* phead)
{
    //判断链表是否为空
	assert(!ListEmpty(phead));
	ListNode* del = phead->next;
	del->next->prev = phead;
	phead->next = del->next;
	free(del);
	del = NULL;
}

3.5.5 查找

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

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

List.c

//查找
ListNode* ListCheckNode(ListNode* phead, LTNDataType num)
{
	assert(!ListEmpty(phead));
	ListNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == num)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

3.5.6 在指定位置之前插入数据

List.c

//在指定位置之前插入数据
void ListInsertFront(ListNode* pos, LTNDataType num)
{
	assert(pos);
	//为新节点创建空间
	ListNode* newonde = ListBuyNode(num);
	newonde->next = pos;
	newonde->prev = pos->prev;
	pos->prev->next = newonde;
	pos->prev = newonde;
}

3.5.6 在指定位置之后插入数据

List.c

//在指定位置之后插入数据
void ListInsertBack(ListNode* pos, LTNDataType num)
{
	assert(pos);
	//为新节点创建空间
	ListNode* newnode = ListBuyNode(num);
	newnode->prev = pos;
	newnode->next = pos->next;
	pos->next->prev = newnode;
	pos->next = newnode;
}

3.5.7 删除指定位置上的数据

List.c

//删除指定位置上的数据
void ListErase(ListNode* pos)
{
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}

3.5.8 删除指定位置之前的数据

List.c

//删除指定位置之前的数据
void ListEraseFront(ListNode* pos)
{
	assert(pos);
	ListNode* del = pos->prev;
	del->prev->next = pos;
	pos->prev = del->prev;
	free(del);
	del = NULL;
}

3.5.9 删除指定位置之后的数据

List.c

//删除指定位置之后的数据
void ListEraseBack(ListNode* pos)
{
	assert(pos);
	ListNode* del = pos->next;
	del->next->prev = pos;
	pos->next = del->next;
	free(del);
	del = NULL;
}

3.5.10 修改指定位置上的数据

//修改指定位置上的数据
void ListChangeNode(ListNode* pos, LTNDataType num)
{
	assert(pos);
	pos->data = num;
}

3.5.11 销毁链表

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

List.c

//销毁链表
void ListDestory(ListNode** pphead)
{
	ListNode* pcur = (*pphead)->next;
	while (pcur != *pphead)
	{
		ListNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(*pphead);
	*pphead = NULL;
}

四、完整代码

List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//双链表的结构
typedef int LTNDataType;
typedef struct ListNode
{
	LTNDataType data;//存储数据
	struct ListNode* prev;//指针保存上一个节点的地址
	struct ListNode* next;//指针保存的是下一个结点的地址
}ListNode;
//打印
void ListPrint(ListNode* phead);
//要改变头节点plist——要用二级指针
//初始化
void ListInit(ListNode** pphead);
//ListNode* ListInit();
//尾插
void ListPushBack(ListNode* phead, LTNDataType num);
//头插
void ListPushFront(ListNode* phead, LTNDataType num);
//尾删
void ListPopBack(ListNode* phead);
//头删
void ListPopFront(ListNode* phead);
//查找
ListNode* ListCheckNode(ListNode* phead, LTNDataType num);
//在指定位置之后插入数据
void ListInsertBack(ListNode* pos, LTNDataType num);
//在指定位置之前插入数据
void ListInsertFront(ListNode* pos, LTNDataType num);
//删除指定位置上的数据
void ListErase(ListNode* pos);
//删除指定位置之前的数据
void ListEraseFront(ListNode* pos);
//删除指定位置之后的数据
void ListEraseBack(ListNode* pos);
//修改指定位置上的数据
void ListChangeNode(ListNode* pos, LTNDataType num);
//判断链表是否为空
bool ListEmpty(ListNode* phead);
//销毁链表
void ListDestory(ListNode** pphead);

List.c

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
//创建空间
ListNode* ListBuyNode(LTNDataType num)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = num;
	newnode->prev = newnode->next = newnode;
	return newnode;
}
//初始化
void ListInit(ListNode** pphead)
{
	ListNode* tmp = (ListNode*)malloc(sizeof(ListNode));
	if (tmp == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	*pphead = tmp;
	(*pphead)->data = -1;
	(*pphead)->prev = (*pphead)->next = *pphead;
}
//打印
void ListPrint(ListNode* phead)
{
	assert(phead);
	ListNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d -> ", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}
//判断链表是否为空
bool ListEmpty(ListNode* phead)
{
	assert(phead);
	//头结点自己指向自己，说明链表为空
	return phead->next == phead;
}
//尾插
void ListPushBack(ListNode* phead, LTNDataType num)
{
	assert(phead);
	//为新节点创建空间
	ListNode* newnode = ListBuyNode(num);
	//先改变newnode的指向
	newnode->prev = phead->prev;
	newnode->next = phead;
	phead->prev->next = newnode;
	phead->prev = newnode;
}
//头插
//在头结点的后面插入
void ListPushFront(ListNode* phead, LTNDataType num)
{
	assert(phead);
	//为新结点创建空间
	ListNode* newnode = ListBuyNode(num);
	newnode->prev = phead;
	newnode->next = phead->next;
	phead->next->prev = newnode;
	phead->next = newnode;
}
//尾删
void ListPopBack(ListNode* phead)
{
	//判断双链表是否为空
	assert(!ListEmpty(phead));
	ListNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;
	free(del);
	del = NULL;
}
//头删
void ListPopFront(ListNode* phead)
{
	assert(!ListEmpty(phead));
	ListNode* del = phead->next;
	del->next->prev = phead;
	phead->next = del->next;
	free(del);
	del = NULL;
}
//查找
ListNode* ListCheckNode(ListNode* phead, LTNDataType num)
{
	assert(!ListEmpty(phead));
	ListNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == num)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}
//在指定位置之后插入数据
void ListInsertBack(ListNode* pos, LTNDataType num)
{
	assert(pos);
	//为新节点创建空间
	ListNode* newnode = ListBuyNode(num);
	newnode->prev = pos;
	newnode->next = pos->next;
	pos->next->prev = newnode;
	pos->next = newnode;
}
//在指定位置之前插入数据
void ListInsertFront(ListNode* pos, LTNDataType num)
{
	assert(pos);
	//为新节点创建空间
	ListNode* newonde = ListBuyNode(num);
	newonde->next = pos;
	newonde->prev = pos->prev;
	pos->prev->next = newonde;
	pos->prev = newonde;
}
//删除指定位置上的数据
void ListErase(ListNode* pos)
{
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}
//删除指定位置之前的数据
void ListEraseFront(ListNode* pos)
{
	assert(pos);
	ListNode* del = pos->prev;
	del->prev->next = pos;
	pos->prev = del->prev;
	free(del);
	del = NULL;
}
//删除指定位置之后的数据
void ListEraseBack(ListNode* pos)
{
	assert(pos);
	ListNode* del = pos->next;
	del->next->prev = pos;
	pos->next = del->next;
	free(del);
	del = NULL;
}
//修改指定位置上的数据
void ListChangeNode(ListNode* pos, LTNDataType num)
{
	assert(pos);
	pos->data = num;
}
//销毁链表
void ListDestory(ListNode** pphead)
{
    ListNode* pcur = (*pphead)->next;
	while (pcur != *pphead)
	{
		ListNode* next = pcur->next;
		free(pcur);
	    pcur = next;
	}
	free(*pphead);
	*pphead = NULL;
}

test.c

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
void test01()
{
	ListNode* plist = NULL;
	ListInit(&plist);
	//尾插
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPushBack(plist, 5);
	ListPushBack(plist, 6);
	ListPrint(plist);
	//头插
	ListPushFront(plist, 1);
	ListPushFront(plist, 0);
	ListPrint(plist);
	//尾删
	ListPopBack(plist);
	ListPrint(plist);
	//头删
	ListPopFront(plist);
	ListPrint(plist);
	//查找
	ListNode* pos = ListCheckNode(plist, 5);
	//在指定位置后面插入
	ListInsertBack(pos, 6);
	ListPrint(plist);
	//在指定位置之前插入
	pos = ListCheckNode(plist, 1);
	ListInsertFront(pos, 0);
	ListPrint(plist);
	//删除指定位置上的数据
	ListErase(pos);
	ListPrint(plist);
	//删除指定位置之前的数据
	pos = ListCheckNode(plist, 4);
	ListEraseFront(pos);
	ListPrint(plist);
	//删除指定位置之后的数据
	ListEraseBack(pos);
	ListPrint(plist);
	ListEraseBack(pos);
	ListPrint(plist);
	//销毁链表
	ListDestory(&plist);
}
int main()
{
	test01();
	return 0;
}

ok，写到这里我们就完成了双链表的代码书写，但是我们发现上面的代码中，除了初始化和销毁的代码，其余的函数声明中都是一级指针，所以我们需要考虑接口的一致性。

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

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

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

5.1 初始化优化

List.c

ListNode* ListInit(LTNDataType num)
{
	ListNode* phead = ListBuyNode(-1);
	return phead;
}

test.c

#define  _CRT_SECURE_NO_WARNINGS  1
 
#include"List.h"
 
void test01()
{
	/*ListNode* plist = NULL;
    ListInit(&plist);*/
    ListNode* plist = ListInit(-1);
}
 
int main()
{
	test01();
	return 0;
}

5.2 销毁优化

List.c

void ListDestory(ListNode* phead)
{
	ListNode* pcur = phead->next;
	while (pcur != phead)
	{
		ListNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
}

test..c

void test01()
{
    //销毁链表
    ListDestory(plist);
    plist = NULL;
}
int main()
{
    test01();
    return 0;
}

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

5.3 优化后完整代码

List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//双链表的结构
typedef int LTNDataType;
typedef struct ListNode
{
	LTNDataType data;//存储数据
	struct ListNode* prev;//指针保存上一个节点的地址
	struct ListNode* next;//指针保存的是下一个结点的地址
}ListNode;
//打印
void ListPrint(ListNode* phead);
//初始化
ListNode* ListInit(LTNDataType num);
//尾插
void ListPushBack(ListNode* phead, LTNDataType num);
//头插
void ListPushFront(ListNode* phead, LTNDataType num);
//尾删
void ListPopBack(ListNode* phead);
//头删
void ListPopFront(ListNode* phead);
//查找
ListNode* ListCheckNode(ListNode* phead, LTNDataType num);
//在指定位置之后插入数据
void ListInsertBack(ListNode* pos, LTNDataType num);
//在指定位置之前插入数据
void ListInsertFront(ListNode* pos, LTNDataType num);
//删除指定位置上的数据
void ListErase(ListNode* pos);
//删除指定位置之前的数据
void ListEraseFront(ListNode* pos);
//删除指定位置之后的数据
void ListEraseBack(ListNode* pos);
//修改指定位置上的数据
void ListChangeNode(ListNode* pos, LTNDataType num);
//判断链表是否为空
bool ListEmpty(ListNode* phead);
//销毁链表
void ListDestory(ListNode* phead);

List.c

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
//创建空间
ListNode* ListBuyNode(LTNDataType num)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = num;
	newnode->prev = newnode->next = newnode;
	return newnode;
}
//初始化
ListNode* ListInit(LTNDataType num)
{
	ListNode* phead = ListBuyNode(-1);
	return phead;
}
//打印
void ListPrint(ListNode* phead)
{
	assert(phead);
	ListNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d -> ", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}
//判断链表是否为空
bool ListEmpty(ListNode* phead)
{
	assert(phead);
	//头结点自己指向自己，说明链表为空
	return phead->next == phead;
}
//尾插
void ListPushBack(ListNode* phead, LTNDataType num)
{
	assert(phead);
	//为新节点创建空间
	ListNode* newnode = ListBuyNode(num);
	//先改变newnode的指向
	newnode->prev = phead->prev;
	newnode->next = phead;
	phead->prev->next = newnode;
	phead->prev = newnode;
}
//头插
//在头结点的后面插入
void ListPushFront(ListNode* phead, LTNDataType num)
{
	assert(phead);
	//为新结点创建空间
	ListNode* newnode = ListBuyNode(num);
	newnode->prev = phead;
	newnode->next = phead->next;
	phead->next->prev = newnode;
	phead->next = newnode;
}
//尾删
void ListPopBack(ListNode* phead)
{
	//判断双链表是否为空
	assert(!ListEmpty(phead));
	ListNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;
	free(del);
	del = NULL;
}
//头删
void ListPopFront(ListNode* phead)
{
	assert(!ListEmpty(phead));
	ListNode* del = phead->next;
	del->next->prev = phead;
	phead->next = del->next;
	free(del);
	del = NULL;
}
//查找
ListNode* ListCheckNode(ListNode* phead, LTNDataType num)
{
	assert(!ListEmpty(phead));
	ListNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == num)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}
//在指定位置之后插入数据
void ListInsertBack(ListNode* pos, LTNDataType num)
{
	assert(pos);
	//为新节点创建空间
	ListNode* newnode = ListBuyNode(num);
	newnode->prev = pos;
	newnode->next = pos->next;
	pos->next->prev = newnode;
	pos->next = newnode;
}
//在指定位置之前插入数据
void ListInsertFront(ListNode* pos, LTNDataType num)
{
	assert(pos);
	//为新节点创建空间
	ListNode* newonde = ListBuyNode(num);
	newonde->next = pos;
	newonde->prev = pos->prev;
	pos->prev->next = newonde;
	pos->prev = newonde;
}
//删除指定位置上的数据
void ListErase(ListNode* pos)
{
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}
//删除指定位置之前的数据
void ListEraseFront(ListNode* pos)
{
	assert(pos);
	ListNode* del = pos->prev;
	del->prev->next = pos;
	pos->prev = del->prev;
	free(del);
	del = NULL;
}
//删除指定位置之后的数据
void ListEraseBack(ListNode* pos)
{
	assert(pos);
	ListNode* del = pos->next;
	del->next->prev = pos;
	pos->next = del->next;
	free(del);
	del = NULL;
}
//修改指定位置上的数据
void ListChangeNode(ListNode* pos, LTNDataType num)
{
	assert(pos);
	pos->data = num;
}
//销毁链表
void ListDestory(ListNode* phead)
{
	ListNode* pcur = phead->next;
	while (pcur != phead)
	{
		ListNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
}

test.c

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
void test01()
{
	ListNode* plist = ListInit(-1);
	//尾插
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPushBack(plist, 5);
	ListPushBack(plist, 6);
	ListPrint(plist);
	//头插
	ListPushFront(plist, 1);
	ListPushFront(plist, 0);
	ListPrint(plist);
	//尾删
	ListPopBack(plist);
	ListPrint(plist);
	//头删
	ListPopFront(plist);
	ListPrint(plist);
	//查找
	ListNode* pos = ListCheckNode(plist, 5);
	//在指定位置后面插入
	ListInsertBack(pos, 6);
	ListPrint(plist);
	//在指定位置之前插入
	pos = ListCheckNode(plist, 1);
	ListInsertFront(pos, 0);
	ListPrint(plist);
	//删除指定位置上的数据
	ListErase(pos);
	ListPrint(plist);
	//删除指定位置之前的数据
	pos = ListCheckNode(plist, 4);
	ListEraseFront(pos);
	ListPrint(plist);
	//删除指定位置之后的数据
	ListEraseBack(pos);
	ListPrint(plist);
	ListEraseBack(pos);
	ListPrint(plist);
	//销毁链表
	ListDestory(plist);
	plist = NULL;
}
int main()
{
	test01();
	return 0;
}

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

如果在今后需要进行数据的任意插入和删除，使用链表；若需要大量的存储数据和访问，使用顺序表