目錄
為什麼會有靜态連結清單？
怎麼做到的呢？
靜态連結清單是什麼？
靜态連結清單的代碼實作：
準備工作：
初始化靜态連結清單：
添加元素：
插入元素：
删除元素：
總結：
為什麼會有靜态連結清單？
Basic、Fortran 等早期的程式設計進階語言，由于沒有指針，連結清單結構按照指針的方式，它就沒有辦法實作。
有人就想出了用數組來代替指針，來描述單連結清單。
怎麼做到的呢？
首先我們讓數組的元素都是有兩個資料域組成，data 和 cur(Cursor：遊标)。
數組的每個下标都對應一個 data 和一個 cur。
- 資料域 data，用來方法資料元素。
- 遊标 cur，相當于單連結清單中的next指針，存放該元素的後繼在數組中的下标，
用數組描述的連結清單叫做靜态連結清單，也叫做遊标實作法。
靜态連結清單是什麼？
靜态連結清單其實是為了給沒有指針的進階語言設計的一種實作單連結清單能力的方法。
靜态連結清單的代碼實作：
由于水準有限，就使用Java來實作。
準備工作：
既然是一個資料結構那麼我們就先建立一個類：StaticLinkedList
然後實作連結清單的結點類：Node（内部類）
public class StaticLinkedList <T> {
private StaticNode<T>[] data;
private static final int MAX_SIZE = 1000; //初始化先對建立的大一些，以便有空閑空間保證插入時不至于溢出
private int size = 0;//有效元素的個數
private int lastNodeIndex = 0; //連結清單中最後一個有值結點的下标
/**
* 結點類
*/
static class Node<T>{
T data; //資料域
int cur; //遊标Corsor，存放後繼結點在數組中的下标
}
}
初始化靜态連結清單：
要對數組第一個和最後一個元素作為特殊元素處理，不存資料。我們通常把未被使用的數組元素稱為備用連結清單。
- 數組第一個元素，即下标為0的元素的 cur 就存放備用連結清單的第一個結點的下标；
- 數組的最後一個元素的 cur 則存放第一個有數值的元素的下标，相當于單連結清單中的頭結點作用，當整個連結清單為空時，則為0。
public class StaticLinkedList <T> {
。。。。
public StaticLinkList(){
data = new StaticNode[MAX_SIZE];
initList(data);
}
/**
* 初始化靜态連結清單
* @param data
*/
private void initList(StaticNode<T>[] data) {
for (int i = 0; i < data.length - 1; i++) {
data[i] = new StaticNode<T>(null, i+1); //初始化每個節點的cur值，為其數組中下标加1，指向下一個元素
}
data[data.length-1] = new StaticNode<T>(null, 0); //數組最後一個元素的cur，
//用來存放第一個插入元素的下标，即第一個有值元素的下标
}
。。。。
}
添加元素：
分析：
- 向連結清單申請空閑空間（申請空間需要自己實作）
- 判斷是否是第一次添加元素 size == 0
- 是：将數組中最後一個結點的cur指向1，指向連結清單中第一個有值元素的下标
- 否：将新添加元素的下标與最後一個有值元素的遊标聯系起來。
- 更新存儲最後一個有值元素變量的值，其實就是，申請空間傳回的下标
代碼：
/**
* 順序添加元素
* @param item 待添加的元素
* @return
*/
public boolean add(T item){
int newCur = malloc_SLL(); //申請空閑空間
StaticNode<T> newNode = new StaticNode<>(item, 0); //新添加元素，由于是最後一個元素，其遊标置0
data[newCur] = newNode; //存儲新結點
if (size == 0){ //連結清單為空，
//添加的時候不能改變起始的結點下标，除非是第一次添加結點
data[data.length-1].cur = 1; //最後一個元素的遊标存放第一個有值元素的下标，為1
}else{
//尾插法，擷取到最後一個有值元素的下标
//将最後一個有值結點的遊标與新結點的下标連接配接起來
data[lastNodeIndex].cur = newCur;
}
//最後一個有值結點的下标，就是新添加的結點的下标
lastNodeIndex = newCur;
size ++;
return true;
}
mallc_SLL():
分析：
- 需要擷取 空閑空間的下标 ，這不就是 data[0].cur 的值嘛！
- 擷取完元素後要将更改 data[0].cur 的值，因為現在的值，已經被我們申請了
/**
* 傳回空閑空間的下标
* @return
*/
private int malloc_SLL(){
int i = data[0].cur; //擷取到空閑空間的下标
if (i != 0) {
data[0].cur = data[i].cur; //第一個空閑空間被我們拿走了，就要将後一個空閑空間的下标指派給，data[0]的cur
}
return i;
}
效果：
測試代碼：
@Test
public void test(){
StaticLinkedList list = new StaticLinkedList();
list.addElem("甲");
list.addElem("乙");
list.addElem("丁");
list.addElem("戊");
list.addElem("己");
System.out.println(list);
}
效果：
注意：要看到效果需要重寫 toString() 方法
public String toString() {
String str = "StaticLinkedList = [ ";
int i = data[length - 1].cur;
while(data[i].data != null){
str += data[i].data + " ";
i = data[i].cur;
}
str += "]";
return str;
}
按順序添加元素已經完成了！接下來就寫插入元素吧
插入元素：
分析：
- 判斷插入的位置是再最後一個有值元素結點的後面，還是其他位置
- 将資料指派給申請到的空閑空間
- 把前一進制素的cur指派給新結點的cur
- 把新結點的下标，指派給前一進制素的cur
代碼：
/**
* 靜态連結清單的插入操作
* @param item
* @param index
* @return
*/
public boolean insert(T item, int index){
//插入到最後面
if (size == index -1){
//調用add()
return this.add(item);
}
rangeCheck(index);
int ccur = MAX_SIZE -1; //擷取第一個有值結點的下标
int fIndex = malloc_SLL(); //獲得空閑分量的下标
if (fIndex != 0){
data[fIndex].data = item; //将資料指派給新得到的分量
for (int i = 1; i <= index - 1; i++) { //周遊，找到第i個元素之前的位置
ccur = data[ccur].cur;
}
data[fIndex].cur = data[ccur].cur; //把第i個結點之前的cur指派給新結點的cur
data[ccur].cur = fIndex; //把新結點的下标指派給第i個結點之前結點的cur
size ++;
return true;
}
return false;
}
測試：
測試的資料就是之前插入的資料
@Test
public void insertTest(){
list.insert("丙",5); //插入到末尾
System.out.println(list);
list.insert("中間", 3); //插入到中間
System.out.println(list);
list.insert("頭", 1); //插入到開頭
System.out.println(list);
}
效果：
rangeCheck()：方法
/**
* 檢測index是否合法
* @param index
*/
private void rangeCheck(int index) {
//1. 索引過小 2.索引過大
if (index < 1 || index > size){
throw new RuntimeException("[StaticLinkList] 索引越界，index:"+index+",size:"+size);
}
}
删除元素：
分析：
- 循環，擷取到前一進制素的下标
- 判斷是否删除的是最後一個元素
- 是：将lastNodeIndex改為前一進制素的下标
- 儲存前一進制素的遊标
- 儲存要删除元素的遊标值
- 将前一進制素的遊标替換為後一進制素的遊标
- 将被删除的元素，添加到備用連結清單
代碼：
/**
* 靜态連結清單的删除操作
* @param index 待删除的元素的位置
* @return
*/
public T delete(int index){
//檢測index是否合法
rangeCheck(index);
int ccur = MAX_SIZE - 1; //擷取到第一個有值元素的下标
for (int i = 1; i <= index - 1; i++) { //擷取到指定位置前一進制素
ccur = data[ccur].cur;
}
//判斷是否是删除最後一個結點
if (index == size){
lastNodeIndex = ccur; //将lastNodeIndex更改為前一個結點的下标
}
int j = data[ccur].cur; //将被删除結點遊标的值指派給儲存起來
data[ccur].cur = data[j].cur; //将要被删除的結點的後續結點的下标，指派給前一結點的遊标（完成删除操作）
freeSLL(j); //将空閑空間回收到備用連結清單
size --; //有效元素-1
//傳回被删除結點的資料
return data[j].data;
}
測試：
@Test
public void delete(){
System.out.println("删除第一個："+list.delete(1));
System.out.println(list);
System.out.println("删除中間："+list.delete(2));
System.out.println(list);
System.out.println("删除最後一個："+list.delete(list.getSize()));
System.out.println(list);
}
效果：
free_SLL(int index)：将空閑空間回收到備用連結清單
/**
* 回收結點，到備用連結清單
* @param j
*/
private void freeSLL(int j) {
data[j].cur = data[0].cur; //将被删除的結點，添加到備用連結清單中去
data[0].cur = j; //讓data[0]的遊标，存儲第一個空閑空間的下标 j下标所指的結點就是第一個空閑空間了
}
好了，靜态連結清單的基本操作就是這些了！！！
總結：
靜态連結清單優缺點：
優點：
- 在插入和删除操作時，隻需要修改遊标，不需要移動元素，進而改進了在順序存儲結構中的插入和删除操作需要移動大量元素的缺點。
缺點：
- 沒有解決連續存儲配置設定帶來的表長難以确定的問題
- 失去了順序存儲結構随機存取的特性
總的來說，靜态連結清單其實就是為了給沒有指針的進階語言設計的一種實作單連結清單能力的方法。
如果，本文中有錯的話，懇請大家指出，我一定改正！！！