C语言实现单链表 && 双向链表

文章目录

• 一、单链表
• • 1.单链表的概念
  • 2.单链表与顺序表的比较
  • 3.单链表的基本操作接口
  • 4.单链表的结构定义
  • 5.动态申请一个节点
  • 6.单链表的打印
  • 7.为什么要传送二级指针？？？
  • 8.单链表的增删查改
  • • 8.1单链表的尾插
    • 8.2 单链表的尾删
    • 8.3 单链表的头插
    • 8.4 单链表的头删
    • 8.5 单链表的查找
    • 8.6单链表在pos位置之后插入节点
    • 8.7单链表删除在pos位置之后的节点
    • 8.8单链表的销毁
  • 9.整体代码实现
  • • 9.1 SList.h
    • 9.2 SList.c
• 二、带头循环双向链表
• • 1.带头循环双向链表的优点
  • 2.双向链表的接口函数
  • 3.带头循环双向链表的结构
  • 4.创建返回链表的头节点
  • 带头循环双向链表的打印
  • 5.带头循环双向链表的增删查改
  • • 5.1创建新节点
    • 5.2双向链表的尾插
    • 5.3双向链表的尾删
    • 5.4双向链表的头插
    • 5.5双向链表的头删
    • 5.6双向链表的查找
    • 5.7双向链表在pos位置之前插入节点
    • 5.8双向链表在pos位置删除节点
    • 5.9 Insert和Erase的复用
    • • 5.9.1双向链表尾插
      • 5.9.2双向链表尾删
      • 5.9.3双向链表头插
      • 5.9.4双向链表头删
    • 6.带头循环双向链表的销毁
  • 6.整体代码实现
  • • 6.1 DList.h
    • 6.2 DList.c
• 三、单链表与双向链表

---

一、单链表 1.单链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接在一起的。
链表用节点的方式存储了数据以及其指向的下一个节点的地址，分别为存储有效数据数据的数据域，存储下一节点的地址的指针域。单链表只有一个指针域，而双向链表有两个。

2.单链表与顺序表的比较

结构上：
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,即顺序表相邻元素之间的物理位置和逻辑位置皆相邻。
链表则是用一段物理地址非连续的存储结构存储数据，即链表存储结构逻辑上是相邻的，但物理上不相邻。

顺序表的优缺点：
优点：
1.空间连续，支持随机访问。
缺点：
1.中间或前面部分的插入删除时间复杂度O(N)；
2.增容代价比较大；
单链表的优缺点：
优点：
1.进行头部插入和头部删除的时间复杂度为O(1)；
2.没有增容问题，每次插入一个开辟一个空间；
缺点：
1.以节点为单位存储，不支持随机访问；

3.单链表的基本操作接口

以下实现的单链表皆无哨兵位头节点。

//单链表基本操作的接口
//动态申请一个节点
SListNode* BuySListNode(SLDataType val);
//单链表的打印
void SListPrint(SListNode* phead);
//单链表的尾插
void SListPushBack(SListNode** pphead, SLDataType val);
//单链表的尾删
void SListPopBack(SListNode** pphead);
//单链表的头插
void SListPushFront(SListNode** pphead, SLDataType val);
//单链表的头删
void SListPopFront(SListNode** pphead);
//单链表的查找
SListNode* SListFind(SListNode* phead, SLDataType val);
//单链表在pos位置之后插入
void SListInsertAfter(SListNode* pos, SLDataType val);
//单链表删除pos位置之后的节点
void SListEraseAfter(SListNode* pos);
//单链表的销毁
void SListDestory(SListNode** pphead);

4.单链表的结构定义

typedef int SLDataType;
typedef struct SListNode
{
	struct SListNode* next;//存储下一个节点的地址
	SLDataType val;//存储有效数据
}SListNode;

5.动态申请一个节点

//动态申请一个节点
SListNode* BuySListNode(SLDataType val)
{
	//申请节点
	SListNode* new_node = (SListNode*)malloc(sizeof(SListNode));
	assert(new_node);//判断节点是否申请失败
	//对数据域和指针域赋值
	new_node->next = NULL;
	new_node->val = val;
}

6.单链表的打印

//单链表的打印
void SListPrint(SListNode* phead)
{
	SListNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
	printf("NULLn");
}

7.为什么要传送二级指针？？？

为什么要传送二级指针，是无头单链表的最难点，这考察你对指针和结构体的知识掌握是否熟练。
在部分情况下，如在链表为空的情况下插入节点，在链表只有一个节点时删除节点，都需要你改变指向头节点的指针的指向,但由于函数的形参的只是实参的一份临时拷贝，改变形参不会影响实参的改变，所以你需要传送实参的指针，也就是头节点的指针的指针。
传送一级指针的作用：
如果你传送的是节点的指针，那么你可以修改节点中的指针域和数据域，但无法修改你传送的一级指针的指向；如：打印链表，在pos位置后插入数据；这些都不需要你修改头节点的指针的指向，所以使用一级指针便够了。
总结：
传送一级指针，允许你修改节点中的内容。
传送二级指针，允许你修改指向节点的指针的指向，并且也允许你修改节点中的内容。

8.单链表的增删查改 8.1单链表的尾插

注意：
无头单链表的尾插需要划分两种情况：1.链表为空；2.链表不为空；
当链表为空时，我们需要修改头节点指针的指向，让其指向新开辟的节点，所以需要使用二级指针；
当链表不为空时，我们需要遍历链表，直到链表的尾节点，再让其指针域指向新开辟的节点，此操作便与二级指针无关。

//单链表的尾插
void SListPushBack(SListNode** pphead, SLDataType val)
{
	assert(pphead);//pphead不可能为空
	
	//创建节点
	SListNode* new_node = BuySListNode(val);
	//尾插数据
	//1.链表为空
	if ((*pphead) == NULL)
	{
		//修改头节点的指向
		*pphead = new_node;
	}
	else
	{
		//2.链表不为空
		SListNode* tail = *pphead;
		//寻找尾节点
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		//插入数据
		tail->next = new_node;
	}
}

8.2 单链表的尾删

注意：
无头单链表的尾删划分为两种情况：1.链表中只有一个节点；2.链表中有两个及以上节点；
当链表只有一个节点时，先释放掉唯一的节点，再将头节点的指针指向NULL,此时需要使用二级指针，才能将外部实参同样修改为指向NULL；
当链表有两个及两个以上的节点时，只需要遍历链表，寻找到尾节点的前一个节点,然后释放掉尾节点，让尾节点的前一个节点的指针域指向NULL。

void SListPopBack(SListNode** pphead)
{
	assert(pphead);
	assert(*pphead != NULL);//确保有节点可删

	//删除节点
	//链表只有一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//链表有两个及以上节点
		//寻找尾节点的前一个节点
		SListNode* cur = *pphead;
		while (cur->next->next != NULL)
		{
			cur = cur->next;
		}
		//释放尾节点，让尾节点的前一个节点指针域指向NULL
		SListNode* tail = cur->next;
		cur->next = NULL;
		free(tail);
	}
}

8.3 单链表的头插

注意：在无头单链表中头插节点，任何情况下都需要改变头节点指针的指向，让其指向新的头节点；

//单链表的头插
void SListPushFront(SListNode** pphead, SLDataType val)
{
	assert(pphead);

	//创建新节点
	SListNode* new_node = BuySListNode(val);
	assert(new_node);//检查申请是否成功
	
	SListNode* next = *pphead;//记录原链表的头节点
	//在头节点前插入新节点
	*pphead = new_node;//让头节点的指针指向新节点
	new_node->next = next;
}

8.4 单链表的头删

注意：单链表的头删与头插一样，任何情况下都需要改变头节点指针的指向；让头节点指针指向原链表中头节点的下一个节点。

//单链表的头删
void SListPopFront(SListNode** pphead)
{
	assert(pphead);
	assert(*pphead != NULL);//确保有节点可删

	SListNode* next = (*pphead)->next;//记录下头节点的下一个节点
	free(*pphead);
	*pphead = next;
}

8.5 单链表的查找

单链表的查找只需要依次遍历链表，找到值相等的节点便可访问该节点，找不到则返回NULL；
由于不需要改变头节点的指向，所以只需要传递一级指针。

//单链表的查找
SListNode* SListFind(SListNode* phead, SLDataType val)
{
	assert(phead);
	
	SListNode* pos = phead;
	while (pos != NULL)
	{
		if (pos->val == val)
		{
			return pos;
		}
		pos = pos->next;
	}
	return NULL;
}

8.6单链表在pos位置之后插入节点

//单链表在pos位置之后插入节点
void SListInsertAfter(SListNode* pos, SLDataType val)
{
	assert(pos);

	//创建新节点
	SListNode* new_node = BuySListNode(val);
	
	//在pos后插入数据	
	SListNode* next = pos->next;//记录原pos位置之后的节点
	pos->next = new_node;
	new_node->next = next;
}

8.7单链表删除在pos位置之后的节点

//单链表删除在pos位置之后的节点
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	assert(pos->next != NULL);
	
	SListNode* next = pos->next;
	pos->next = next->next;
	free(next);
}

8.8单链表的销毁

//销毁单链表
void SListDestory(SListNode** pphead)
{
	assert(pphead);

	SListNode* cur = *pphead;
	//遍历链表，依次对每个节点进行释放
	while (cur != NULL)
	{
		SListNode* next = cur->next;
		free(cur);//释放当前节点
		cur = next;
	}
	*pphead = NULL;
}

9.整体代码实现 9.1 SList.h

#pragma once
#include
#include
#include

typedef int SLDataType;
typedef struct SListNode
{
	struct SListNode* next;//存储下一个节点的地址
	SLDataType val;//存储有效数据
}SListNode;

//单链表基本操作的接口
//动态申请一个节点
SListNode* BuySListNode(SLDataType val);
//单链表的打印
void SListPrint(SListNode* phead);
//单链表的尾插
void SListPushBack(SListNode** pphead, SLDataType val);
//单链表的尾删
void SListPopBack(SListNode** pphead);
//单链表的头插
void SListPushFront(SListNode** pphead, SLDataType val);
//单链表的头删
void SListPopFront(SListNode** pphead);
//单链表的查找
SListNode* SListFind(SListNode* phead, SLDataType val);
//单链表在pos位置之后插入
void SListInsertAfter(SListNode* pos, SLDataType val);
//单链表删除pos位置之后的节点
void SListEraseAfter(SListNode* pos);
//单链表的销毁
void SListDestory(SListNode** pphead);

9.2 SList.c

#include"List.h"

//动态申请一个节点
SListNode* BuySListNode(SLDataType val)
{
	//申请节点
	SListNode* new_node = (SListNode*)malloc(sizeof(SListNode));
	assert(new_node);//判断节点是否申请失败
	//对数据域和指针域赋值
	new_node->next = NULL;
	new_node->val = val;
}

//单链表的打印
void SListPrint(SListNode* phead)
{
	SListNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
	printf("NULLn");
}

//单链表的尾插
void SListPushBack(SListNode** pphead, SLDataType val)
{
	assert(pphead);//pphead不可能为空
	
	//创建节点
	SListNode* new_node = BuySListNode(val);
	//尾插数据
	//1.链表为空
	if ((*pphead) == NULL)
	{
		//修改头节点的指向
		*pphead = new_node;
	}
	else
	{
		//2.链表不为空
		SListNode* tail = *pphead;
		//寻找尾节点
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		//插入数据
		tail->next = new_node;
	}
}

//单链表的尾删
void SListPopBack(SListNode** pphead)
{
	assert(pphead);
	assert(*pphead != NULL);//确保有节点可删

	//删除节点
	//链表只有一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//链表有两个及以上节点
		//寻找尾节点的前一个节点
		SListNode* cur = *pphead;
		while (cur->next->next != NULL)
		{
			cur = cur->next;
		}
		//释放尾节点，让尾节点的前一个节点指针域指向NULL
		SListNode* tail = cur->next;
		cur->next = NULL;
		free(tail);
	}
}

//单链表的头插
void SListPushFront(SListNode** pphead, SLDataType val)
{
	assert(pphead);

	//创建新节点
	SListNode* new_node = BuySListNode(val);
	assert(new_node);//检查申请是否成功
	
	SListNode* next = *pphead;//记录原链表的头节点
	//在头节点前插入新节点
	*pphead = new_node;//让头节点的指针指向新节点
	new_node->next = next;
}

//单链表的头删
void SListPopFront(SListNode** pphead)
{
	assert(pphead);
	assert(*pphead != NULL);//确保有节点可删

	SListNode* next = (*pphead)->next;//记录下头节点的下一个节点
	free(*pphead);
	*pphead = next;
}

//单链表的查找
SListNode* SListFind(SListNode* phead, SLDataType val)
{
	assert(phead);
	
	SListNode* pos = phead;
	while (pos != NULL)
	{
		if (pos->val == val)
		{
			return pos;
		}
		pos = pos->next;
	}
	return NULL;
}

//单链表在pos位置之后插入节点
void SListInsertAfter(SListNode* pos, SLDataType val)
{
	assert(pos);

	//创建新节点
	SListNode* new_node = BuySListNode(val);
	
	//在pos后插入数据	
	SListNode* next = pos->next;//记录原pos位置之后的节点
	pos->next = new_node;
	new_node->next = next;
}

//单链表删除在pos位置之后的节点
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	assert(pos->next != NULL);
	
	SListNode* next = pos->next;
	pos->next = next->next;
	free(next);
}

//销毁单链表
void SListDestory(SListNode** pphead)
{
	assert(pphead);

	SListNode* cur = *pphead;
	//遍历链表，依次对每个节点进行释放
	while (cur != NULL)
	{
		SListNode* next = cur->next;
		free(cur);//释放当前节点
		cur = next;
	}
	*pphead = NULL;
}

二、带头循环双向链表 1.带头循环双向链表的优点

在前面我们可以发现：单链表在处理尾插尾删，任意位置插入删除时，其时间复杂度都为O(N)，为了提高效率，便引入了带头双向循环链表。虽然其结构较之单链表更为复杂，但其实现却异常简单。

2.双向链表的接口函数

//带头循环双向链表的函数接口
//创建返回链表的头节点
DListNode* ListNodeCreate();
//双向链表的打印
void ListPrint(DListNode* phead);
//双向链表的尾插
void ListPushBack(DListNode* phead, DLDataType val);
//双向链表的尾删
void ListPopBack(DListNode* phead);
//双向链表的头插
void ListPushFront(DListNode* phead, DLDataType val);
//双向链表的头删
void ListPopFront(DListNode* phead);
//双向链表的寻找
DListNode* ListFind(DListNode* phead, DLDataType val);
//双向链表在pos位置前面插入节点
void ListInsert(DListNode* pos, DLDataType val);
//双向链表删除pos位置的节点
void ListErase(DListNode* pos);
//双向链表的销毁
void ListDestory(DListNode* phead);

3.带头循环双向链表的结构

带头循环双向链表同样以节点的形式存储数据：
1.它的指针域存储着两个指针：一个指向前一个节点，另一个指向下一个节点。
2.它的头部节点由一个哨兵位节点构成，其节点并不存储有效数据，并且不参与增删查改等操作，这也意味着其头节点的指针不需要被改变
3.它的尾节点不再指向NULL，而是指向第一个头节点，也就是哨兵位节点。

typedef int DLDataType;
typedef struct DListNode
{
	struct DListNode* next;//存储下一个节点的地址
	struct DListNode* prev;//存储前一个节点的地址
	DLDataType val;//存储有效数据
}DListNode;

4.创建返回链表的头节点

注意：刚创建的哨兵位节点的两个指针应该都指向自己。

DListNode* ListNodeCreate()
{
	DListNode* guard = (DListNode*)malloc(sizeof(DListNode));
	assert(guard);//检查是否申请成功
	guard->next = guard;
	guard->prev = guard;
	return guard;
}

带头循环双向链表的打印

注意：由于尾节点的next指针已经不再是指向NULL，而是指向哨兵位节点，在判断结束时应该小心这一点。

//双向链表的打印
void ListPrint(DListNode* phead)
{
	assert(phead);
	printf("head<=>");
	DListNode* cur = phead->next;
	//尾节点的next应该是指向哨兵位节点
	while (cur != phead)
	{
		printf("%d<=>", cur->val);
		cur = cur->next;
	}
	printf("headn");
}

5.带头循环双向链表的增删查改 5.1创建新节点

DListNode* BuyListNode(DLDataType val)
{
	DListNode* new_node = (DListNode*)malloc(sizeof(DListNode));
	assert(new_node);
	new_node->val = val;
	new_node->next = new_node;
	new_node->prev = new_node;

	return new_node;
}

5.2双向链表的尾插

//双向链表的尾插
void ListPushBack(DListNode* phead, DLDataType val)
{
	assert(phead);
	//寻找尾节点
	//哨兵位的前一个节点就是尾节点
	DListNode* tail = phead->prev;
	
	//创建新节点
	DListNode* new_node = BuyListNode(val);

	//尾插新节点
	tail->next = new_node;//1.原尾节点的下一个节点指针指向新节点
	new_node->next = phead;//2.新节点的下一个节点指向哨兵位
	new_node->prev = tail;//3.新节点的前一个节点指针指向原尾节点
	phead->prev = new_node;//4.哨兵位前一个节点指针指向新节点
}

当链表为空时，上述代码是否仍适用呢？
答案是能的！

5.3双向链表的尾删

由于尾节点的存在，就不需要判断该链表只剩一个节点的情况。
链表只剩一个节点，该哨兵位的前一个节点指针和下一个结点指针都指向自己。

//双向链表的尾删
void ListPopBack(DListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//确保有节点可删
	
	//寻找尾节点
	DListNode* tail = phead->prev;
	//寻找尾节点的前一个节点
	DListNode* prev = tail->prev;

	//删除尾节点
	prev->next = phead;
	phead->prev = prev;
	free(tail);
}

5.4双向链表的头插

//双向链表的头插
void ListPushFront(DListNode* phead, DLDataType val)
{
	assert(phead);
	//寻找原链表的第一个有效头节点
	DListNode* next = phead->next;
	
	//创建新节点
	DListNode* new_node = BuyListNode(val);
	
	//插入数据
	phead->next = new_node;//1.头节点的下一个节点指针指向新节点
	new_node->prev = phead;//2.新节点的前一个节点指针指向头节点
	new_node->next = next;//3.新节点的下一个节点指针指向原链表的有效头节点
	next->prev = new_node;//4.原链表的有效头节点前一个节点指针指向新节点
}

5.5双向链表的头删

//双向链表的头删
void ListPopFront(DListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);

	//寻找哨兵位以外的头节点
	DListNode* cur = phead->next;
	//寻找头节点的下一个节点
	DListNode* next = cur->next;

	//删除节点
	phead->next = next;
	next->prev = phead;
	free(cur);
}

5.6双向链表的查找

//双向链表的查找
DListNode* ListFind(DListNode* phead, DLDataType val)
{
	assert(phead);
	assert(phead->next != phead);

	//遍历链表查找
	DListNode* cur = phead->next;
	//尾节点的next指向phead
	while (cur != phead)
	{
		if (cur->val == val)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

5.7双向链表在pos位置之前插入节点

//双向链表在pos位置之前插入节点
void ListInsert(DListNode* pos, DLDataType val)
{
	assert(pos);
	
	//创建节点
	DListNode* new_node = BuyListNode(val);

	//寻找pos位置的前一个节点
	DListNode* prev = pos->prev;
	
	//插入数据
	new_node->next = pos;//1
	pos->prev = new_node;//2
	new_node->prev = prev;//3
	prev->next = new_node;//4
}

5.8双向链表在pos位置删除节点

//双向链表在pos位置删除节点
void ListErase(DListNode* pos)
{
	assert(pos);
	assert(pos->next != pos);//有节点可删
	
	//记录pos的前一个节点
	DListNode* prev = pos->prev;
	//记录pos的后一个节点
	DListNode* next = pos->next;

	//删除节点
	prev->next = next;//1
	next->prev = prev;//2
	free(pos);//3
}

5.9 Insert和Erase的复用 5.9.1双向链表尾插

//双向链表的尾删
void ListPopBack(DListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//确保有节点可删
	
	//Erase的复用
	ListErase(phead->prev);
}

5.9.2双向链表尾删

void ListPopBack(DListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//确保有节点可删
	
	//Erase的复用
	ListErase(phead->prev);
}

5.9.3双向链表头插

//双向链表的头插
void ListPushFront(DListNode* phead, DLDataType val)
{
	assert(phead);

	//Insert的复用
	ListInsert(phead->next, val);
}

5.9.4双向链表头删

//双向链表的头删
void ListPopFront(DListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);

	//Erase的复用
	ListErase(phead->next);
}

6.带头循环双向链表的销毁

链表的销毁可以使用二级指针，因为需要将指向哨兵位的指针置空；但为了接口的一致性，我们这里只传一级指针，让调用者在外部自行置空。

//双向链表的销毁
void ListDestory(DListNode* phead)
{
	DListNode* cur = phead->next;
	//依次释放哨兵位以外的节点
	while (cur != phead)
	{
		DListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	//释放哨兵位
	free(phead);
}

6.整体代码实现 6.1 DList.h

#pragma once
#include
#include
#include


typedef int DLDataType;
typedef struct DListNode
{
	struct DListNode* next;//存储下一个节点的地址
	struct DListNode* prev;//存储前一个节点的地址
	DLDataType val;//存储有效数据
}DListNode;

//带头循环双向链表的函数接口
//创建返回链表的头节点
DListNode* ListNodeCreate();
//双向链表的打印
void ListPrint(DListNode* phead);
//双向链表的尾插
void ListPushBack(DListNode* phead, DLDataType val);
//双向链表的尾删
void ListPopBack(DListNode* phead);
//双向链表的头插
void ListPushFront(DListNode* phead, DLDataType val);
//双向链表的头删
void ListPopFront(DListNode* phead);
//双向链表的寻找
DListNode* ListFind(DListNode* phead, DLDataType val);
//双向链表在pos位置前面插入节点
void ListInsert(DListNode* pos, DLDataType val);
//双向链表删除pos位置的节点
void ListErase(DListNode* pos);
//双向链表的销毁
void ListDestory(DListNode* phead);

6.2 DList.c

#include"DList.h"

//创建返回链表的头节点
DListNode* ListNodeCreate()
{
	DListNode* guard = (DListNode*)malloc(sizeof(DListNode));
	assert(guard);//检查是否申请成功
	guard->next = guard;
	guard->prev = guard;
	return guard;
}

//双向链表的打印
void ListPrint(DListNode* phead)
{
	assert(phead);
	printf("head<=>");
	DListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<=>", cur->val);
		cur = cur->next;
	}
	printf("headn");
}

DListNode* BuyListNode(DLDataType val)
{
	DListNode* new_node = (DListNode*)malloc(sizeof(DListNode));
	assert(new_node);
	new_node->val = val;
	new_node->next = new_node;
	new_node->prev = new_node;

	return new_node;
}

//双向链表的尾插
void ListPushBack(DListNode* phead, DLDataType val)
{
	assert(phead);
	//寻找尾节点
	//哨兵位的前一个节点就是尾节点
	//DListNode* tail = phead->prev;
	//
	创建新节点
	//DListNode* new_node = BuyListNode(val);

	尾插新节点
	//tail->next = new_node;//原尾节点的下一个节点指针指向新节点
	//new_node->next = phead;//新节点的下一个节点指向哨兵位
	//new_node->prev = tail;//新节点的前一个节点指针指向原尾节点
	//phead->prev = new_node;//哨兵位前一个节点指针指向新节点

	//Insert的复用
	ListInsert(phead, val);
}

//双向链表的尾删
void ListPopBack(DListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//确保有节点可删
	
	寻找尾节点
	//DListNode* tail = phead->prev;
	寻找尾节点的前一个节点
	//DListNode* prev = tail->prev;

	删除尾节点
	//prev->next = phead;
	//phead->prev = prev;
	//free(tail);

	//Erase的复用
	ListErase(phead->prev);
}

//双向链表的头插
void ListPushFront(DListNode* phead, DLDataType val)
{
	assert(phead);
	寻找原链表的第一个有效头节点
	//DListNode* next = phead->next;
	//
	创建新节点
	//DListNode* new_node = BuyListNode(val);
	//
	插入数据
	//phead->next = new_node;//1.头节点的下一个节点指针指向新节点
	//new_node->prev = phead;//2.新节点的前一个节点指针指向头节点
	//new_node->next = next;//3.新节点的下一个节点指针指向原链表的有效头节点
	//next->prev = new_node;//4.原链表的有效头节点前一个节点指针指向新节点

	//Insert的复用
	ListInsert(phead->next, val);
}

//双向链表的头删
void ListPopFront(DListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);

	寻找哨兵位以外的头节点
	//DListNode* cur = phead->next;
	寻找头节点的下一个节点
	//DListNode* next = cur->next;

	删除节点
	//phead->next = next;
	//next->prev = phead;
	//free(cur);

	//Erase的复用
	ListErase(phead->next);
}

//双向链表的查找
DListNode* ListFind(DListNode* phead, DLDataType val)
{
	assert(phead);
	assert(phead->next != phead);

	//遍历链表查找
	DListNode* cur = phead->next;
	//尾节点的next指向phead
	while (cur != phead)
	{
		if (cur->val == val)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

//双向链表在pos位置之前插入节点
void ListInsert(DListNode* pos, DLDataType val)
{
	assert(pos);
	
	//创建节点
	DListNode* new_node = BuyListNode(val);

	//寻找pos位置的前一个节点
	DListNode* prev = pos->prev;
	
	//插入数据
	new_node->next = pos;
	pos->prev = new_node;
	new_node->prev = prev;
	prev->next = new_node;
}

//双向链表在pos位置删除节点
void ListErase(DListNode* pos)
{
	assert(pos);
	assert(pos->next != pos);//有节点可删
	
	//记录pos的前一个节点
	DListNode* prev = pos->prev;
	//记录pos的后一个节点
	DListNode* next = pos->next;

	//删除节点
	prev->next = next;
	next->prev = prev;
	free(pos);
}

//双向链表的销毁
void ListDestory(DListNode* phead)
{
	DListNode* cur = phead->next;
	//依次释放哨兵位以外的节点
	while (cur != phead)
	{
		DListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	//释放哨兵位
	free(phead);
}

三、单链表与双向链表

1.无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表。另外这种结构在笔试面试中出现很多。
2.带头双向循环链表：结构最复杂，但实现起来最简单。一般用于单独存储数据。相较于单链表，其在任意位置的插入与删除时间效率都为O(1)，效率远大于单链表。