大话数据结构三：线性表的链式存储结构（静态链表）

1. 静态链表：用数组描述的链表叫静态链表，通常为方便数据插入，我们会把数组建的大一些。

2. 数组元素（node）：由两个数据域组成（data，cursor）。数据域data用来存放数据元素，也就是通常我们要处理的数据；而cursor相当于单链表中的指针，存放该元素的后继在数组中的下标。

3. Java实现静态链表：

// 静态链表
class StaticLinkedList {
	private int size;
	private Node[] node = new Node[100];

	// 用数组初始化静态链表
	public StaticLinkedList(int arr[]) {
		for (int i = 0; i < 100; i++) {
			node[i] = new Node(); // 初始化100个结点对象（感觉性能不会很好）
		}
		for (int j = 0; j < arr.length; j++) {
			node[j + 1].setData(arr[j]);  // 第一个结点为头结点，头结点没有数据,只存索引
			node[j].setCursor(j + 1);
		}
		size = arr.length;
	}

	// 在某位置插入值
	public void insert(int index, int value) {
		validateIndex(index);
		int curIndex = node[index].getCursor();    // 获取待插入结点的前一个结点指针,它记住的是原待插入结点位置
		node[size + 1].setData(value); // 第一个结点为头结点,所以新插入的结点为node[size + 1]
		node[size + 1].setCursor(curIndex); // 让新插入的结点记住原位置结点角标
		node[index].setCursor(size + 1); // 让原位置前一结点记住新插入结点角标
		size++;
	}

	// 删除指定位置的值
	public void delete(int index) { 
		validateIndex(index);
		int curIndex = node[index].getCursor(); // 获取待删除节点的前一个结点指针,它记住的是待删除结点角标（注：第一个结点为头结点）
		int nextIndex = node[curIndex].getCursor(); // 获取待删除节点指针,它记住的是待删除的下一个结点角标
		node[index].setCursor(nextIndex); // 将待删除结点的前一个结点指针指向待删除结点的下一个结点角标
		size--;
	}
	
	// 验证下标值是否合法，非法时抛出异常。
	private void validateIndex(int index) {
		if (index < 0 || index > size) {
			throw new IndexOutOfBoundsException("无效的下标：" + index);
		}
	}

	// 输出所有元素
	public void display() {
		int nextIndex = node[0].getCursor();  // node[0] 为头结点,存的是下一个结点角标
		int i = 0;
		while (i < size) {
			System.out.printf("%d\t", node[nextIndex].getData());
			nextIndex = node[nextIndex].getCursor();
			i++;
		}
	}
}

// 结点(数组元素)
class Node {
	int data; // 记录存入的数据 
	int cursor; // 记录下一个数据的下标
	public int getData() {
		return data;
	}
	public void setData(int data) {
		this.data = data;
	}
	public int getCursor() {
		return cursor;
	}
	public void setCursor(int cursor) {
		this.cursor = cursor;
	}
}

// 测试类
public class Main {
	public static void main(String[] args) {
		int arr[] = { 1, 3, 4, 5, 6 };
		StaticLinkedList list = new StaticLinkedList(arr);
		System.out.print("初始化：\n");
		list.display();
		System.out.print("\n在角标为1的位置插入2后：\n");
		list.insert(1, 2);
		list.display();
		System.out.print("\n删除角标为5的结点后：\n");
		list.delete(5);
		list.display();
	}
}

4. 静态链表的优越点：

优点：在插入和删除操作时,不需要移动元素,从而改进了在顺序存储结构中插入和删除操作需要移动大量元素的缺点。

缺点：没有解决连续存储分配带来表长难以确定的问题。

5. 总的来说，静态链表其实是为了给没有指针的高级语言设计的一种实现单链表的方法，一般很少用。