• 2.4 双链表


    欢迎访问我的博客地址 : 博客地址

    关于双端链表

    双端链表也叫双向链表或双链表,它是一种非常实用的数据结构。单链表的节点只有一个指针域,且指向下一个节点,而双链表则有两个指针域,分别指向直接前驱和直接后继。同时也意味着,表头和表尾都能方便的进行插入和删除的操作,进而能轻易同时实现队列的功能。

    双端链表的实现

    双链表的表示

    双链表可以用表示链表节点的list_node和表示链表本身的list两个结构体来表示。下面的代码,参考了redis的双端链表

    ![list.png][1]

    /* 链表节点 */
    typedef struct list_node 
    {   
        /* 前驱节点 */
        struct list_node *prev;
        /* 后继节点 */
        struct list_node *next;
        /* 值 */
        void *value;
    } list_node;
    
    /* 链表 */
    typedef struct list
    {   
        /* 表长度 */
        unsigned long length;
        /* 表头 */
        list_node *head;
        /* 表尾 */
        list_node *tail;
    } list;
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    1. 链表节点(list_node)带有prevnext两个指针,这意味着,可以从表头到表尾或表尾到表头两个方向遍历或迭代链表。
    2. 链表本身(list)和队列(queue)类似,维护headtail两个指针,这意味着,在表头或者表尾的插入的复杂度为O(1),而单链表在表尾执行插入操作时,需要从表头遍历到表尾后插入,复杂度为O(n)。

    函数清单

    下面是用于操作队列的函数名及其作用与复杂度

    函数作用算法复杂度
    list_create创建新链表O(1)
    list_empty清空链表节点,但不清除链表本身O(N)
    list_release清除整个链表O(N)
    list_add_node_head在表头添加一个节点O(1)
    list_add_node_tail在表尾添加一个节点O(1)
    list_get_value_head获取表头节点数据O(1)
    list_get_value_tail获取表尾节点数据O(1)
    list_del_node删除一个节点O(1)
    list_get_iterator创建一个迭代器O(1)
    list_release_iterator释放迭代器O(1)
    list_next获取迭代器下一个节点值O(1)

    双链表的创建

    /* 创建链表 */
    list *list_create(void)
    {
        /* 创建链表 */
        list *list = (struct list *)malloc(sizeof(struct list));
        if(list==NULL) return NULL;
        
        /* 初始化链表 */
        list->head = list->tail = NULL;
        list->length = 0;
        
        return list;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-p6DIU9vw-1660706404254)(/images/list_create.png)]][2]

    表头插入操作

    /* 添加一个节点在链表头部 */
    list * list_add_node_head(list *list, void *value)
    {   
        /* 新建一个链表节点 */
        list_node *node = (list_node *)malloc(sizeof(list_node));
        if(node==NULL) return NULL;
        node->value = value;
        /* 如果链表为空 */
        if(list->length == 0) {
            list->head = list->tail = node;
            node->prev = node->next = NULL;
        }else {
            /* 设置新节点 */
            node->prev = NULL;
            node->next = list->head;
            /* 设置链表 */
            list->head->prev = node;
            list->head = node;
        }
        list->length++;
        return list;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    首先,创建一个新的链表节点。
    然后,判断双链表的长度,也即判断双链表是否为空。
    如果为空,则让链表的头尾指针headtail都指向该新节点,且新节点(node)指向前驱节点的指针prev和指向后继节点的指针next都设置为NULL

    ![list_insert2.png][3]

    如果不为空,则说明链表中已有节点存在。
    此时,先设置新节点,指针prev置为NULL,指针next指向链表头指针(head)指向的节点,也即表头节点。
    然后让头指针指向的节点的prev指针指向新节点。
    最后,将指针head指向新节点。

    ![list_insert.png][4]

    执行完节点的插入操作后,别忘了让链表长度自增1。

    表尾插入操作

    /* 添加一个节点在链表尾部 */
    list * list_add_node_tail(list *list, void *value)
    {
        /* 新建一个链表节点 */
        list_node *node = (list_node *)malloc(sizeof(list_node));
        if(node==NULL) return NULL;
        node->value = value;
        if(list->length==0) {
            list->head = list->tail = node;
            node->prev = node->next = NULL;
        } else {
            node->prev = list->tail;
            node->next = NULL;
            list->tail->next = node;
            list->tail = node;
        }
        list->length++;
        return list;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    首先,也要创建一个新的链表节点。
    接着也需要判断链表是否为空,如果是,则与链表为空时表头的插入操作相同。
    否则,让新节点prev指向链表表尾节点,next置为NULL
    然后,链表的tail->next指向新节点,表尾指针tail指向新节点。
    最后,插入完成,链表长度自增1。

    ![list_insert3.png][5]

    节点的删除

    /* 删除一个节点 */
    void list_del_node(list *list, list_node *node)
    {   
        /* 判断该节点是否有直接前驱 */
        if (node->prev)
            node->prev->next = node->next;
        else
            list->head = node->next;
        
        /* 判断该节点是否有直接后继 */
        if (node->next)
            node->next->prev = node->prev;
        else
            list->tail = node->prev;
        
        /* 释放该节点 */
        free(node);
        list->length--;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    该方法主要用于从表头或者表尾获取数据后对其节点的删除操作。

    首先判断该节点是否有直接前驱,如果有,则将直接前驱的next指针指向该节点的直接后继。如果没有,则说明该节点是首元节点,位于表头,将表头指针指向该节点的直接后继即可。

    接着是判断该节点是否有直接后继,如果有,则将该节点的直接后继的prev指针指向该节点的直接前驱。如果没有,则说明该节点位于表尾,将表尾指针指向该节点的直接前驱即可。 、

    最后释放该节点的内存,并将链表长度自减1。

    返回表头或表尾数据

    /* 获取表头数据 */
    void *list_get_value_head(list *list)
    {
        if(list->head == NULL) return NULL;
        /* 临时创建一个变量保存数据 */
        void *value = list->head->value;
        /* 删除该节点 */
        list_del_node(list, list->head);
        return value;
    }
    
    /* 获取表尾数据 */
    void *list_get_value_tail(list *list)
    {
        if(list->tail == NULL) return NULL;
        void *value = list->tail->value;
        list_del_node(list, list->tail);
        return value;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    由于list有表头和表尾指针,所以获得其数据也非常方便。

    链表的释放与清除

    /* 清空链表中所有的节点但是不删除链表本身 */
    void list_empty(list *list)
    {
        unsigned long length;
        list_node *current, *next;
        current = list->head;
        length = list->length;
        while (length--)
        {
            next = current->next;
            free(current);
            current = next;
        }
        list->head = list->tail = NULL;
        list->length = 0;
    }
    
    /* 释放整个链表 */
    void list_release(list *list)
    {
        list_empty(list);
        free(list);
    }
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    在清除链表所有节点时,我们从表头根据链表长度遍历到表尾逐个清除,最后使链表headtail指针为NULL
    释放整个链表只需要先清除该链表节点,再释放该链表本身即可。

    链表迭代器的实现

    宏定义迭代器方向

    #define LIST_START_HEAD 0
    #define LIST_START_TAIL 1
    
    • 1
    • 2

    其中LIST_START_HEAD表示沿着节点的next指针前进,从表头到表尾遍历。
    LIST_START_TAIL则表示,沿着节点的prev指针前进,从表尾到表头遍历。

    迭代器的表示

    /* 迭代器结构 */
    typedef struct list_iter
    {
        /* 下一个节点 */
        list_node *next;
        /* 方向 */
        int direction;
    }list_iter;
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    迭代器定义了两个成员,其中next是表示指向下一个节点的指针,direction表示迭代方向,对应上方的宏定义。

    迭代器的创建

    /* 创建一个迭代器 */
    list_iter *list_get_iterator(list *list, int direction)
    {
        list_iter *iter = (list_iter *) malloc(sizeof(list_iter));
        if(iter==NULL) return NULL;
        /* 判断迭代方向 */
        if(direction == LIST_START_HEAD)
            iter->next = list->head;
        else 
            iter->next = list->tail;
        iter->direction = direction;
        return iter;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    在初始化迭代器时,接受两个参数,分别是需要迭代的链表,和迭代的方向。
    判断给定参数,如果从表头遍历到尾遍历,则将迭代器的next指针指向链表的表头,反之则指向表尾。

    获取迭代器的下一个数据

    /* 返回链表下一个节点值 */
    void *list_next(list_iter *iter)
    {
        list_node *current = iter->next;
        if (current==NULL) return NULL;
    
        if(iter->direction == LIST_START_HEAD)
            iter->next = current->next;
        else 
            iter->next = current->prev;
    
        return current->value;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    在获取迭代器的下一个数据时,首先判断当前迭代器next指针指向的节点是否为空,如果空,则返回NULL
    接着迭代器next指针根据迭代方向指向下一个节点。
    最后返回数据。

    迭代器的释放

    /* 释放迭代器内存 */
    void list_release_iterator(list_iter *iter)
    {
        free(iter);
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5

    释放迭代器,还是挺简单的。

    在main方法中测试

    int main() 
    {   
        /* 测试数据 */
        char a = 'A';
        char b = 'B';
        char c = 'C';
    
        /* 创建链表 */
        list *list = list_create(); 
        
        /* 测试空表是否报错 */
        printf("-----测试空链表是否报错\n");
        printf("%p\n", list_get_value_head(list));
        printf("%p\n", list_get_value_tail(list));
    
        /* 表头添加数据 */
        list_add_node_head(list, &a);
        list_add_node_head(list, &b);
        /* 表尾添加数据 */
        list_add_node_tail(list, &c);
        list_add_node_tail(list, &a);
    
        printf("-----此时链表长度:%d\n", list->length);
        printf("-----测试表头出队-----\n");
        /* 先出队两次,测试表头出队 */
        while (list->length>2)
        {   
            printf("%c\n", *(char*)list_get_value_head(list));
        }
        printf("-----测试表尾出队-----\n");
        /* 测试表尾出队 */
        while (list->length)
        {   
            printf("%c\n", *(char*)list_get_value_tail(list));
        }
    
        /* 添加数据 */
        list_add_node_head(list, &a);
        list_add_node_head(list, &b);
        list_add_node_head(list, &c);
    
        /* 创建一个正向迭代器迭代器 */
        list_iter *iter = list_get_iterator(list, LIST_START_HEAD);
        /* 测试迭代器 */
        printf("-----测试迭代器-------\n");
        printf("%c\n", *(char *)list_next(iter));
        printf("%c\n", *(char *)list_next(iter));
    
        /* 释放迭代器 */
        list_release_iterator(iter);
    
        /* 清除链表节点 */
        list_empty(list);
        
        printf("-----测试空链表是否报错\n");
        printf("%p\n", list_get_value_head(list));
        printf("%p\n", list_get_value_tail(list));
    
        /* 释放链表 */
        list_release(list);
    
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63

    编译并输出:

    # gcc -fsanitize=address -fno-omit-frame-pointer  -g list.c  && ./a.out
    -----测试空链表是否报错
    (nil)
    (nil)
    -----此时链表长度:4
    -----测试表头出队-----
    B
    A
    -----测试表尾出队-----
    A
    C
    -----测试迭代器-------
    C
    B
    -----测试空链表是否报错
    (nil)
    (nil)
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
  • 相关阅读:
    SAS,Stata,HLM,R,SPSS和Mplus分层线性模型HLM分析学生受欢迎程度数据
    近年全球网络安全领域投融资整体特点
    前端 CSS 经典:SVG 描边动画
    java 咖啡餐厅管理系统Myeclipse开发mysql数据库web结构java编程计算机网页项目
    豪恩集团IPO过会:年营收9.8亿 应收账款价值超2亿
    【2022秋招面经】——NLP
    iOS——引用计数(一)
    使用Bigemap计算挖填土石方量
    有关BSP驱动该如何学习的个人看法
    sqlserver查询多个分类的最新时间数据
  • 原文地址:https://blog.csdn.net/qq_43699122/article/details/126382272