静态链表：数据全部存储在数组中（和顺序表一样），但存储位置是随机的，数据之间"一对一"的逻辑关系通过一个整形变量（称为"游标"，和指针功能类似）维持。
例如，使用静态链表存储 {1,2,3} 的过程如下：
创建一个足够大的数组，假设大小为 6，如图1 所示：
图1：空数组
接着，在将数据存放到数组中时，给各个数据元素配备一个整形变量，此变量用于指明各个元素的直接后继元素所在数组中的位置下标，如图 2 所示：
图2：静态链表存储数据
通常，静态链表会将第一个数据元素放到数组下标为 1 的位置（a[1]）中。
图 2 中，从 a[1] 存储的数据元素 1 开始，通过存储的游标变量 3，就可以在 a[3] 中找到元素 1 的直接后继元素 2；同样，通过元素 a[3] 存储的游标变量 5，可以在 a[5] 中找到元素 2 的直接后继元素 3，这样的循环过程直到某元素的游标变量为 0 截止（因为 a[0] 默认不存储数据元素）。
类似图 2 这样，通过 "数组+游标" 的方式存储具有线性关系数据的存储结构就是静态链表。
静态链表中的节点
静态链表存储数据元素也需要自定义数据类型，至少需要包含以下2部分信息：
- 数据域：用于存储数据元素的值
- 游标：其实就是数组的下表，表示直接后继元素所在数组中的位置
备用链表
图2显示的静态链表还不够完整，静态链表搜中，出了数据本身通过游标组成的立案表外，还需要有一条连接各个空闲位置的链表，称为备用链表
通常，备用链表的表头位于数组下标为 0（a[0]） 的位置，而数据链表的表头位于数组下标为 1（a[1]）的位置。
图3：备用链表和数据链表
静态链表中设置备用链表的好处是，可以清楚地知道数组中是否有空闲位置，以便数据链表添加新数据时使用。比如，若静态链表中数组下标为 0 的位置上存有数据，则证明数组已满。
静态链表的实现
假设使用静态链表（数组长度为 6）存储 {1,2,3}，则需经历以下几个阶段。
在数据链表未初始化之前，数组中所有位置都处于空闲状态，因此都应被链接在备用链表上，如图 4 所示：
图4 未存储前静态链表的结构
当向静态链表中添加数据时，需提前从备用链表中摘除节点，以供新数据使用。
备用链表摘除节点最简单的方法是摘除 a[0] 的直接后继节点；同样，向备用链表中添加空闲节点也是添加作为 a[0] 新的直接后继节点。因为 a[0] 是备用链表的第一个节点，我们知道它的位置，操作它的直接后继节点相对容易，无需遍历备用链表，耗费的时间复杂度为
O(1)。
因此，在图 4 的基础上，向静态链表中添加元素 1 的过程如图 5 所示：
图5 静态链表中添加元素1
在图5的基础上，添加元素2的过程如图6所示：
图6：静态链表中继续添加元素2
在图 6 的基础上，继续添加元素 3 ，过程如图 7 所示：
图7：静态链表中继续添加元素3
静态链表与动态链表区别
类似于图8 这样的链表，我们称他为“动态链表”。
图8:链表存储结构
类似于图9 这样的链表，我们称他为“静态链表”。
图9：静态链表存储数据示意图
静态链表和动态链表的共同点是，数据之间"一对一"的逻辑关系都是依靠指针（静态链表中称"游标"）来维持，仅此而已。
静态链表
使用静态链表存储数据，需要预先申请足够大的一整块内存空间，也就是说，静态链表存储数据元素的个数从其创建的那一刻就已经确定，后期无法更改。
静态链表是在固定大小的存储空间内随机存储各个元素，这就造成了静态链表中需要使用另一条链表（一般称为“备用链表”），来记录空闲存储空间的位置。
这意味着使用静态链表除了操作数据链表，还需要操作备用链表。
动态链表
动态链表不需要预先申请内存空间，也就是说动态链表存储数据元素的个数是不限的，想存多少就存多少。
同时，使用动态链表整个过程是需要操控一条存储数据的链表。当添加删除元素的时，只需要申请malloc或释放free空间即可（java中不需要，gc自动回收），实现简单。
循环链表
无论是静态链表还是动态链表，有时候在解决具体问题时，需要我们对其结构进行稍微地调整。比如，可以把链表两头连接，使其成为一个环状链表，通常称为循环链表。
图10 循环链表
需要注意的是，虽然循环链表成环状，但本质上还是链表，因此在循环链表中，依然能够找到头指针和首元节点等。循环链表和普通链表相比，唯一的不同就是循环链表首尾相连，其他都完全一样。
循环链表实现约瑟夫环
约瑟夫环问题，是一个经典的循环链表问题，题意是：已知 n 个人（分别用编号 1，2，3，…，n 表示）围坐在一张圆桌周围，从编号为 k 的人开始顺时针报数，数到 m 的那个人出列；他的下一个人又从 1 开始，还是顺时针开始报数，数到 m 的那个人又出列；依次重复下去，直到圆桌上剩余一个人。
如图 11 所示，假设此时圆周周围有 5 个人，要求从编号为 3 的人开始顺时针数数，数到 2 的那个人出列：
图11：循环链表实现约瑟夫环
出列顺序依次为：
- 编号为 3 的人开始数 1，然后 4 数 2，所以 4 先出列；
- 4 出列后，从 5 开始数 1，1 数 2，所以 1 出列；
- 1 出列后，从 2 开始数 1，3 数 2，所以 3 出列；
- 3 出列后，从 5 开始数 1，2 数 2，所以 2 出列；
- 最后只剩下 5 自己，所以 5 胜出。
约瑟夫环问题有多种变形，比如顺时针转改为逆时针等，虽然问题的细节有多种变数，但解决问题的中心思想是一样的，即使用循环链表。
//解决了约瑟夫环问题，但未使用循环链表
private static void senario(int total, int cycle) {
List<Integer> all = new LinkedList<Integer>();
for(int i = 1;i <= total;i++){
all.add(i);
}
int i = 0;
for(int n = 1;n < total;n++){
i = (i + cycle -1) % all.size();
System.out.print(all.get(i)+(n==total-1?"\n":" "));
all.remove(i);
}
System.out.printf("幸存者为：%d号 (人数=%d, 周期=%d, (默认从第1个人开始、正向报数))\n",
all.get(0), total, cycle);
}
循环链表和动态链表唯一不同在于它的首尾连接，这也注定了在使用循环链表时，附带最多的操作就是遍历链表。
在遍历的过程中，尤其要注意循环链表虽然首尾相连，但并不表示该链表没有第一个节点和最后一个结点。所以，不要随意改变头指针的指向。
双向链表
无论是动态链表还是静态链表，表中各节点中都只包含一个指针（游标），且都统一指向直接后继节点，通常称这类链表为单向链表（或单链表）。
如果算法中需要大量地找某指定结点的前趋结点，链表并不是效率最优的存储结构，为了能够高效率解决"从后往前"的问题，可以使用双向链表（简称双链表）。
图12：双向链表结构示意图
双向，指的是各节点之间的逻辑关系是双向的，但通常头指针只设置一个，除非实际情况需要。
从图 11 中可以看到，双向链表中各节点包含以下 3 部分信息（如图 12 所示）：
- 指针域：用于指向直接前驱节点
- 数据域：用于存储数据元素
- 指针域：用于存储直接后继节点
图12：双向链表节点构成
双向链表的基本操作
添加至表头
假设新元素节点为 temp，表头节点为 head，则需要做以下 2 步操作即可
- temp.next = head; head.prior=temp;
- 将头指针重新指向temp
图13 添加元素至双链表的表头
添加至表中
新节点先与直接后继节点建立双层逻辑关系
新节点的直接前驱节点与新节点建立双层逻辑关系
图14：添加元素至双链表表中
添加至表尾
找到双链表最后一个节点
让新节点与最后一个节点进行双层逻辑关系
图15：双链表尾部添加数据
双链表删除，查找，更改
与单链表几乎无异。
双向循环链表
双向链表也可以进行首尾连接，构成双向循环链表。如图 16 所示：
图16：双向循环链表示意图
当问题中涉及到需要 "循环往复" 地遍历表中数据时，就需要使用双向循环链表。例如，前面章节我们对约瑟夫环问题进行了研究，其实约瑟夫环问题有多种玩法，每次顺时针报数后，下一轮可以逆时针报数，然后再顺时针......一直到剩下最后一个人。解决这个问题就需要使用双向循环链表结构。
网友评论