概述

链表是一种比较基础的数据结构，主要在插入和删除时效率较高。Redis实现的是双向链表。

数据结构

listNode是链表的节点，有头指针和尾指针

1
2
3
4
5
typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

list是链表结构，有链表头、尾节点和链表长度属性，还有3个函数。

1
2
3
4
5
6
7
8
typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned long len;
} list;

函数

创建 listCreate

1
2
3
4
5
6
7
8
9
10
11
12
13
list *listCreate(void)
{
    struct list *list;

    if ((list = zmalloc(sizeof(*list))) == NULL)
        return NULL;
    list->head = list->tail = NULL;
    list->len = 0;
    list->dup = NULL;
    list->free = NULL;
    list->match = NULL;
    return list;
}

拷贝 listDup

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
list *listDup(list *orig)
{
    list *copy;
    listIter iter;
    listNode *node;

    if ((copy = listCreate()) == NULL)
        return NULL;
    copy->dup = orig->dup;
    copy->free = orig->free;
    copy->match = orig->match;
    listRewind(orig, &iter);
    while((node = listNext(&iter)) != NULL) {
        void *value;

        if (copy->dup) {
            value = copy->dup(node->value);
            if (value == NULL) {
                listRelease(copy);
                return NULL;
            }
        } else
            value = node->value;
        if (listAddNodeTail(copy, value) == NULL) {
            listRelease(copy);
            return NULL;
        }
    }
    return copy;
}

其它函数

  1. list *listCreate(void); 创建空链表
  2. void listRelease(list *list); 释放链表
  3. void listEmpty(list *list); 清空链表
  4. list listAddNodeHead(list list, void *value); 链表头添加节点
  5. list listAddNodeTail(list list, void *value); 链表尾添加节点
  6. list listInsertNode(list list, listNode old_node, void value, int after); 链表中插入节点
  7. void listDelNode(list list, listNode node); 删除节点
  8. listIter listGetIterator(list list, int direction); 获得链表迭代器
  9. listNode listNext(listIter iter); 下一个节点
  10. void listReleaseIterator(listIter *iter); 释放迭代器
  11. list listDup(list orig); 拷贝链表
  12. listNode listSearchKey(list list, void *key); 根据key查找节点
  13. listNode listIndex(list list, long index); 根据index获取节点
  14. void listRewind(list list, listIter li); 生成迭代器
  15. void listRewindTail(list list, listIter li); 生成尾迭代器
  16. void listRotate(list *list); 尾节点转为头节点
  17. void listJoin(list l, list o); 链表连接