前言
鏈表提供了高效的節點重排能力， 以及順序性的節點訪問方式， 并且可以通過增刪節點來靈活地調整鏈表的長度，
作為一種常用資料結構， 鏈表內置在很多高級的編程語言里面， 因為 Redis 使用的 C 語言并沒有內置這種資料結構， 所以 Redis 構建了自己的鏈表實作，
大家可以把Redis的鏈表實作，和Java的LinkedList實作進行對比，看下哪個更加厲害一點，
鏈表定義
1 typedef struct listNode { 2 3 // 前置節點 4 struct listNode *prev; 5 6 // 后置節點 7 struct listNode *next; 8 9 // 節點的值 10 void *value; 11 12 } listNode;
多個 listNode 可以通過 prev 和 next 指標組成雙端鏈表， 如圖 3-1 所示，
雖然僅僅使用多個 listNode 結構就可以組成鏈表， 但使用 adlist.h/list 來持有鏈表的話， 操作起來會更方便：
1 typedef struct list { 2 3 // 表頭節點 4 listNode *head; 5 6 // 表尾節點 7 listNode *tail; 8 9 // 鏈表所包含的節點數量 10 unsigned long len; 11 12 // 節點值復制函式 13 void *(*dup)(void *ptr); 14 15 // 節點值釋放函式 16 void (*free)(void *ptr); 17 18 // 節點值對比函式 19 int (*match)(void *ptr, void *key);
我們可以看到，list包含鏈表的頭節點，尾節點以及長度，這就為鏈表帶來了很多的好處，如下：
- 雙端： 鏈表節點帶有
prev和next指標， 獲取某個節點的前置節點和后置節點的復雜度都是 O(1) ， - 無環： 表頭節點的
prev指標和表尾節點的next指標都指向NULL， 對鏈表的訪問以NULL為終點， - 帶表頭指標和表尾指標： 通過
list結構的head指標和tail指標， 程式獲取鏈表的表頭節點和表尾節點的復雜度為 O(1) ， - 帶鏈表長度計數器： 程式使用
list結構的len屬性來對list持有的鏈表節點進行計數， 程式獲取鏈表中節點數量的復雜度為 O(1)，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/235323.html
標籤：其他
上一篇：Apache Kylin 概述