[redis读书笔记] 第一部分数据结构与对象链表

二链表

1.链表节点使用ListNode结构，是一个双向的链表，同时，还实现了一个控制所有ListNode的结构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;

由list和listnode组成的基本结构如下，可见

- listNode里的prev和next构成双向列表

- list.head和list.tail使访问头尾node的复杂度为o(1)

- 头Node的prev和尾node的next指向NULL，不会成环

- list.len使访问list长度的复杂度为o(1)

- 多态：通过list.match，list.free和list.dup来实现多态，即支持各种类型的listnode.value

巴特西

[redis读书笔记] 第一部分数据结构与对象链表

最新文章

热门文章

巴特西

[redis读书笔记] 第一部分 数据结构与对象 链表

最新文章

热门文章

[redis读书笔记] 第一部分数据结构与对象链表