线性表之静态链表
1. 静态链表的设计
1.1 定义静态链表
链表是由多个相同类型的节点组成的线性表，它的每个节点都包含一个数据项和一个指向下一个节点的指针，链表中各个节点的地址是不连续的。
下面是一个用于存储整形数据的链表节点结构：
struct Node
{
int data;
struct Node* next;
};- data：用于存储实际数据
- next：用于连接当前节点的后继节点，存储的是下一个节点的地址（很多资料中将其称之为游标）
静态链表是一种使用数组实现的链表，通常用于环境中无法使用指针的情况。这种结构在内存中是连续存储的，但节点的位置可以变化，因此称为静态链表。
静态链表的节点结构和链表类似，但是不完全相同，当前节点连接后继节点使用的是索引而不是指针。
下面是一个用于存储整形数据的链表节点结构：
struct Node
{
int data;
int next;
};- data：用于存储实际数据
- next：使用索引的方式记录后继节点的位置
由于静态链表是一个数组，也就是说在存储数据之前元素对应的存储空间就已经存在了，此时我们就需要考虑以下几个问题：
- 如何判断当前节点是一个空闲节点？
- 如何判断当前节点是一个有效的数据节点？
- 如何判断当前节点是链表的尾节点？
由于链表的数据域data的值是千变万化的，所以我们只能在它的next域上下功夫，在使用静态链表之前可以对它的值做如下规定（不考虑头结点）：
- next == -1：当前节点为静态链表的尾节点
- next == -2：当前节点为静态链表的空闲节点
- next >= 0：当前节点为静态链表的有效的数据节点
1.2 链表头结点
不论是链表（动态）还是静态链表根据处理方式的不同，都可以分为两大类：带头结点的链表和不带头结点的链表。
带头结点：链表的第一个节点（头结点）的data域不存储数据，next域记录的是第一个数据节点的位置（索引或者地址）
不带头结点：链表的第一个节点的data域存储数据，next域记录的是第二个数据节点的位置（索引或者地址）
一般情况下建议大家使用带头结点的链表，带头结点的链表避免了链表中没有节点的这种情况（空链表指的是链表中没有数据节点），减少了bug的产生，并且更容易处理和维护。
下图描述的是一个静态链表，请大家动脑分析，完成对这个链表的遍历。
虽然数组中存储的数据的按照下边遍历顺序为：null、a、b、c、f、d、g，但实际上在静态链表中存储的数据顺序并非如此。其中的关键点就是：先看各个节点中的 next 域记录的位置，然后再把这个位置作为数组的下标，去访问对应的数组元素。
- 数组0号元素为静态链表的头结点，next=6，所以第1个数据为g
- 数组6号元素为静态链表的数据节点，next=1，所以第2个数据节点为a
- 数组1号元素为静态链表的数据节点，next=5，所以第3个数据节点为d
- 数组5号元素为静态链表的数据节点，next=4，所以第4个数据节点为f
- 数组4号元素为静态链表的数据节点，next=2，所以第5个数据节点为b
- 数组2号元素为静态链表的数据节点，next=3，所以第6个数据节点为c
- 数组3号元素为静态链表的尾节点，没有后继节点
因此遍历静态链表，得到的序列应该是：g、a、d、f、b、c
2. 静态链表和数组
静态链表和数组的本质是相同的，但是在使用方式上又有所不同，下面就给大家总结一下二者的优缺点：
插入删除操作，静态链表效率高
- 静态链表只需要修改对应节点的next域的值，需不要移动元素
- 数组在插入新节点需要大量元素后移，删除节点需要大量元素前移
访问指定位置的元素，数组效率高
- 静态链表需要遍历才能找到这个节点
- 数组通过下标就可以找到该节点了
默认情况下内存大小是固定的
- 申请的内存空间大，但是数据量少，浪费存储空间
- 申请的内存空间小，但是数据量大，内存不够用
静态链表和数组是对同一块连续内存的两种不同使用方式，二者没有孰优孰劣之分，作为一名合格的程序猿要做的就是具体问题具体分析，从众多解决方案中找出一个最优解。