双向链表,还能这么实现

举报
实力程序员 发表于 2021/06/09 09:18:32 2021/06/09
【摘要】 我找到一种双向链表的实现方式,不需要增加任何额外的空间,并且能彻底消除对NULL的判断。

双向链表,是一种常用的数据结构。在C语言中,双向链表的实现,通常采用下面的数据结构:

typedef struct dlist_node_t {
    struct dlist_node_t* pprev;
    struct dlist_node_t* pnext;
    void* pdata;
} dlist_node_t;

typedef struct dlist_t {
    dlist_node_t* phead;
    dlist_node_t* ptail;
} dlist_t;

dlist_t 是双向链表的数据结构,其有两个指针:一个指向头部节点,一个执行尾部节点。
每个节点,用dlist_node_t来表示,节点内部有三个成员:指向前一个节点的指针,指向下一个节点的指针,节点保存的数据指针。

向链表增加或删除节点时,都需要对指针是否为NULL进行判断,包括:判断dlist_t的头指针、尾指针是否为NULL,判断dlist_node_t的前向、后向指针是否为NULL,从而进行对应的处理,这样排列组合起来的场景是比较多的,因此代码实现逻辑比较繁琐。

为了避免判断NULL,简化代码,一些新的实现思路被提出。有人提议,把dlist_t的头尾指针,都改成dlist_node_t结构体,形成2个固定的哨兵,如下:

typedef struct dlist_t {
    dlist_node_t head;
    dlist_node_t tail;
} dlist_t;

这样dlist_t就没有NULL指针了,并且链表中的节点,前向和后向指针都一定不是NULL。这样代码实现就大大简化了。
这样的设计,只有head的前向指针、tail的后向指针为NULL,并且由于他们是哨兵,这两个NULL指针不需要修改,也不需要判断。

这种改进方案,唯一的不足,是dlist_t 数据结构占用的内存变大了,多消耗了4个指针的内存空间,即32个byte。


对于追求完美的开发者而言,这不应该是终极方案!

我找到一种双向链表的实现方式,不需要增加任何额外的空间,并且能彻底消除对NULL的判断。其核心设计思路为:
把 dlist_t 也看作是一个dlist_node_t,和链表内的dlist_node_t一起构成一个首尾相接的环形结构,从而消除NULL指针。

具体如下图所示:

2021-06-08_dlist.jpg

代码核心实现要点,如下:
1)数据结构dlist_t中的phead和ptail的位置需要对调。
2)dlist_t 初始化时,前向和后向指针都指向自己。
3)向dlist_t中增加、删除成员时,把双向链表看作是一个环状的双向链表,这个环上,每个节点的前向和后向指针都不是NULL,都可以访问和修改。

代码示例如下:
dlist.h 的内容如下:

// dlist.h
#ifndef DLIST_H
#define DLIST_H

typedef struct dlist_node_t {
    struct dlist_node_t* pprev;
    struct dlist_node_t* pnext;
    void* pdata;
} dlist_node_t;

typedef struct dlist_t {
    dlist_node_t* ptail;
    dlist_node_t* phead;
} dlist_t;

int dlist_init(dlist_t* plist);
int dlist_push_tail(dlist_t* plist, void* pdata);
int dlist_push_head(dlist_t* plist, void* pdata);

void* dlist_pop_tail(dlist_t* plist);
void* dlist_pop_head(dlist_t* plist);

// ...

#endif


dlist.c 的内容如下:

// dlist.c
#include "dlist.h"

#include <stdlib.h>

int dlist_init(dlist_t* plist) {
    plist->phead = (dlist_node_t*)plist;
    plist->ptail = (dlist_node_t*)plist;
    return 0;
}

int dlist_push_tail(dlist_t* plist, void* pdata) {
    // new node
    dlist_node_t* pnode = (dlist_node_t*)malloc(sizeof(*pnode));
    pnode->pdata = pdata;

    // tail node
    dlist_node_t* ptail = plist->ptail;

    // ring : insert as next node of the tail node
    pnode->pnext = ptail->pnext;
    ptail->pnext->pprev = pnode;
    pnode->pprev = ptail;
    ptail->pnext = pnode;

    return 0;
}

int dlist_push_head(dlist_t* plist, void* pdata) {
    // new node
    dlist_node_t* pnode = (dlist_node_t*)malloc(sizeof(*pnode));
    pnode->pdata = pdata;

    // head node
    dlist_node_t* phead = plist->phead;

    // ring : insert as prev node of the head node
    pnode->pprev = phead->pprev;
    phead->pprev->pnext = pnode;
    pnode->pnext = phead;
    phead->pprev = pnode;

    return 0;
}

void* dlist_pop_tail(dlist_t* plist) {
    if (plist->ptail == (dlist_node_t*)plist) {     // empty
            return NULL;
    }

    // remove tail node from dlist
    dlist_node_t* pnode = plist->ptail;
    pnode->pprev->pnext = pnode->pnext;
    pnode->pnext->pprev = pnode->pprev;

    // free node
    void* pdata = pnode->pdata;
    free(pnode);

    return pdata;
}

void* dlist_pop_head(dlist_t* plist) {
    if (plist->phead == (dlist_node_t*)plist) {     // empty
            return NULL;
    }

    // remove head node from dlist
    dlist_node_t* pnode = plist->phead;
    pnode->pprev->pnext = pnode->pnext;
    pnode->pnext->pprev = pnode->pprev;

    // free node
    void* pdata = pnode->pdata;
    free(pnode);

    return pdata;
}


测试程序 test_dlist.c 的内容如下:

#include "dlist.h"
#include <stdio.h>
#include <stdint.h>

int main() {
    dlist_t list, *plist = &list;
    int iret = dlist_init(plist);
    dlist_push_tail(plist, (void*)1);
    dlist_push_tail(plist, (void*)2);
    dlist_push_tail(plist, (void*)3);
    dlist_push_head(plist, (void*)4);
    dlist_push_head(plist, (void*)5);

    printf("%lu\n", (uint64_t)dlist_pop_head(plist));
    printf("%lu\n", (uint64_t)dlist_pop_head(plist));
    printf("%lu\n", (uint64_t)dlist_pop_head(plist));
    printf("%lu\n", (uint64_t)dlist_pop_head(plist));
    printf("%lu\n", (uint64_t)dlist_pop_head(plist));

    return 0;
}


运行 ./test_dlist, 输出结果如下:

$ ./test_dlist
5
4
1
2
3


我的微信号 "实力程序员",欢迎大家关注我。

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。