线性表的应用 —— 静态链表

线性表的应用 —— 静态链表

链表还有另一种静态表示方式，可以用一个数组存储数据，用另一个数组记录当前数据的后继的下标。

【举个栗子】

一个动态的单向循环链表：

用静态链表可以先把数据存储在一维数组data[]中，然后用后继数组right[]记录每个元素的后继下标：

0空间没有存储数据，作为头节点。
right[1]=2，代表data[1]的后继下标为2，即data[2]，也就是说元素56的后继为9；right[8]=0，代表data[8]的后继为头节点。

【插入】

若在第6个元素之前插入一个元素25，则只需将25放入data[]数组的尾部，即data[9]=25，然后修改后继数组right[5]=9，right[9]=6，

插入之后，right[5]=9，right[9]=6，也就是说节点5的后继为9，节点9的后继为6，节点6的前驱为9，节点9的后继为6。

相当于节点9被插入节点5和节点6之间，即插入节点6之前。也就是说，元素49的后继为25，元素25的后继为20。这就相当于把元素25插入49、20之间。
不需要移动元素，只改动后继数组就可以了。

【删除】

若删除第3个元素，则只需修改后继数组right[2]=4，此时，2的后继为4，相当于把第3个元素跳过去了，实现了删除功能，而第3个元素并未被真正删除，只是它已不在链表中。

这样做的好处是不需要移动大量的元素。

【为什么后继数组不直接存储数据】

静态链表存储通常存储后继的下标，而不是直接存储数据，除非特殊需要。因为数组下标为int型数据，而数据有可能为long long类型或结构体类型，占的字节数更多。

【静态的双向链表】

举个栗子：一个动态的双向链表

可以先用静态的双链表把数据存储在一维数组data[]中，然后用前驱数组left[]记录每个元素的前驱下标，用后继数组right[]记录每个元素的后继下标。

left[1]=0，代表data[1]没有前驱；
right[1]=2，代表data[1]的后继下标为2，即data[2]，表示元素56没有前驱，其后继为9。
left[8]=7，right[8]=0，表示62的前驱为16，没有后继。

【插入】

left[1]=0，代表data[1]没有前驱；right[1]=2，代表data[1]的后继下标为2，即data[2]，表示元素56没有前驱，其后继为9。left[8]=7，right[8]=0，表示62的前驱为16，没有后继。

插入之后，left[9]=5，right[5]=9，left[6]=9，right[9]=6，也就是说节点5的前驱为9，节点9的后继为9，节点6的前驱为9，节点9的后继为6。

相当于节点9被插入节点5和节点6之间，即插入节点6之前。
不需要移动元素，只改动前驱数组、后继数组就可以了。

【删除】

若删除第3个元素，则只需修改left[4]=2，right[2]=4，如下图所示。此时，4的前驱为2，2的后继为4，相当于跳过了第3个元素，实现了删除功能。和静态单链表一样，第3个元素并未被真正删除，只是已不在链表中。这样做的好处是不需要移动大量元素。

删除之后，left[4]=2，right[2]=4，也就是说节点2的前驱为4，节点2的后继为4，跳过了节点3。