数据结构中静态链表的关键技术点

什么是静态链表

在我公众号上一篇文章中实现了单链表的基本操作，创建单链表的过程就是一个动态生成链表的过程，即从"空表"的初始状态起，依次建立各元素结点，并逐个插入链表中。

而静态链表就是单链表和数组的结合。

首先我们让数组的元素都是由两个数据域组成，data 和 cursor。也就是说数组的每个下标都对应一个 data 和 cursor。数据域 data,用来存放数据元素，也就是通常我们要处理的数据；而 cursor 相当于单链表中的 next 指针，存放该元素的后继在数组中的下标，我们把 cursor 叫做游标。

这种用数组描述的链表叫做静态链表。

静态链表的三个核心

结点的两个属性：实际有用的数据 data + 存储数据的数组单元下标值 cursor

备用链表：备用链表是静态链表中删除元素和未被使用到的数组元素

首尾特殊元素：数组的第一个元素不存放数据信息，其中 cursor 存放备用链表中第一个结点的下标值；数组的最后一个元素也不存放数据信息，其中 cursor 存放首结点的下标

静态链表的插入和删除的基本思想插入

假设插入的位置为 i, 结点为 element

判断插入位置是否合理，不合理则返回。

如果合理则插入时先要从备用链表中申请一个数组单元用于存放结点

找到数组中 i-1 个元素的位置，因为这个元素的游标 cursor 存放了 i 元素的数组下标

将插入的结点插入到申请的数组元素位置上，cursor 值为 i-1 元素的 cursor

将 i-1 元素的 cursor 更新为新的结点的位置。 核心代码如下:

删除

假设插入的位置为 i

如果删除的位置不合理则直接返回

如果合理仍然需要找到链表第 i - 1 个元素的数组下标

将 i-1 元素的 cursor 指向 i 元素的 cursor

回收要删除的结点 核心代码如下：

静态链表的优缺点

优点：在插入和删除操作时，只需要移动元素，从而改进了顺序存储结构中的插入和删除操作需要移动大量元素的缺点。缺点：没有解决连续存储分配带来的表长难以确定的问题，以及失去了顺序存储结构随机存取的特性。

运行结果

为了不占篇幅就不把运行结果贴上来了，线性表的静态链表不是很难，关键点就只有插入和删除操作优点难理解，这里还有一些其他操作我没有写上去，因为比较简单，比方说：获取静态链表的长度，尾插法插入结点，如果想要知道所有操作细节，欢迎查看我的数据结构的源码获取方式。

项目源码获取方式

github地址：https://github.com/liuenci/Data-Structure。有兴趣的同学可以帮我点个Star啊。

程序员的日常技术分享