通用双向链表的设计(参考Linux系统中的实现)

简介: 通常我们设计设计链表都是将数据域放在里面,这样每次需要使用链表的时候都需要实现一个链表,然后重新实现它的相关操作,这里参考Linux系统中的设计实现了一个通用的双向链表,只需要在你的结构里面有一个这个链表的域,就可以使用链表的相关操作了。

通常我们设计设计链表都是将数据域放在里面,这样每次需要使用链表的时候都需要实现一个链表,然后重新实现它的相关操作,这里参考Linux系统中的设计实现了一个通用的双向链表,只需要在你的结构里面有一个这个链表的域,就可以使用链表的相关操作了。

注意:这个通用的双向链表是参考Linux系统中的实现,它使用了typeof这个功能,所以有些编译器可能不支持。我是再Windows系统中使用MinGW下使用GCC编译的。

////////////////////////////////////////////////////////////////////////////////////////

// list.h

 
#ifndef _list_h
#define _list_h
 
typedef struct _list_head {
    struct _list_head *prev,*next;
} list_head;
 
#define offsetof(TYPE,MEMBER) ( (size_t) &((TYPE*)0)->MEMBER )
 
#define container_of(ptr,type,member) ({\
    const typeof( ((type*)0)->member ) *__mptr = (ptr);\
    (type*)( (char*)__mptr - offsetof(type,member) );})
 
#define list_empty(head) ( head->next==0&&head->prev==0 )
 
/* get the member of list object
 * @ptr        pointer to list_head
 * @type    the type of container which contains list_head field
 * @memeber field name in the container
 * @return    return pointer to the container
 */
#define list_entry(ptr,type,member) container_of(ptr,type,member)
 
/* add a new node after `head`
 */
void list_add(list_head *head,list_head *node);
 
/* delete a node
 */
void list_del(list_head *node);
 
#endif

/////////////////////////////////////////////////////////

// list.c

#include "list.h"
 
/* add a new node after `head`
 */
void list_add(list_head *head,list_head *node) {
    if(list_empty(head)) {
        head->next = head;
        head->prev = head;
    }
    node->next = head->next;
    node->prev = head;
    head->next->prev = node;
    head->next = node;
}
/* delete a node
 */
void list_del(list_head *node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
}

///////////////////////////////////////////////////////////////////////////////

// test.c

#include <stdio.h>
#include <assert.h>
#include "list.h"
 
typedef struct _task {
    int id;
    list_head next;
} task;
 
#define task_next(t) ( container_of(t->next.next,task,next) )
 
void task_print(task *t) {
    printf("#%d -> ",t->id);
}
 
void task_foreach(task *head,void (*callback)(task *)) {
    task *p = head;
    do {
        callback(p);
        p = task_next(p);
    }
    while (p!=head);
}
 
// use task like a list
void test_list() {
    task t1={1,{0,0}},
        t2={2,{0,0}},
        t3={3,{0,0}},
        t4={4,{0,0}},
        t5={5,{0,0}};
 
    list_add(&t1.next,&t2.next);
    list_add(&t2.next,&t3.next);
    list_add(&t3.next,&t4.next);
    list_add(&t4.next,&t5.next);
 
    task_foreach(&t1,task_print);
}
 
int main(int argc, char *argv[]) {
    test_list();
 
    return 0;
}

编译运行

    gcc test.c list.h list.c -o test
    .\test.exe

下载代码

目录
相关文章
|
机器学习/深度学习 移动开发 Linux
linux通用双向链表
1, 基于linux4.9版本 #include #include #include #if 1 struct list_head { struct list_head *next, *prev; }; ...
929 0
|
Linux 机器学习/深度学习 C语言
linux内核源码“双向链表list_head”续
      上篇博文《linux内核源码“双向链表list_head”》中以一个实例介绍了list_head双向链表的用法,只有实例的代码,并没有list_head链表的代码,考虑到各位好学博友的强烈愿望,今天把list_head的代码即list.h头文件粘贴到此,供各位好学博友使用。
853 0
|
Linux
linux内核源码“双向链表list_head”
摘要:linux内核源码真是好东东,是众多高手思维的结晶,在linux 源代码中有个头文件为list.h 。很多linux 下的源代码都会使用这个头文件,它里面定义了一个结构, 以及定义了和其相关的一组函数,这个结构是这样的: struct list_head{ struct list_head *next, *prev; };         如果您之前学过双向链表,那么当你看到这个结构的时候,会觉得似曾相识。
1251 0
|
Linux C语言 C++
linux下c语言 双向链表
C/C++ code /*sgx 2008-10-30 c语言 双向链表*/#include #include #include #define TRUE 1;#define FALSE 0;typedef int ELEMTYPE;typedef struct DoubleLinkNode{...
765 0
|
27天前
|
Unix Linux 程序员
Linux文本搜索工具grep命令使用指南
以上就是对Linux环境下强大工具 `grep` 的基础到进阶功能介绍。它不仅能够执行简单文字查询任务还能够处理复杂文字处理任务,并且支持强大而灵活地正则表达规范来增加查询精度与效率。无论您是程序员、数据分析师还是系统管理员,在日常工作中熟练运用该命令都将极大提升您处理和分析数据效率。
103 16
|
18天前
|
Linux
linux命令—stat
`stat` 是 Linux 系统中用于查看文件或文件系统详细状态信息的命令。相比 `ls -l`,它提供更全面的信息,包括文件大小、权限、所有者、时间戳(最后访问、修改、状态变更时间)、inode 号、设备信息等。其常用选项包括 `-f` 查看文件系统状态、`-t` 以简洁格式输出、`-L` 跟踪符号链接,以及 `-c` 或 `--format` 自定义输出格式。通过这些选项,用户可以灵活获取所需信息,适用于系统调试、权限检查、磁盘管理等场景。
|
3月前
|
监控 Linux 网络安全
Linux命令大全:从入门到精通
日常使用的linux命令整理
668 13
|
4月前
|
Linux 网络安全 数据安全/隐私保护
使用Linux系统的mount命令挂载远程服务器的文件夹。
如此一来,你就完成了一次从你的Linux发车站到远程服务器文件夹的有趣旅行。在这个技术之旅中,你既探索了新地方,也学到了如何桥接不同系统之间的距离。
555 21
|
4月前
|
JSON 自然语言处理 Linux
linux命令—tree
tree是一款强大的Linux命令行工具,用于以树状结构递归展示目录和文件,直观呈现层级关系。支持多种功能,如过滤、排序、权限显示及格式化输出等。安装方法因系统而异常用场景包括:基础用法(显示当前或指定目录结构)、核心参数应用(如层级控制-L、隐藏文件显示-a、完整路径输出-f)以及进阶操作(如磁盘空间分析--du、结合grep过滤内容、生成JSON格式列表-J等)。此外,还可生成网站目录结构图并导出为HTML文件。注意事项:使用Tab键补全路径避免错误;超大目录建议限制遍历层数;脚本中推荐禁用统计信息以优化性能。更多详情可查阅手册mantree。
linux命令—tree