redis实现跳表源码，Redis源码阅读之链表实现
redis实现跳表源码，Redis源码阅读之链表实现3、 带表头指针和表尾指针：通过list结构的head指针和tail指针，程序获取链表的表头节点和表尾节点的复杂度为O(1)。2、 无环：表头节点的prev指针和表位节点的next指针都指向null，对链表的访问以null为终点。1. 作为列表键的底层实现之一：当一个列表键包含了数量比较多的元素，又或者列表中包含的元素都是比较长的字符串时，Redis就会使用链表作为列表键的底层实现。2. 除此之外，发布与订阅、慢查询、监视器等功能也用到了链表，Redis服务器本身还使用链表来保存多个客户端的状态信息， 以及使用链表来构建客户端输出缓冲区。1、 双端：链表节点带有prev和next指针，获取某个节点的前置节点和后置节点的复杂度都是O(1)。
什么是链表链表是一种物理 存储单元 上非连续、非顺序的存储结构， 数据对象的逻辑顺序是通过链表中的指针进行链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储 数据元素 的数据域，另一个是存储下一个结点地址的 指针 域。 相比于 线性表 顺序结构 ，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)
Redis的底层数据结构-链表一、链表结构定义
1. 链表节点结构定义：
2. 链表结构定义：
1. 作为列表键的底层实现之一：当一个列表键包含了数量比较多的元素，又或者列表中包含的元素都是比较长的字符串时，Redis就会使用链表作为列表键的底层实现。
2. 除此之外，发布与订阅、慢查询、监视器等功能也用到了链表，Redis服务器本身还使用链表来保存多个客户端的状态信息， 以及使用链表来构建客户端输出缓冲区。
Redis的链表特性总结1、 双端：链表节点带有prev和next指针，获取某个节点的前置节点和后置节点的复杂度都是O(1)。
2、 无环：表头节点的prev指针和表位节点的next指针都指向null，对链表的访问以null为终点。
3、 带表头指针和表尾指针：通过list结构的head指针和tail指针，程序获取链表的表头节点和表尾节点的复杂度为O(1)。
4、 带链表长度计数器：程序使用list结构的len属性来对list持有的链表节点进行计数，所以获取节点数量的复杂度为O(1)。
5、 多态：链表节点使用void *指针来保存节点值，并且可以通过list结构的dup、free、match三个属性为节点设置类型特定函数，所以链表可以用于保存各种不同类型的值。
链表和链表节点的API
创建链表
创建链表 41 list *listCreate(void) 42 { 43 struct list *list; 44 45 if ((list = zmalloc(sizeof(*list))) == NULL) 46 return NULL; 47 list->head = list->tail = NULL; 48 list->len = 0; 49 list->dup = NULL; 50 list->free = NULL; 51 list->match = NULL; 52 return list; 53 }
清空链表，但是不释放这个链表
55 /* Remove all the elements from the list without destroying the list itself. */ 56 void listEmpty(list *list) 57 { 58 unsigned long len; 59 listNode *current *next; 60 61 current = list->head; 62 len = list->len; 63 while(len--) { 64 next = current->next; 65 if (list->free) list->free(current->value); 66 zfree(current); 67 current = next; 68 } 69 list->head = list->tail = NULL; 70 list->len = 0; 71 }
释放链表
76 void listRelease(list *list) 77 { 78 listEmpty(list); 79 zfree(list); 80 }
连接两个链表
345 /* Add all the elements of the list 'o' at the end of the 346 * list 'l'. The list 'other' remains empty but otherwise valid. */ 347 void listJoin(list *l list *o) { 348 if (o->head) 349 o->head->prev = l->tail; 350 351 if (l->tail) 352 l->tail->next = o->head; 353 else 354 l->head = o->head; 355 356 if (o->tail) l->tail = o->tail; 357 l->len = o->len; 358 359 /* Setup other as an empty list. */ 360 o->head = o->tail = NULL; 361 o->len = 0; 362 }
复制链表
250 list *listDup(list *orig) 251 { 252 list *copy; 253 listIter iter; 254 listNode *node; 255 256 if ((copy = listCreate()) == NULL) 257 return NULL; 258 copy->dup = orig->dup; 259 copy->free = orig->free; 260 copy->match = orig->match; 261 listRewind(orig &iter); 262 while((node = listNext(&iter)) != NULL) { 263 void *value; 264 265 if (copy->dup) { 266 value = copy->dup(node->value); 267 if (value == NULL) { 268 listRelease(copy); 269 return NULL; 270 } 271 } else 272 value = node->value; 273 if (listAddNodeTail(copy value) == NULL) { 274 listRelease(copy); 275 return NULL; 276 } 277 } 278 return copy; 279 }
