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

二、双向链表

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

至此，结束——

我是云边有个稻草人

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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/1014443

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

前言：

一、链表的分类