双端链表

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

留神

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

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

int *a;void *pp=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;}