一個(gè)鏈表節(jié)點(diǎn)的結(jié)構(gòu)

typedef struct listNode {

    // 前置節(jié)點(diǎn)
    struct listNode *prev;

    // 后置節(jié)點(diǎn)
    struct listNode *next;

    // 節(jié)點(diǎn)的值
    void *value;

} listNode;

鏈表

/*
 * 雙端鏈表結(jié)構(gòu)
 */
typedef struct list {

    // 表頭節(jié)點(diǎn)
    listNode *head;

    // 表尾節(jié)點(diǎn)
    listNode *tail;

    // 節(jié)點(diǎn)值復(fù)制函數(shù)
    void *(*dup)(void *ptr);

    // 節(jié)點(diǎn)值釋放函數(shù)
    void (*free)(void *ptr);

    // 節(jié)點(diǎn)值對(duì)比函數(shù)
    int (*match)(void *ptr, void *key);

    // 鏈表所包含的節(jié)點(diǎn)數(shù)量
    unsigned long len;

} list;

Redis的鏈表

1. 雙端：鏈表節(jié)點(diǎn)帶有prev和next指針，獲得節(jié)點(diǎn)的前置或后置節(jié)點(diǎn)復(fù)雜福都是O(1)
2. 無(wú)環(huán)：表頭節(jié)點(diǎn)的prev指針和表尾節(jié)點(diǎn)的next指針都指向NULL
3. 帶鏈表長(zhǎng)度計(jì)數(shù)器