当前位置： 首页 > article >正文

链表的分类以及双向链表的实现

article 2025/3/4 1:57:19

1.链表的分类

在这里插入图片描述

1.1单向链表与双向链表的区别

单向链表只能从头结点遍历到尾结点。
双向链表不仅能从头结点遍历到尾结点，还能从尾结点遍历到头结点。
在这里插入图片描述

1.2带头链表与不带头链表的区别

在这里插入图片描述

1.3循环链表与不循环链表的区别（也称为带环链表与不带环链表）

不循环链表中，尾结点的next指针的值为NULL
循环链表中，尾结点的next指针可以指向该链表中的任意一个结点，包括尾结点。
在这里插入图片描述

2.双向链表中需要注意的点

2.1：双向链表的全称为双向带头循环的链表，单向链表的全称为单向不带头不循环的链表。

在这里插入图片描述

2.2双向链表中结点的结构

typedef int DataType;
typedef struct ListNode
{
	DataType data;//存储DataType类型的数据
	struct ListNode* next;//存储后一个结点的地址
	struct ListNode* prev;//存储前一个结点的地址
}LN;

2.3区分单链表（单向不带头不循环链表）与双向链表（双向带头循环链表）为空表的情况

2.3.1： 若单链表为空表，表示单链表中没有结点（即没有存储有效数据），即指向第一个结点的指针为空指针
2.3.2：若双向链表为空表，并不是表示双向链表中没有结点，而是只有一个头结点，且头结点中存储一个无效数据，并且头结点中的两个指针均指向头结点（要满足循环）。故双向链表为空表时，并不是指链表中一个结点也没有，而是指链表中没有存储有效数据。

在这里插入图片描述

2.4常使用的两种链表

虽然链表的分类有很多，但是最常用的只有单链表(单向不带头不循环链表)与双向链表(双向带头循环链表)。

1.单链表：结构简单，一般不会用来存数据，实际中更多的是作为其他数据结构的子结构，如哈希桶、图的邻接表等等，另外单链表在笔试面试中考察的较多。

2.双向链表：结构复杂，一般用于单独存储数据，实际中使用的链表数据结构，通常都是双向链表。虽然双向链表的结构复杂，但是该结构的优势明显，另外该结构也容易实现。

2.5顺序表与单链表的比较

在这里插入图片描述

3.双向链表的实现

a.List.h文件

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int DataType;
//定义双向链表结点的结构
typedef struct ListNode
{
	DataType data;
	struct ListNode* next;//存储下一个结点的地址
	struct ListNode* prev;//存储上一个结点的地址
}ListNode;

//申请新结点的空间,并返回该空间的地址
ListNode* ListBuyNode(DataType x);

//双向链表的初始化(初始情况下，双向链表中只有一个头结点，不存储任何有效的数据)
void ListInit(ListNode** pphead);

//打印双向链表(打印存储的有效数据)
void ListPrint(ListNode* phead);


//向双向链表尾部插入结点
void ListPushBack(ListNode *phead, DataType x);//向双向链表尾部插入结点时，不会改变头结点的地址，因此传头结点的地址即可

//向双向链表头部插结点(注意:不是插在头结点之前，而是插在头结点后面。)
//因为头结点中存储的是无效数据，第一个存储有效数据的结点是头结点后面的结点
void ListPushFront(ListNode* phead, DataType x);//向双向链表的头部插入结点时，不会改变头结点的地址，因此传头结点的地址即可


//判断双向链表是否为空表
//若双向链表中只有一个头结点，头结点中没有存储有效数据，且头结点中的两个指针均指向头结点(要满足循环))，则双向链表为空表

bool ListEmpty(ListNode* phead);

//删除尾部的结点(删除尾部的结点时，头结点的地址不会发生变化，因此传头结点的地址即可)
void ListPopBack(ListNode* phead);

//删除第一个存储有效数据的结点(删除该结点时，头结点的地址不会变化，因此传头结点的地址即可)
//为什么不是删头结点呢？因为如果把头结点删除了，双向循环链表就不带头了，就不是双向循环链表了
void ListPopFront(ListNode* phead);

//查找存储数据为x的结点，返回该结点的地址
ListNode* ListFind(ListNode* phead, DataType x);

//删除指定的结点(pos指向的结点)
//头结点是不能删的，不然就不是双向链表了
void ListErase(ListNode * pos);

//在指定的结点(pos指向的结点)后插入结点
void ListInsert(ListNode* pos, DataType x);

//双向链表的销毁(包括头结点也要销毁)
void ListDestory(ListNode** pphead);//链表销毁后，头结点的地址就变成了NULL，因此要传指向头结点的指针的地址



/*
容易发现除了双向链表的初始化与销毁的形参是二级指针外，其余的函数的形参都是一级指针
那么能不能将初始化与销毁这两个函数的形参做一些修改呢？

答案是可以的，看下面修改后的函数
*/


//双向链表的初始化(直接申请一个头结点的空间，然后返回空间的地址)
ListNode* ListInit2();

//双向链表的销毁的第二种方法
void ListDestory2(ListNode* phead);

b.List.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//申请新结点的空间
ListNode* ListBuyNode(DataType x)
{
	ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
	assert(NewNode);
	NewNode->data = x;
	NewNode->next = NewNode->prev = NewNode;
	/*
	这种写法便于创建头结点，当双向链表为空表时，头结点中的两个指针均指向自己(链表满足循环)
	如果是下面这种写法，创建头结点时，链表无法循环，就不是双向链表了
	NewNode->next = NewNode->prev =NULL,
	*/
	return NewNode;
}

//双向链表的初始化(初始情况下，双向链表中只有一个头结点，不存储任何有效的数据)
void ListInit(ListNode** pphead)
{
	assert(pphead);//双向链表未初始化之前，链表中没有头结点，因此指向头结点的指针的值为NULL，但指向头结点的指针的地址不是NULL
	//pphead:指向头结点的指针的地址
    //*pphead:头结点的地址
	*pphead = ListBuyNode(INT_MAX);//用INT_MAX表示头结点中存储的是无效数据
}


//打印双向链表(打印存储的有效数据)
void ListPrint(ListNode* phead)
{
	assert(phead);//双向链表中，头结点的地址不可能是NULL
	if (phead->next == phead)//若双向链表为空表(只有一个头结点，头结点中存储的是无效数据，且头结点中的两个指针均指向头结点)
	{
		printf("双向链表为空表\n");
		return;
	}
	ListNode* pcur = phead->next;//pcur指向第一个存储有效数据的结点
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}



//向双向链表尾部插入结点
void ListPushBack(ListNode* phead, DataType x)
{
	assert(phead);//双向链表中，头结点的地址不可能是NULL
	//申请新结点的空间
	ListNode* NewNode = ListBuyNode(x);
	//先修改新结点中指针的指向
	NewNode->prev = phead->prev;
	NewNode->next = phead;
	//再修改原链表的尾结点中next指针的指向
	phead->prev->next = NewNode;
	//最后修改头结点中的prev指针的指向
	phead->prev = NewNode;
}

//向双向链表头部插结点(注意:不是插在头结点之前，而是插在头结点后面。)
void ListPushFront(ListNode* phead, DataType x)
{
	assert(phead);//双向链表中，头结点的地址不可能是NULL
	//申请新结点的空间
	ListNode* NewNode = ListBuyNode(x);
	//先修改新结点中指针的指向
	NewNode->next = phead->next;
	NewNode->prev = phead;
	//再改变原链表中第一个存储有效数据的结点中prev指针的指向
	phead->next->prev = NewNode;
	//最后改变头结点中next指针的指向
	phead->next = NewNode;
}

//判断双向链表是否为空表(若双向链表中只有一个头结点，头结点中没有存储有效数据，且头结点中的两个指针均指向头结点(要满足循环))
bool ListEmpty(ListNode* phead)
{
	assert(phead);//双向链表中，头结点的地址不可能是NULL
	return phead->next == phead;//若表达式为真(即双向链表是空表)，返回true,否则返回false
}



//删除尾部的结点
void ListPopBack(ListNode* phead)
{
	assert(phead);//双向链表中，头结点的地址不可能是NULL
	assert(!ListEmpty(phead));//若双向链表为空表则不能删除结点
	//删除结点时，会影响头结点的prev指针，以及尾结点的前一个结点的next指针

	ListNode* ptail = phead->prev;//ptail指向的是尾结点

	ListNode* prev = ptail->prev;//定义prev指针,指向尾结点的前一个结点
	//等号的左边的prev是该函数中是定义的变量，它的作用域是该函数；而右边的prev是结构体中成员变量（只有访问这个结构体时，才会用到prev），它的作用域是这个结构体。两个prev的作用域不同，因此两者不冲突。
	
	//先修改原链表中，尾结点的前一个结点的next指针
	prev->next = phead;
	//再修改头结点的prev指针
	phead->prev = prev;
	//最后释放原链表中尾结点的空间
	free(ptail);
	ptail = NULL;
}


//删除第一个存储有效数据的结点
void ListPopFront(ListNode* phead)
{
	assert(phead);//双向链表中，头结点的地址不可能是NULL
	assert(!ListEmpty(phead));//若双向链表为空表则不能删除结点
	//删除结点时，会影响头结点中的next指针，以及存储第一个有效数据的结点的后一个结点中的prev指针
	ListNode* first = phead->next;//first指向第一个存储有效数据的结点
	ListNode* Next = first->next;//Next指向存储第一个有效数据的结点的后一个结点

	//先修改存储第一个有效数据的结点的后一个结点中prev指针的指向
	Next->prev = phead;
	//再修改头结点中的next指针
	phead->next = Next;
	//最后释放原链表中存储第一个有效数据的结点的空间
	free(first);
	first = NULL;
}


//查找存储数据为x的结点，返回该结点的地址
ListNode* ListFind(ListNode* phead, DataType x)
{
	assert(phead);//双向链表中，头结点的地址不可能是NULL

	//从第一个存储有效数据的结点开始往后找
	ListNode* pcur = phead->next;//pcur指向第一个存储有效数据的结点
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//若将所有存储有效数据的结点都遍历了一遍后，依旧找不到存储x的结点，则返回NULL
	return NULL;
}

//删除指定的结点(pos指向的结点)
void ListErase(ListNode* pos)
{
	assert(pos);//pos指向的结点的地址不可能是NULL

	//删除结点时，会影响pos指向的结点的前一个结点中的next指针,
	//                  以及pos指向的后一个结点的prev指针

	//先修改pos指向的结点的前一个结点中的next指针
	pos->prev->next = pos->next;
	//再修改pos指向的后一个结点的prev指针
	pos->next->prev = pos->prev;
	//最后释放pos指向的结点的空间
	free(pos);
	pos = NULL;
}


//在指定的结点(pos指向的结点)后插入结点
void ListInsert(ListNode* pos, DataType x)
{
	assert(pos);//pos指向的结点的地址不可能是NULL
	//申请新结点的空间
	ListNode* NewNode = ListBuyNode(x);

	//插入结点时，会影响pos指向的结点的next指针，以及原链表中pos指向的结点的后一个结点的prev指针
	ListNode* Next = pos->next;//Next指向原链表中，pos指向的结点的下一个结点

	//先修改新结点中指针的指向
	NewNode->prev = pos;
	NewNode->next = Next;
	//再修改pos指向的结点的next指针
	pos->next = NewNode;
	//再修改原链表中pos指向的结点的后一个结点的prev指针
	Next->prev = NewNode;
}

//双向链表的销毁(包括头结点也要销毁)
void ListDestory(ListNode** pphead)
{
	//pphead表示指向头结点的指针的地址
	//*pphead表示头结点的地址
	
	//若pphead==NULL，则*pphead就无法找到头结点的地址了
	//双向链表中，头结点的地址不可能为NULL
	assert(pphead && *pphead);

	ListNode* pcur = (*pphead)->next;//pcur指向第一个存储有效数据的结点
	//先回收存储有效数据的结点的空间
	while (pcur != *pphead)
	{
		ListNode* Next = pcur->next;//Next指向pcur指向的结点的下一个结点
		free(pcur);
		pcur = Next;
	}
	//再回收头结点的空间
	free(*pphead);
	*pphead = pcur = NULL;
}

//双向链表的初始化(直接申请一个头结点的空间，然后返回空间的地址)
ListNode* ListInit2()
{
	ListNode* phead = ListBuyNode(INT_MAX);//INT_MAX表示头结点中存储的是无效数据
	assert(phead);
	return phead;
}


//双向链表的销毁的第二种方法
void ListDestory2(ListNode* phead)
{
	assert(phead);//双向链表中，头结点的地址不可能为NULL

	ListNode* pcur = phead->next;//pcur指向第一个存储有效数据的结点
	//先回收存储有效数据的结点的空间
	while (pcur != phead)
	{
		ListNode* Next = pcur->next;
		free(pcur);
		pcur = Next;
	}
	//再回收头结点的空间
	free(phead);
	/*
	头结点的空间虽然被回收了，但由于形参接收的是实参的值，不是实参的地址，形参的改变无法影响实参
	因此实参(plist)依然是指向头结点，plist变成了野指针，需要手动将plist置为NULL
	*/
	pcur = phead = NULL;
}

test.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//测试双向链表的初始化
void test1(ListNode **pplist)
{
	ListInit(pplist);
}

//测试向双向链表中尾插结点
void test2(ListNode *phead)
{
	ListPushBack(phead, 1);
	ListPushBack(phead, 2);
	ListPushBack(phead, 3);
	ListPushBack(phead, 4);
	ListPrint(phead);
}

//测试向双向链表中头插结点
void test3(ListNode *phead)
{
	ListPushFront(phead, 4);
	ListPushFront(phead, 3);
	ListPushFront(phead, 2);
	ListPushFront(phead, 1);
	ListPrint(phead);
}

//测试删除尾结点
void test4(ListNode* phead)
{
	ListPushBack(phead, 1);
	ListPushBack(phead, 2);
	ListPrint(phead);//1->2->
	ListPopBack(phead);
	ListPrint(phead);//1->
	ListPopBack(phead);
	ListPrint(phead);//空表
	//ListPopBack(phead);空表不能删除结点，会报错
}

//测试删除第一个存储有效数据的结点
void test5(ListNode* phead)
{
	ListPushBack(phead, 1);
	ListPushBack(phead, 2);
	ListPrint(phead);//1->2->
	ListPopFront(phead);
	ListPrint(phead);//2->
	ListPopFront(phead);
	ListPrint(phead);//此时双向链表为空表
}

//测试查找存储数据为x的结点
void test6(ListNode *phead)
{
	ListPushBack(phead, 1);
	ListPushBack(phead, 2);
	ListPushBack(phead, 3);
	ListPushBack(phead, 4);
	ListPrint(phead);//1->2->3->4->
	ListNode* find = ListFind(phead, 2);
	if (find != NULL)
	{
		printf("找到了\n");
	}
	else
	{
		printf("找不到\n");
	}

}


//测试删除指定的结点(pos指向的结点)
void test7(ListNode* phead)
{
	ListPushBack(phead, 1);
	ListPushBack(phead, 2);
	ListPushBack(phead, 3);
	ListPushBack(phead, 4);
	ListPrint(phead);//1->2->3->4->
	ListNode* find = ListFind(phead, 1);
	ListErase(find);
	ListPrint(phead);//2->3->4->




}


//测试在指定的结点(pos指向的结点)后插入结点
void test8(ListNode* phead)
{
	ListPushBack(phead, 1);
	ListPushBack(phead, 2);
	ListPushBack(phead, 3);
	ListPushBack(phead, 4);
	ListPrint(phead);//1->2->3->4->
	ListNode* find = ListFind(phead, 4);
	ListInsert(find, 5);//1->2->3->4->5->
	ListPrint(phead);
}


//测试摧毁双向链表
void test9(ListNode** pphead)
{
	ListPushBack(*pphead, 1);
	ListPushBack(*pphead, 2);
	ListPrint(*pphead);//1->2->
	ListDestory(pphead);


}


int main()
{
	ListNode * plist = NULL;//plist表示指向头结点的指针

	//测试双向链表的初始化
	test1(&plist);

	//测试向双向链表中尾插结点
	//test2(plist);
	
	//测试向双向链表中头插结点
	//test3(plist);

	//测试删除尾结点
	//test4(plist);

	//测试删除第一个存储有效数据的结点
	//test5(plist);

	//测试查找存储数据为x的结点
	//test6(plist);

	//测试删除指定的结点(pos指向的结点)
	//test7(plist);

	//测试在指定的结点(pos指向的结点)后插入结点
	//test8(plist);

	//测试销毁双向链表
	//test9(&plist);


	//测试销毁双向链表的第二种方法
	ListDestory2(plist);
	//虽然链表被销毁了，但是plist依然是指向原来链表中的头结点，变成了野指针，需要手动将plist置为NULL
	plist = NULL;


	return 0;
}

http://www.kler.cn/a/421209.html

相关文章：

  • Unity类银河战士恶魔城学习总结（P157 Audio Time Limter ---P158 Area Sound范围音效）
  • 【微服务】Docker
  • ELK的Filebeat
  • Mac安装MINIO服务器实现本地上传和下载服务
  • springboot+mybatis对接使用postgresql中PostGIS地图坐标扩展类型字段
  • 认识Java数据类型和变量
  • Flutter：常见的页面布局：上边内容可滚动，底部固定一个按钮
  • 网工日记：VRRP-虚拟路由冗余协议
  • pyqt6简单应用
  • 健康养生生活
  • MagicAnimate 技术浅析（一）
  • 常用端口号总结
  • Python 网络爬虫的高级应用：反爬绕过与爬取多样化数据
  • python分析wireshark文件
  • QT：核心机制
  • 量化交易系统开发-实时行情自动化交易-8.3.开拓者TBQuant平台
  • 精通 Python 网络安全（二）
  • mysql数据库之三范式
  • week 10 - Database: Normalisation
  • win11 多任务 贴靠 bug：左右两窗口贴靠时拖动中间的对齐条后，资源管理器有概率卡死