為了彌補鏈表在內存分配上的不足，出現了靜態鏈表這么一個折中的辦法。靜態鏈表比較類似于內存池，它會預先分配一個足夠長的數組，之后鏈表節點都會保存在這個數組里，這樣就不需要頻繁的進行內存分配了。
當然，這個方法的缺點是需要預先分配一個足夠長的數組，肯定會導致內存的浪費。數組不夠長到不是什么大不了的，使用第一節的動態擴容方法就是了。
靜態鏈表一般是由兩個鏈表組成，一個保存數據的鏈表，一個空閑節點的鏈表，如圖 3 所示。
圖 3 靜態鏈表
當需要向鏈表中添加節點時，就從空閑鏈表中摘下一個使用。從鏈表中刪除節點時，就將被刪除的節點歸還到空閑鏈表中。
在實現上，由于靜態鏈表的節點都是存儲在數組中的，所以經常使用數組索引代替指針，如果數組擴容了，也不會影響現有的節點。下面簡單的實現了一個靜態雙向鏈表，沒有添加動態擴容的能力。
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | struct?snode {????int?value;????int?prev;????int?next;};struct?sllist {????snode *nodes;????int?head, freeHead;????sllist():head(-1), freeHead(0) {????????// 初始化空閑鏈表，靜態分配長度為 100。????????nodes =?new?snode[100];????????for?(int?i = 0;i < 100;i++) {????????????nodes[i].next = i + 1;????????}????}????void?add(int?value) {????????// 從空閑鏈表中摘取節點。????????int?newNode = freeHead;????????freeHead = nodes[freeHead].next;????????nodes[newNode].value = value;????????nodes[newNode].prev = -1;????????nodes[newNode].next = head;????????if?(head != -1) {????????????nodes[head].prev = newNode;????????}????????head = newNode;????}????void?remove(snode node) {????????int?idx = head;????????if?(node.prev == -1) {????????????head = node.next;????????}?else?{????????????idx = nodes[node.prev].next;????????????nodes[node.prev].next = node.next;????????}????????if?(node.next != -1) {????????????nodes[node.next].prev = node.prev;????????}????????// 將節點歸還空閑鏈表。????????nodes[idx].next = freeHead;????????freeHead = idx;????}}; |
靜態鏈表的效率幾乎跟數組一樣，極大的提升了鏈表的效率。不過因為鏈表的效率受內存分配影響，不同的語言可能有不同的表現，具體情況還需要實驗分析才可以。
函數獲取時間的設置和使用方法)
