【数据结构初阶】千字文章带你征服 “ 双向链表 ”(附源码)

hi，bro！又见面啦

目录

前言：

一、链表的分类

二、双向链表

1、  概念与结构

2、  双向链表的实现

2.1  定义双向链表的结构

2.2  初始化

2.3  尾插

2.4  头插

2.5  打印

2.6  尾删

2.7  头删

2.8  查找

2.9  在pos结点之后插入结点

2.10  删除指定位置结点

2.11  销毁

2.12  销毁2

2.13  初始化2

3、源码

List.h

List.c 

test.c 

三、顺序表和链表的比较

Bye Bye Bye ————————

---

前言：

前面我们学习了单链表，单链表是链表的一种，今天我们即将要学习的双向链表也是其中之一。我们前面没有具体介绍链表的分类，所以在学习双向链表之前，先了解下链表的分类。

一、链表的分类

链表的结构多样，有下面8种链表结构（2×2×2）： 

链表说明：

何为循环：尾结点的next指针不为NULL

链表结构虽多，我们常用的就两种结构，单链表和双向带头循环链表

• 无头单向非循环链表（单链表）：结构简单，一般不用来单独存储数据。实际上更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
• 带头双向循环链表（双向链表）：结构最复杂，一般用在单独存储数据，实际中使用的链表数据结构，都是带头双向循环链表。虽然这个结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。
• 在带头链表里面，除了头结点（哨兵位），其他结点都存储有效的数据。

二、双向链表

1、  概念与结构

带头双向循环链表

双向链表的结点结构：数据 + 指向后一个结点的指针 + 指向前一个节点的指针 

struct ListNode
{
    int data;
    struct ListNode* next;
    struct ListNode* prev;
}

头结点的prev指针指向尾结点，尾结点的next指针指向头结点，就这样实现了循环。 

【注意】 带头链表的头结点实际为 哨兵位 ，哨兵位结点不存储任何有效数据，只是在这里放哨占位子的。而前面单链表里面的头结点并不表示真的表示有头结点，而是为了表示方便，这种表述是不规范的。单链表里面的第一个结点并非真的头结点。

2、  双向链表的实现

2.1  定义双向链表的结构

//定义双向链表的结构
typedef int LTDataType ;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;

2.2  初始化

//创建新结点
LTNode* LTBuyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc file!");
		exit(1);
	}
	newnode->data = x;
	//等于自身,实现循环
	newnode->next = newnode->prev = newnode;

	return newnode;

}

//初始化
void LTInit(LTNode** pphead)
{
	//创建新结点
	*pphead = LTBuyNode(-1);
}

双向链表为空：表示只有一个哨兵位。

2.3  尾插

第一个结点：第一个有效的结点，里面存储有效的数据。

哨兵位：头结点。

//插入
//第一个参数传一级还是二级，要看phead指向的结点会不会发生改变
//如果发生改变，那么phead的改变要影响实参，传二级
//如果不发生改变，那么phead不会影响实参，传一级
//phead指向的结点是哨兵位，不会发生改变，故传一级

//尾插
void LTPushBack(LTNode* phead,LTDataType x)
{
	assert(phead);

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

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

}

2.4  头插

//头插
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 = newnode;
}

2.5  打印

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

	//从第一个有效的结点开始打印
	LTNode* pcur = phead->next;
	while (pcur!=phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

2.6  尾删

//判空
bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}
//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	//在尾删之前要判空
	assert(!LTEmpty(phead));

	LTNode* del = phead->prev;
	LTNode* prev = del->prev;
    
    //phead del(phead->prev) prev(del->prev)
	phead->prev = prev;
	prev->next = phead;

	free(del);
	del = NULL;
}

2.7  头删

//头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	//在头删之前要判空
	assert(!LTEmpty(phead));

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

	free(del);
	del = NULL;
}

2.8  查找

//查找
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;
}

2.9  在pos结点之后插入结点

//在pos结点之后插入数据
void LTInsert(LTNode* phead, LTNode* pos,LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(100);

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

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

}

2.10  删除指定位置结点

//删除指定位置结点
void LTErase(LTNode* phead, LTNode* pos)
{
	assert(phead);

	//pos->prev pos pos->next
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;

	free(pos);
	pos = NULL;

}

为了保持接口的一致性，优化接口都为一级指针，见下：

2.11  销毁

//销毁
void LTDesTroy(LTNode** pphead)
{
	assert(pphead && *pphead);

	LTNode* pcur = (*pphead)->next;
	while (pcur != *pphead)
	{
		LTNode* Next = pcur->next;
		free(pcur);
		pcur = Next;
	}

	//销毁哨兵位结点
	free(*pphead);
	*pphead = NULL;
	pcur = NULL;
}

2.12  销毁2

//销毁2
void LTDesTroy2(LTNode* phead)  //传一级指针，需要手动将plist置为空
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur!=phead)
	{		
		LTNode* Next = pcur->next;
		free(pcur);
		pcur = Next;
	}
	free(phead);
	phead = NULL;
	pcur = NULL;

}

2.13  初始化2

用返回值的方式实现

//初始化2
LTNode* LTInit2()
{
	LTNode* phead = LTBuyNode(-1);
	return phead;
}

3、源码

List.h

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

//定义双向链表的结构
typedef int LTDataType ;
typedef struct ListNode
{
	int data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;

//初始化
void LTInit(LTNode** pphead);

//尾插
void LTPushBack(LTNode* phead,LTDataType x);

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

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

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

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

//查找
LTNode* LTFind(LTNode* phead,LTDataType x);

//在pos结点之后插入数据
void LTInsert(LTNode* phead,LTNode* pos,LTDataType x);

//删除指定位置结点
void LTErase(LTNode* phead, LTNode* pos);

//销毁
void LTDesTroy(LTNode** pphead);

//销毁
void LTDesTroy2(LTNode* phead);

//初始化2
LTNode* LTInit2();

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 file!");
		exit(1);
	}
	newnode->data = x;
	//等于自身,实现循环
	newnode->next = newnode->prev = newnode;

	return newnode;

}

//初始化
void LTInit(LTNode** pphead)
{
	//创建新结点
	*pphead = LTBuyNode(-1);
}

//插入
//第一个参数传一级还是二级，要看phead指向的结点会不会发生改变
//如果发生改变，那么phead的改变要影响实参，传二级
//如果不发生改变，那么phead不会影响实参，传一级
//phead指向的结点是哨兵位，不会发生改变，故传一级

//尾插
void LTPushBack(LTNode* phead,LTDataType x)
{
	assert(phead);

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

	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 = newnode;
}

//打印
void LTPrint(LTNode* phead)
{
	assert(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(phead);
	//在尾删之前要判空
	assert(!LTEmpty(phead));

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

	phead->prev = prev;
	prev->next = phead;

	free(del);
	del = NULL;
}

//头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	//在头删之前要判空
	assert(!LTEmpty(phead));

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

	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 LTInsert(LTNode* phead, LTNode* pos,LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(100);

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

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

}

//删除指定位置结点
void LTErase(LTNode* phead, LTNode* pos)
{
	assert(phead);

	//pos->prev pos pos->next
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;

	free(pos);
	pos = NULL;

}

//销毁
void LTDesTroy(LTNode** pphead)
{
	assert(pphead && *pphead);

	LTNode* pcur = (*pphead)->next;
	while (pcur != *pphead)
	{
		LTNode* Next = pcur->next;
		free(pcur);
		pcur = Next;
	}

	//销毁哨兵位结点
	free(*pphead);
	*pphead = NULL;
	pcur = NULL;
}

//销毁
void LTDesTroy2(LTNode* phead)  //传一级指针，需要手动将plist置为空
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur!=phead)
	{		
		LTNode* Next = pcur->next;
		free(pcur);
		pcur = Next;
	}
	free(phead);
	phead = NULL;
	pcur = NULL;

}

//初始化2
LTNode* LTInit2()
{
	LTNode* phead = LTBuyNode(-1);
	return phead;
}

test.c 

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"

void ListTest01()
{
	LTNode* plist = NULL;
	//双向链表头结点不能为空，要初始化
	LTInit(&plist);

	LTNode* plist = LTInit2();

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

	LTPushFront(plist, 6);
	LTPrint(plist);
	
	LTPopBack(plist);
	LTPrint(plist);

	LTPopFront(plist);
	LTPrint(plist);

	LTNode* pos = LTFind(plist, 3);
	if (pos == NULL)
	{
		printf("没有找到\n");
	}
	else
	{
		printf("找到了\n");
	}

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

	LTErase(plist,pos);
	LTPrint(plist);

	LTDesTroy(&plist);

	//此时plist为野指针，虽然保存的有地址，但其中的地址已被释放
	LTDesTroy2(plist);
	plist = NULL;
}


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

三、顺序表和链表的比较

不同点	顺序表	链表（单链表）
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	O（1）	O（N）
任意位置插入或者删除数据	可能需要搬移元素，效率低	只需改变指针指向
插入	动态顺序表，空间不够时需要扩容，可能会发生空间浪费	没有容量的概念，按需申请释放，不存在空间浪费
应用场景	元素高效存储+频繁访问	任意位置高效插入和删除

今天双向链表的学习就结束了，休息一下吧。

---

完——

Bye Bye Bye ————————

Bye Bye Bye_*NSYNC_高音质在线试听_Bye Bye Bye歌词|歌曲下载_酷狗音乐酷狗音乐为您提供由*NSYNC演唱的高清音质无损Bye Bye Byemp3在线听,听Bye Bye Bye,只来酷狗音乐!https://t4.kugou.com/song.html?id=dzeLrbfCPV2

至此，结束——

我是云边有个稻草人

期待与你的下一次相遇 。。。。。。