admin管理员组

文章数量:1794759

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

前言：

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

一、链表的分类

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

链表说明：

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

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

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

二、双向链表

1、 概念与结构

带头双向循环链表

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

代码语言：javascript代码运行次数：0运行复制
struct ListNode
{
    int data;
    struct ListNode* next;
    struct ListNode* prev;
}

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

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

2、 双向链表的实现

2.1 定义双向链表的结构
代码语言：javascript代码运行次数：0运行复制
//定义双向链表的结构
typedef int LTDataType ;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;
2.2 初始化
代码语言：javascript代码运行次数：0运行复制
//创建新结点
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 尾插

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

哨兵位：头结点。

代码语言：javascript代码运行次数：0运行复制
//插入
//第一个参数传一级还是二级，要看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 头插
代码语言：javascript代码运行次数：0运行复制
//头插
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 打印
代码语言：javascript代码运行次数：0运行复制
//打印
void LTPrint(LTNode* phead)
{
	assert(phead);

	//从第一个有效的结点开始打印
	LTNode* pcur = phead->next;
	while (pcur!=phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}
2.6 尾删
代码语言：javascript代码运行次数：0运行复制
//判空
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 头删
代码语言：javascript代码运行次数：0运行复制
//头删
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 查找
代码语言：javascript代码运行次数：0运行复制
//查找
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结点之后插入结点
代码语言：javascript代码运行次数：0运行复制
//在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 删除指定位置结点
代码语言：javascript代码运行次数：0运行复制
//删除指定位置结点
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 销毁
代码语言：javascript代码运行次数：0运行复制
//销毁
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
代码语言：javascript代码运行次数：0运行复制
//销毁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

用返回值的方式实现

代码语言：javascript代码运行次数：0运行复制
//初始化2
LTNode* LTInit2()
{
	LTNode* phead = LTBuyNode(-1);
	return phead;
}

3、源码

List.h
代码语言：javascript代码运行次数：0运行复制
#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
代码语言：javascript代码运行次数：0运行复制
#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
代码语言：javascript代码运行次数：0运行复制
#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）

任意位置插入或者删除数据

可能需要搬移元素，效率低

只需改变指针指向

插入

动态顺序表，空间不够时需要扩容，可能会发生空间浪费

没有容量的概念，按需申请释放，不存在空间浪费

应用场景

元素高效存储+频繁访问

任意位置高效插入和删除

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

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-07-31，如有侵权请联系 cloudcommunity@tencent 删除数据源码指针数据结构链表

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

版权声明：本文标题：【数据结构初阶】千字文章带你征服 “ 双向链表 ”(附源码) 内容由林淑君副主任自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.xiehuijuan.com/baike/1754689938a1705245.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。