菜鸟从Redis源码学习C语言之Redis双向链表

双向链接是C语言中常用的一种数据结构,是链表的一种。链表由若干个结点组成。

相关文件:adlist.h,adlist.c

其结构如下:

一、双向链接相关结构体的声明

1、链表结点

组成链表的基本组成单元(可以称为链表元素)

  1. typedef struct listNode {
  2. struct listNode *prev;
  3. struct listNode *next;
  4. void *value;
  5. } listNode;
  • prev是指向前一个结点的指针(前一个结点也称前驱结点)

  • next是指向下一个结点的指针(下一个结点也称后继结点)

  • value是指向结点存储内容的指针

2、链表迭代器

它存储了链表的位置(当前指向哪个元素)

  1. typedef struct listIter {
  2. listNode *next;
  3. int direction;
  4. } listIter;
  • next表示指向的链接结点指针

  • direction为指针的移动方向(是从表头开始还是从表尾开始,0表示从表头开始)

3、双向链表

链表将所以链表结点通过一定的规则连接在一起

  1. typedef struct list {
  2. listNode *head;
  3. listNode *tail;
  4. void *(*dup)(void *ptr);
  5. void (*free)(void *ptr);
  6. void (*match)(void *ptr, void *key);
  7. unsigned long len;
  8. } list;
  • head:为表头指针

  • tail:为表尾指针

  • len:为表长度,即结点个数

  • dup:表结点复制函数

  • free:表结点释放函数

  • match:表结点比较函数(搜索匹配)

二、双向链接的操作

1、创建双向链表

作用:为链表申请分配内存空间,初始化其成员属性

  1. list *listCreate()
  2. {
  3. //声明一个链表指针lst
  4. struct list *lst;
  5. //为链表指针分配内存空间
  6. lst = (list *)malloc(sizeof(struct list));
  7. //如果内存分配失败
  8. if (lst == NULL) {
  9. return NULL;
  10. }
  11. //因为只是空表,所以表头和表尾指向NULL
  12. lst->head = lst->tail = NULL;
  13. //表长度为0
  14. lst->len = 0;
  15. return lst;
  16. }

这是一个创建双向链表的通用方法,与redis的实现类似(去掉了Redis中的初始化dup等成员的值,还有内存分配与C默认的内存分配有些不一样,但原理是一样的)

2、向双向链表中插入结点2、向双向链表中插入结点

插入结点的步骤:

  • 声明一个保存结点信息的指针变量node,并为指针申请并分配内存空间
  • 设置这个新结点的前驱和后继指针指向
  • 设置链表中该结点的位置(这个不是必须的)
  • 设置链表的长度(一般是自增)
  • 返回链表指针
(1)从表头位置中插入(1)从表头位置中插入
  • 原理:

把插入的新结点作为新的表头,如果原表是空表,则新结点既是表头,也是表尾,结点的前驱指针和后继指针都是NULL;如果原表是非空表,则新结点的前驱指针是NULL,后继指针是原来的表头指针,原来的表头指针的前驱指针是新插入的结点

  • 原理图:

代码:

  1. list *listAddHead(list *list, void *value)
  2. {
  3. struct listNode *node;
  4. node = malloc(sizeof(struct listNode));
  5. if (node == NULL) {
  6. return NULL;
  7. }
  8. node->value = value;
  9. //原来是空表
  10. if (list->len == 0) {
  11. list->head = list->tail = node;
  12. node->prev = node->next = NULL;
  13. } else {
  14. node->prev = NULL;
  15. node->next = list->head;
  16. list->head->prev = node;
  17. list->head = node;
  18. }
  19. list->len++;
  20. return list;
  21. }
(2)从表尾位置插入(2)从表尾位置插入
  • 原理:和在表头插入类似,把插入的新结点作为新的表尾,如果原表是空表,则新结点既是表头,也是表尾,结点的前驱指针和后继指针都是NULL;如果原表是非空表,则新结点的后继指针是NULL,姜胜允指针是原来的表尾指针,原来的表尾指针的后继指针是新插入的结点

  • 原理图:

代码:

  1. list *listAddTail(list *list, void *value)
  2. {
  3. struct listNode *node;
  4. node = malloc(sizeof(struct listNode));
  5. if (node == NULL) {
  6. return NULL;
  7. }
  8. node->value = value;
  9. if (list->len == 0) {
  10. node->prev = node->next = NULL;
  11. list->head = list->tail = node;
  12. } else {
  13. node->prev = list->tail;
  14. node->next = NULL;
  15. list->tail->next = node;
  16. list->tail = node;
  17. }
  18. list->len++;
  19. return list;
  20. }
(3)在某个结点的前面或后面插入(3)在某个结点的前面或后面插入
  • 原理:在某个结点(指定结点)的前面的插入新结点,则这个新结点的前驱结点为指定结点的前驱结点,新结点的后继结点为指定结点,如果指定结点为头结点,那么链表头结点为新结点;在某个结点(指定结点)的后面的插入新结点,则这个新结点的后继结点为指定结点的后继结点,新结点的前驱结点为指定结点,如果指定结点为尾结点,那么链表尾结点为新结点

  • 原理图:

代码:

  1. list *listInsert(list *list, listNode *oldNode, void *value, int after)
  2. {
  3. //用于保存新结点
  4. struct listNode *node;
  5. //分配内存空间
  6. node = malloc(sizeof(struct listNode));
  7. if (node == NULL) {
  8. return NULL;
  9. }
  10. node->value = value;
  11. if (after) {
  12. node->prev = oldNode;
  13. node->next = oldNode->next;
  14. oldNode->next = node;
  15. if (list->tail == oldNode) {
  16. list->tail = node;
  17. }
  18. } else {
  19. node->prev = oldNode->prev;
  20. node->next = oldNode;
  21. oldNode->prev = node;
  22. if (list->head == oldNode) {
  23. list->head = node;
  24. }
  25. }
  26. list->len++;
  27. return list;
  28. }
3、删除双向链表的结点
  • 原理:将删除结点的前驱结点的前驱结点的next指针指向删除结点的后继结点,将删除结点的后继结点的prev指针指向删除结点的前驱结点(当然要判断删除的结点是否是头尾结点),并释放结点的空间。

  • 原理图:

  • 代码:
  1. void listDelNode(list *list, listNode *node)
  2. {
  3. //判断删除的结点是否有前驱结点(是否是头结点)
  4. if (node->prev) {
  5. node->prev->next = node->next;
  6. } else {
  7. list->head = node->next;
  8. }
  9. if (node->next) {
  10. node->next->prev = next->prev;
  11. } else {
  12. list->tail = node->prev;
  13. }
  14. free(node);
  15. list->len--;
  16. }