目录

 

一：前言

（1）什么是双链表

（2）双向带头循环链表的好处

二：双向链表实现

（1）创建源文件和头文件

（2）生成一个新结点

（3）链表初始化

（4）链表的打印

（5）尾部插入

（6）尾部删除

（7）头部插入

（8）头部删除

（9）查找

（10）指定插入

（11）指定删除

（12）小优化和最终代码

😉小优化

🧐最终代码

三：小结

---

 

一：前言

上次我们学习了怎么实现单链表，这一次我们将以单链表为基础实现双链表。

附上单链表链接：http://t.csdn.cn/G7z4m

（1）什么是双链表

 

🤓我们先看下面这个结构体

 相较与单链表，双链表多定义了一个prev(prevent)指针用来记录该结点的前一个结点，这样我们就既可以找前又可以找后了，双链表有很多种结构，有带哨兵不循环，带哨兵循环或者不带哨兵不循环以及不带哨兵循环。

 

本文选择的是带哨兵循环(双向带头循环)

（2）双向带头循环链表的好处

我们先看一下双向带头循环链表的大致结构：

 

【1】我们可以很清楚的看到双向带头循环链表的一大优势:由哨兵位直接找到尾部结点。

【2】由于哨兵位的存在，我们不必考虑链入第一个结点这样的特殊情况。

【3】代码实用性强，实际运用最多。

 

 

二：双向链表实现

（1）创建源文件和头文件

🤓头文件：BoubleList.h用来包含一些必须的头文件，定义结构体，声明相关函数。

🤓源文件：

【1】BoubleList.c用来实现具体的功能。

【2】text.c用来测试接口函数。

（2）生成一个新结点

后续的插入，初始化我们都需要生成一个新的结点，为了让代码更加简洁美观，我们把这个部分单独封装成函数BuyListNode()，函数返回值为新结点地址。

代码：

 

（3）链表初始化

🤓初始化的要点：

【1】要申请一个哨兵位的结点。

【2】返回申请的哨兵位的地址。(也可以通过传入二级指针的方式进行初始化，形参和实参的关系在单链表一文已经讲过，这里不再赘述)

【3】这个时候只有一个结点，我们让这个结点自己成环。

 

代码：

（4）链表的打印

🤓与单链表打印的不同：

【1】链表是循环的，没法以空指针位结束条件。

【2】链表的第一个结点（哨兵位）存储的是无效数据，我们要忽略哨兵结点。

综上所述我们可以以第一个有效结点为起始位置，以走到哨兵位为结束条件。

代码：

图解：

（5）尾部插入

🤓尾插的基本思路：

【1】生成新结点。

【2】尾结点的next指向新结点。

【3】新结点的prev指向原尾结点，next指向头结点。

【4】头结点的prev指向新结点。

代码：

 

（6）尾部删除

🤓尾删的基本思路：

【1】记录尾部的前一个结点。

【2】头指针的prev指向新的尾结点。

【3】新的尾结点的next指向头结点。

【4】注意不要删除掉头结点。

代码：

 

（7）头部插入

🤓头插的基本思路：

【1】记录原有效头的结点。

【2】原有效头的prev指向新有效头。

【3】新有效头的prev指向哨兵位，next指向原有效头。

【4】哨兵位的next指向新有效头。

代码：

 

（8）头部删除

🤓头删的基本思路：

【1】记录要删除的原有效头结点。

【2】新有效头结点的prev指向哨兵位。

【3】哨兵位的next指向新有效头结点。

【4】注意不要删除哨兵位。

代码：

 

（9）查找

🤓查找的基本思路：

【1】和打印类似，从有效头开始遍历，到哨兵结束。

【2】返回对应结点的地址。

代码：

 

（10）指定插入

🤓指定插入的基本思路：

【1】先用查找找到节点位置pos。

【2】记录后一个结点。

【3】新结点的next指向pos的后一个结点，新结点的prev指向pos

【4】后一个结点的prev指向新结点。

【5】pos结点的next指向新结点。

代码：

 

（11）指定删除

🤓指定删除的基本思路：

【1】记录要删除的结点的后一个结点和前一个结点。

【2】后一个结点的prev指向待删除结点的前一个结点。

【3】前一个结点的next指向待删除结点的后一个结点。

【4】注意不要删除掉哨兵位。

代码：

 

（12）小优化和最终代码

😉小优化

前面我们已经实现了指定插入和指定删除，而头尾删，头尾插不过是指定删除和指定插入的特殊情况而已，所有我们可以在这些函数中复用指定插入和删除，使代码更加简洁。

代码：

 

 

 

 

🧐最终代码

BoubleList.

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
//重定义，方便更改存储数据的类型
typedef int LTDataType;
typedef struct ListNode {
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}LT;
//申请新结点
LT* BuyListNode();
//链表初始化
LT* ListInit();
//打印链表
LT* ListPrint(LT* phead);
//尾部插入
void ListPushBack(LT* phead, LTDataType x);
//尾部删除
void LsitPopBack(LT* phead);
//头部插入
void ListPushFront(LT* phead, LTDataType x);
//头部删除
void ListPopFront(LT* phead);
//查找
LT* ListPopFind(LT* phead, LTDataType x);
//指定插入
void ListInsert(LT* phead, LT* pos, LTDataType x);
//指定删除
void ListErase(LT* phead, LT* pos);

BoubleList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "BoubleList.h"
//申请新结点
LT* BuyListNode()
{
	LT* newNode = (LT*)malloc(sizeof(LT));
	//新结点的prev，next最好置空
	newNode->next = NULL;
	newNode->prev = NULL;
	//返回新结点
	return newNode;
}

//初始化
LT* ListInit( )
{
	LT* phead = NULL;
	//生成哨兵结点
	phead = BuyListNode();
	//只有一个结点，这个结点自己成环
	phead->next = phead;
	phead->prev = phead;
	//返回头结点
	return phead;
}

//打印
LT* ListPrint(LT* phead)
{
	//如果未初始化，报错
	assert(phead != NULL);
	//从有效头结点开始走，一直到哨兵位结束
	LT* cur = phead->next;
	while (cur != phead)
	{
		//打印
		printf("%d ", cur->data);
		//迭代
		cur = cur->next;
	}
	printf("NULL");
	printf("\n");
}


//尾插
void ListPushBack(LT* phead,LTDataType x)
{
	//如果未初始化，报错
	assert(phead != NULL);
	//复用指定插入
    ListInsert(phead, phead->prev, x);
}


//尾部删除
void LsitPopBack(LT* phead)
{
	//如果未初始化，报错
	assert(phead != NULL);
	//不能删除哨兵结点
	assert(phead != phead->prev);
	//复用指定删除
	ListErase(phead, phead->prev);
}




//头部插入
void ListPushFront(LT* phead,LTDataType x)
{
	//如果未初始化，报错
	assert(phead != NULL);
	//复用指定插入
	ListInsert(phead, phead, x);
}

//头部删除
void ListPopFront(LT* phead)
{
	//如果未初始化，报错
	assert(phead != NULL);
	//不能删除哨兵位
	assert(phead->next != phead);
	//复用指定删除
	ListErase(phead, phead->next);
}

//查找，返回结点位置
LT* ListPopFind(LT* phead, LTDataType x)
{
	//如果未初始化，报错
	assert(phead != NULL);
	//和打印一样从第一个有效结点开始遍历
	LT* cur = phead->next;
	while (cur != phead)
	{
		//查找到返回结点位置
		if (cur->data == x)
			return cur;
		//迭代
		cur = cur->next;
	}
	//查找失败，返回null
	return NULL;
}


//指定插入（后）
void ListInsert(LT* phead, LT* pos,LTDataType x)
{
	//如果未初始化，报错
	assert(phead != NULL);
	//生成新结点
	LT* newnode = BuyListNode();
	//记录后一个结点
	LT* beforenode = pos->next;
	//新结点的next指向pos的后一个结点
	newnode->next = beforenode;
	//新结点的prev指向pos
	newnode->prev = pos;
	//后一个结点的prev指向新结点
	beforenode->prev = newnode;
	//pos结点的next指向新结点
	pos->next = newnode;
	//存储数据
	newnode->data = x;
}

//指定删除
void ListErase(LT* phead, LT* pos)
{
	//如果未初始化，报错
	assert(phead != NULL);
	//不能删除哨兵
	assert(pos != phead);
	//记录要删除的结点的后一个结点
	LT* beforepos = pos->next;
	//记录待删除结点的前一个结点
	LT* aheadpos = pos->prev;
	//后一个结点的prev指向待删除结点的前一个结点
	beforepos->prev = aheadpos;
	//前一个结点的next指向待删除结点的后一个结点
	aheadpos->next = beforepos;
	//释放结点
	free(pos);
}

text.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "BoubleList.h"
//测试1
void text1()
{
	//初始化
	 LT* SL=ListInit();
	 //尾部插入
	 ListPushBack(SL, 5);
	 ListPushBack(SL, 8);
	 ListPushBack(SL, 10);
	 //打印
	 ListPrint(SL);
	 //头部插入
	 ListPushFront(SL, 8);
	 ListPushFront(SL, 889);
	 //尾部删除
	 LsitPopBack(SL);
	 //打印
	 ListPrint(SL);
	 //头部删除
	 ListPopFront(SL);
	 ListPopFront(SL);
	 ListPopFront(SL);
	 //指定插入
	 ListInsert(SL, ListPopFind(SL,8), 56);
	 ListPushBack(SL, 100);
	 ListPrint(SL);
	 ListErase(SL, ListPopFind(SL, 100));
	 ListPrint(SL);
}

void text2()
{
	//初始化
	LT* SL = ListInit();
	ListPushFront(SL, 8);
	ListPushFront(SL, 889);
	ListPushBack(SL, 5);
	ListPushBack(SL, 8);
	ListPushFront(SL, 800);
	LsitPopBack(SL);
	ListPrint(SL);

}

int main()
{
	text1();
	//text2();
	return 0;
}

三：小结

【1】与单链表相比，双向带头循环链表的结构更复杂，但是实用性更强。

【2】单链表结构一般不会单独用来存储数据，更多的是作为其它结构的子结构。

【3】正因单链表的不完美，所以能够更好考验水平。下一次我们会进行链表OJ题目的讲解，其中大部分的题目都是通过巧妙的方式弥补单链表的缺点。