线性表中的链表

发布于：2022-11-15 ⋅ 阅读:(597) ⋅ 点赞:(0)

目录

前言
链表的概念及结构
链表的分类
链表的实现

前言

上一篇博客简单介绍了动态顺序表，让我们对动态顺序表有了一定的了解。但我们也发现动态顺序表的一些劣势，增容一般是按2倍的方式增长，很容易造成空间的巨大浪费。在增容过程中可能还会出现拷贝原有数据，释放旧空间后再开辟新空间的情况，也会造成不小的空间损耗和时间损耗。
所以针对这些问题我们就希望建立了一种新的表格方式，随时需要增加多少空间就增加多少，不需要哪一部分就删除哪一部分的新的序表模型------链表。

链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

在这里插入图片描述

链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
在这里插入图片描述

链表的实现

我们主要实现最常见的两种链表：无头单向非循环链表和带头双向循环链表

1.无头单向非循环链表

链表的主要接口

在这里插入图片描述

链表节点的申请

在这里插入图片描述

创建一个链表

在这里插入图片描述

打印单链表

在这里插入图片描述

单链表尾插

在这里插入图片描述

单链表尾删

在这里插入图片描述

单链表头插

在这里插入图片描述

单链表头删

在这里插入图片描述

单链表查找

在这里插入图片描述

单链表pos位置后插入x

在这里插入图片描述

单链表在指定位置pos前插入

在这里插入图片描述

单链表删除pos位置之后的元素

在这里插入图片描述

单链表删除指定pos位置的元素

在这里插入图片描述

销毁链表

在这里插入图片描述

2.带头双向循环链表

链表的主要接口

在这里插入图片描述

创建一个节点

在这里插入图片描述

链表初始化

在这里插入图片描述

删除链表

在这里插入图片描述

打印链表数据

在这里插入图片描述

尾插

在这里插入图片描述

尾删

在这里插入图片描述

头插

在这里插入图片描述

头删

在这里插入图片描述

寻找某一元素的地址

在这里插入图片描述

在指定pos位置前插入元素

在这里插入图片描述

删除指定pos位置的元素

在这里插入图片描述

查询链表元素个数

在这里插入图片描述

检查链表是否为空

在这里插入图片描述

总结

本篇文章主要介绍了两种主要链表和他们的实现，代码量看其多，实则内容相对简单，大家可以根据需求阅读。