双端链表

adlist.c .h

Redis 里的 List 是双端链表的模式

typedef struct listNode {

    // 前置节点
    struct listNode *prev;

    // 后置节点
    struct listNode *next;

    // 节点的值
    void *value;

} listNode;

/*
 * 双端链表构造
 */
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;

/*
 * 双端链表迭代器
 */
typedef struct listIter {

    // 以后迭代到的节点
    listNode *next;

    // 迭代的方向
    int direction;

} listIter;

/* Directions for iterators 
 *
 * 迭代器进行迭代的方向
 */
// 从表头向表尾进行迭代
#define AL_START_HEAD 0
// 从表尾到表头进行迭代
#define AL_START_TAIL 1

留神

1. 这里的表头和表尾的 next 都是指向 null 的所以永远无环
2. 链表节点是应用的 void* 指针来保留节点值的 所以链表能够保留各种不同类型的值

void 指针能够指向任意类型的数据，就是说能够用任意类型的指针对 void 指针赋值

int *a;
void *p
p=a;

#include <iostream>
using namespace std;
int main() {int b[] = {1,2};
    int* a = b;
    void *c;

    c = a;
    cout << c<<endl;
    cout << *a;

}

这里你是能够输入 c 的 c 存的就是指针 a 所村的 也就是 b 数组的内存地址，然而你是不能 *c 因为没有类型 void

API

指定地位插入

/*
 * 创立一个蕴含值 value 的新节点，并将它插入到 old_node 的之前或之后
 *
 * 如果 after 为 0，将新节点插入到 old_node 之前。* 如果 after 为 1，将新节点插入到 old_node 之后。*
 * T = O(1)
 */
list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
    listNode *node;

    // 创立新节点
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;

    // 保留值
    node->value = value;

    // 将新节点增加到给定节点之后
    if (after) {
        node->prev = old_node;
        node->next = old_node->next;
        // 给定节点是原表尾节点
        if (list->tail == old_node) {list->tail = node;}
    // 将新节点增加到给定节点之前
    } else {
        node->next = old_node;
        node->prev = old_node->prev;
        // 给定节点是原表头节点
        if (list->head == old_node) {list->head = node;}
    }

    // 更新新节点的前置指针
    if (node->prev != NULL) {node->prev->next = node;}
    // 更新新节点的后置指针
    if (node->next != NULL) {node->next->prev = node;}

    // 更新链表节点数
    list->len++;

    return list;
}

迭代器

/*
 * 为给定链表创立一个迭代器，* 之后每次对这个迭代器调用 listNext 都返回被迭代到的链表节点
 *
 * direction 参数决定了迭代器的迭代方向：*  AL_START_HEAD：从表头向表尾迭代
 *  AL_START_TAIL：从表尾想表头迭代
 *
 * T = O(1)
 */
listIter *listGetIterator(list *list, int direction)
{
    // 为迭代器分配内存
    listIter *iter;
    if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;

    // 依据迭代方向，设置迭代器的起始节点
    if (direction == AL_START_HEAD)
        iter->next = list->head;
    else
        iter->next = list->tail;

    // 记录迭代方向
    iter->direction = direction;

    return iter;
}

查找

/* 
 * 查找链表 list 中值和 key 匹配的节点。* 
 * 比照操作由链表的 match 函数负责进行，* 如果没有设置 match 函数，* 那么间接通过对比值的指针来决定是否匹配。*
 * 如果匹配胜利，那么第一个匹配的节点会被返回。* 如果没有匹配任何节点，那么返回 NULL。*
 * T = O(N)
 */
listNode *listSearchKey(list *list, void *key)
{
    listIter *iter;
    listNode *node;

    // 迭代整个链表
    iter = listGetIterator(list, AL_START_HEAD);
    while((node = listNext(iter)) != NULL) {
        
        // 比照
        if (list->match) {if (list->match(node->value, key)) {listReleaseIterator(iter);
                // 找到
                return node;
            }
        } else {if (key == node->value) {listReleaseIterator(iter);
                // 找到
                return node;
            }
        }
    }
    
    listReleaseIterator(iter);

    // 未找到
    return NULL;
}