线性表之链表一

Hello大家好！ 很高兴与大家见面！ 给生活添点快乐，开始今天的编程之路。

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

2结构：

这里我们链表的结构就相当于我们的火车一样，由一个个节点组成，如果要向链表增/删节点只需要将⽕⻋⾥的某节⻋厢去掉/加上，不会影响其他⻋厢，每节⻋厢都是独⽴存在的。这里我们把火车车厢想成一个个结点，所以我们要定义链表就相当于定义结点便可以。

2.1结点

与顺序表不同的是，链表⾥的每节"⻋厢"都是独⽴申请下来的（即需要插⼊数据时才去申请⼀块结点的空间），我们称之为“节点/结点”。

我们观察上图链表中的每个节点可以知道每个节点由存储的数据和一个地址变量组成而这个地址与节点的地址相同所以这是一个二级指针。

所以节点的组成主要有两个部分：

结点的组成主要有两个部分：当前结点要保存的数据和保存下⼀个结点的地址（指针变量）。

图中指针变量 plist保存的是第⼀个结点的地址，我们称plist此时“指向”第⼀个结点（头节点），头节点很重要不管后续我们对链表进行什么操作我们都要记住头节点的位置，只有我们知道头节点才可以通过其中的指针变量才可以对后面的节点进行操作，所以我们要记住头节点位置。

3链表的性质

1、链式机构在逻辑上是连续的，在物理结构上不⼀定连续

2、结点⼀般是从堆上申请的

3、从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续

4链表结构的实现

链表由节点组成，而每个节点由要保存的数据和保存下⼀个结点的地址组成，要满足这一结构，我们可以使用结构体。

5 链表的分类

【注意这里的带头不带头是指链表的第一个节点是否为有有效节点即第一个节点是否存储真实数据如我们的单向链表第一个节点就存储真实数据所以单向链表不带头（无头节点我们这里把第一个节点称为头节点只是为了方便理解）而双向链表的第一个节点就没有存储真实数据只是起到哨兵位的作用所以双向链表带头（有头节点）】

5.1单向/双向带头/不带头/循环/不循环分别指什么

二 单链表(不带头单向不循环链表）1单链表结构：

2手动实现单链表

3单链表中涉及到的方法：【打印单链表/向操作系统申请一个新节点/尾插/头插/尾删/头删/查找/在指定位置之前插入数据/在指定位置之后插入数据/删除指定位置结点/销毁链表】

这里我们一般用到三个文件一个头文件（用于函数的声明和定义）和两个源文件（分别用于函数的实现和测试）

Slist.h

Slist.c

三 双向链表(带头双向循环链表）1结构

2实现双向链表及其涉及的操作

LIst.h

List.c

四 顺序表与链表的分析不同点

顺序表

链表（单链表）

存储空间上

物理上⼀定连续（底层是数组）

逻辑上连续，但物理上不⼀定连续

随机访问

⽀持O(1)

不⽀持：O(N)

任意位置插⼊或者删除元素

可能需要搬移元素，效率低O(N)

尾部:O(1)

头部/中间位置:O(N)

只需修改指针指向

在指定位置之前插入数据O(N)

在指定位置之后插入数据O(1)

插⼊

动态顺序表，空间不够时需要扩容和空间浪费（呈倍数增加：2倍）

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

应⽤场景

元素⾼效存储+频繁访问

任意位置⾼效插⼊和删除

本篇文章就到此结束，欢迎大家订阅我的专栏，欢迎大家指正，希望有所能帮到读者更好了线性表之链表相关知识 ，觉得有帮助的还请三联支持一下~后续会不断更新C/C++相关知识，我们下期再见。