Redis 資料結構之List (連結串列)

摘要： 連結串列的作用 首先我們知道，連結串列提供了高效的節點重排能力、順序性的訪問方式、靈活的增刪節點並調整連結串列的長度。作為一種常用的資料結構，在很多高階的程式語言裡都可以看到。實現的方式大同小異。 與陣列的比較 從記憶體空間來看，陣列是一個連續的記憶體空間屬於連續儲存儲存形式...

連結串列的作用

首先我們知道，連結串列提供了高效的節點重排能力、順序性的訪問方式、靈活的增刪節點並調整連結串列的長度。作為一種常用的資料結構，在很多高階的程式語言裡都可以看到。實現的方式大同小異。

與陣列的比較

從記憶體空間來看，陣列是一個連續的記憶體空間屬於連續儲存儲存形式。而連結串列則是離散儲存的儲存形式，有一個指標指向一個節點。所以意味著連結串列在記憶體中可以是離散的。

就從記憶體儲存方式來看，陣列是一個連續的空間，查詢更快，更加適合使用序列來訪問陣列元素。而連結串列更適對線性表長度無法確定，頻繁的插入刪除操作的動態性比較強的線性表。下圖可見，陣列和連結串列的儲存形式。

陣列	連結串列
a	other
b	a
c	other
d	b
e	other
nil	c

節點的定義

首先我們看一下節點的定義。

prev 記錄前一個節點的指標

next 記錄下一個節點的指標

value 記錄節點的陣陣的值

這樣如果你知道第一個節點就能完整的把整個連結串列迴圈顯示出來。

其實目前來看整個連結串列的結構已經出現了，多個listNode通過prev next 就可以連起來行程一個連結串列。但是redis中的連結串列還對listNode 進行了一個封裝，增加了一些冗餘欄位來提高訪問的效能，跟上一篇文章說的SDS有相似地方。

typedef struct listNode{
//前置節點
struct listNode *prev;
//後置節點
struct listNode *next;
//節點的值
void *value;
}

Redis中的list

在redis中對listNode再次封裝了下，使用了一個list。下面我們看下程式碼：

可以看到跟SDS類似，多了一個表頭，表尾，數量和3個函式。

這幾個屬效能夠達到什麼效果呢？

這3個函式可以說是對連結串列最常用的函式，使用起來十分的方便。連結串列數量作用跟SDS相似，可以用O(1)的複雜度獲取整個連結串列的長度，表頭和表尾可以快速的在表頭和表尾新增元素。否則如果要在最後新增需要迴圈整個連結串列拿到尾節點，改變尾節點的next新增新節點。在redis中使用連結串列，幾乎都是使用list。

typedef struct list{
//連結串列頭
listNode *head;
//連結串列尾
listNode *tail;
//連結串列數量
unsigned long len;
//節點複製韓式布
vode *(*dup) (void *ptr);
//節點釋放
vode *(*free) (void *ptr);
//節點對比
vode *(*match) (void *ptr,void *key);
}