【数据结构与算法】【06】数据结构之静态链表

静态链表存储原理

静态链表是一种特殊的链表，它以数组和游标，来间接实现指针的连接效果

这种方式，主要适合一些，没有指针，没有面向对象特性的语言

游标在这里指的就是数组下标，因为没有指针，就用数组下标来标记数据地址

静态链表的主要存储原理包括

• 用数组来代替随机存储
• 数组中的元素，必须包含data数据和next游标两部分，next游标指示下个元素在数组中的下标
• 用特殊值-1来代表链表已经到达链表结尾
• 由于链表存在插入、删除、移动等操作，这些操作仅仅调整了游标指向，并不会真的调整元素在数组中的存储位置，所以元素最终的存储位置仍然是随机的
• 除了记录数据，还要记录哪里有空闲位置可以插入新元素，因此静态链表实际是包含两条链表的，分别是数据链表和备用链表
• 链表的首尾两个元素，具有特殊作用，它们分别用来指向首个闲置元素，和首个数据元素，分别是备用链表和数据链表的头节点
• 当数据链表头节点指向-1时，表示链表是空的，当备用链表头节点指向-1时，表示链表已满

静态链表实现代码

示例代码包含了静态链表的遍历、插入、增加、删除、查询、扩容操作

	import java.util.Arrays;
	import java.util.Objects;
	
	//静态链表
	@SuppressWarnings("all")
	public class StaticList {
	
	    Node[] array;
	
	    //初始化
	    public void Init(int initialLength) {
	        //创建初始数组
	        array = new Node[initialLength];
	        //创建全部节点
	        for (int i = 0; i