鏈表簡介
鏈表提供了高效的節(jié)點重排能力， 以及順序性的節(jié)點訪問方式， 并且可以通過增刪節(jié)點來靈活地調(diào)整鏈表的長度。作為一種常用數(shù)據(jù)結構厌衙， 鏈表內(nèi)置在很多高級的編程語言里面， 因為 Redis 使用的 C 語言并沒有內(nèi)置這種數(shù)據(jù)結構绞绒， 所以 Redis 構建了自己的鏈表實現(xiàn)迅箩。
鏈表及鏈表節(jié)點的實現(xiàn)
- 每個鏈表節(jié)點使用一個adlist.h/listNode結構來表示
typedef struct listNode {
struct listNode *prev; /* 前置節(jié)點 */
struct listNode *next; /* 后置節(jié)點 */
void *value; /* 節(jié)點值 */
} listNode;
- Reids還定義了鏈表結構，用于持有鏈表
typedef struct list {
listNode *head; /* 表頭結點 */
listNode *tail; /* 表尾結點 */
void *(*dup)(void *ptr); /* 節(jié)點復制函數(shù) */
void (*free)(void *ptr); /* 節(jié)點釋放函數(shù) */
int (*match)(void *ptr, void *key);
unsigned long len; /* 鏈表節(jié)點數(shù)量 */
} list;
list 結構為鏈表提供了表頭指針 head 处铛、表尾指針 tail 饲趋， 以及鏈表長度計數(shù)器 len ， 而 dup 撤蟆、 free 和 match 成員則是用于實現(xiàn)多態(tài)鏈表所需的類型特定函數(shù)：
- dup 函數(shù)用于復制鏈表節(jié)點所保存的值奕塑；
- free 函數(shù)用于釋放鏈表節(jié)點所保存的值；
- match 函數(shù)則用于對比鏈表節(jié)點所保存的值和另一個輸入值是否相等家肯。
如圖是由一個list結構和三個listNode結構組成的鏈表
list持有l(wèi)istNode示例.png
這樣定義好處是
- 快速獲取鏈表的頭尾
- 快速查詢鏈表的節(jié)點數(shù)龄砰，像動態(tài)字符串sdshr里的len那樣，不用遍歷全部字符就可以獲取字符串的長度讨衣，這里也類似换棚。
- adlist.h/listIter還定義了迭代器
typedef struct listIter {
listNode *next; /* 當前迭代到的節(jié)點 */
int direction; /* 迭代方向 */
} listIter;
/* Directions for iterators
*
* 迭代器進行迭代的方向
*/
// 從表頭向表尾進行迭代
#define AL_START_HEAD 0
// 從表尾到表頭進行迭代
#define AL_START_TAIL 1
可以這樣迭代
iter = listGetIterator(list, AL_START_HEAD);
while ((node = listNext(iter)) != NULL) {
doSomethingWith(node);
}
鏈表和鏈表節(jié)點的API
| 函數(shù) | 作用 | 時間復雜度 |
|---|---|---|
| listSetDupMethod | 將給定的函數(shù)設置為鏈表的節(jié)點值復制函數(shù)。 | O(1) |
| listGetDupMethod | 返回鏈表當前正在使用的節(jié)點值復制函數(shù)反镇。 | 復制函數(shù)可以通過鏈表的 dup 屬性直接獲得固蚤， O(1) |
| listSetFreeMethod | 將給定的函數(shù)設置為鏈表的節(jié)點值釋放函數(shù)。 | O(1) |
| listGetFree | 返回鏈表當前正在使用的節(jié)點值釋放函數(shù)歹茶。 | 釋放函數(shù)可以通過鏈表的 free 屬性直接獲得夕玩， O(1) |
| listSetMatchMethod | 將給定的函數(shù)設置為鏈表的節(jié)點值對比函數(shù)。 | O(1) |
| listGetMatchMethod | 返回鏈表當前正在使用的節(jié)點值對比函數(shù)惊豺。 | 對比函數(shù)可以通過鏈表的 match 屬性直接獲得燎孟， O(1) |
| listLength | 返回鏈表的長度（包含了多少個節(jié)點）。 | 鏈表長度可以通過鏈表的 len 屬性直接獲得尸昧， O(1) |
| listFirst | 返回鏈表的表頭節(jié)點揩页。 | 表頭節(jié)點可以通過鏈表的 head 屬性直接獲得， O(1) |
| listLast | 返回鏈表的表尾節(jié)點烹俗。 | 表尾節(jié)點可以通過鏈表的 tail 屬性直接獲得爆侣， O(1) |
| listPrevNode | 返回給定節(jié)點的前置節(jié)點萍程。 | 前置節(jié)點可以通過節(jié)點的 prev 屬性直接獲得， O(1) |
| listNextNode | 返回給定節(jié)點的后置節(jié)點累提。 | 后置節(jié)點可以通過節(jié)點的 next 屬性直接獲得， O(1) |
| listNodeValue | 返回給定節(jié)點目前正在保存的值磁浇。 | 節(jié)點值可以通過節(jié)點的 value 屬性直接獲得斋陪， O(1) |
| listCreate | 創(chuàng)建一個不包含任何節(jié)點的新鏈表。 | O(1) |
| listAddNodeHead | 將一個包含給定值的新節(jié)點添加到給定鏈表的表頭置吓。 | O(1) |
| listAddNodeTail | 將一個包含給定值的新節(jié)點添加到給定鏈表的表尾无虚。 | O(1) |
| listInsertNode | 將一個包含給定值的新節(jié)點添加到給定節(jié)點的之前或者之后。 | O(1) |
| listSearchKey | 查找并返回鏈表中包含給定值的節(jié)點衍锚。 | O(N) 友题， N 為鏈表長度 |
| listIndex | 返回鏈表在給定索引上的節(jié)點。 | O(N) 戴质， N 為鏈表長度 |
| listDelNode | 從鏈表中刪除給定節(jié)點度宦。 | O(1) |
| listRotate | 將鏈表的表尾節(jié)點彈出，然后將被彈出的節(jié)點插入到鏈表的表頭告匠， 成為新的表頭節(jié)點戈抄。 | O(1) |
| listDup | 復制一個給定鏈表的副本。 | O(N) 后专， N 為鏈表長度 |
| listRelease | 釋放給定鏈表划鸽，以及鏈表中的所有節(jié)點。 | O(N) 戚哎， N 為鏈表長度 |
