1. 列表节点
typedef struct listNode {
//前置节点struct listNode *prev;
//后置节点struct listNode *next;
//值void *value;
} listNode;
2.redis使用list持有链表
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;
3.链表特性总结:
a. 双端，节点有pre和next指针
b.无环
c.有头尾指针，链接获取头尾节点复杂度为O(1)
d.获取链表长度为O(1)
4.插入节点源码
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;}//节点长度加1list->len++;return list;
}