PS：要转载请注明出处，本人版权所有。
PS: 这个只是基于《我自己》的理解，
如果和你的原则及想法相冲突，请谅解，勿喷。
前置说明
本文作为本人csdn blog的主站的备份。（BlogID=020）
本文发布于 2016-06-06 14:49:11，现用MarkDown+图床做备份更新。blog原图已丢失，使用csdn所存的图进行更新。（BlogID=020）
环境说明
无
前言
无
入侵式链表
链表按照实现原理我分为两类，一是普通的链表，二是入侵式链表。（区别就是，链表结构体里面有没有数据）。由于我重写了Linux 链表的实现，部分东西被我更改，所以文中代码以我的实际代码为例。
下面围绕几点来理解一下：
链表元素结构体声明：
//
typedef struct y_list_head {
struct y_list_head *next;
struct y_list_head *prev;
} Y_LISTHEAD;
节点元素结构体声明：
//
typedef struct {
int a;
Y_LISTHEAD list;
} test;
链表的头节点（用于存放一个链表的逻辑头，由于链表是双向，每个节点都是头）：
//declare a node for head of list .
#define LIST_HEAD(name) \
Y_LISTHEAD name = LIST_HEAD_INIT(name)
这里为了展示例子，我申请了几个变量:
test* ptr_test;
Y_LISTHEAD * pos;
test * entry;
为节点申请内存，并赋值
ptr_test = (test *)malloc(sizeof(test));
ptr_test->a = 0;
现在节点创建完毕，开始加入到链表
/*
* Insert a new entry between two known consecutive entries.
*
* This is only for internal list manipulation where we know
* the prev/next entries already!
*/
static inline void __list_add(Y_LISTHEAD *new,
Y_LISTHEAD *prev,
Y_LISTHEAD *next)
{
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;
}
/**
* list_add - add a new entry
* @new: new entry to be added
* @head: list head to add it after
*
* Insert a new entry after the specified head.
* This is good for implementing stacks.
*/
static inline void list_add(Y_LISTHEAD *new, Y_LISTHEAD *head)
{
__list_add(new, head, head->next);
}
LIST_ADD(&ptr_test->list,&test_list);
同理，在添加几个。（详情见末尾例子）,然后，遍历链表并输出：
// 这里解释一下 GET_ENTRY（）宏函数
//caculate offset-value about member to start of the struct
//计算结构体地址和结构体某成员的地址差值，也就是偏移值
#define OFFSET(type, member) ((unsigned int) &((type *)0)->member)
//第一行声明了一个结构体元素类型的指针
//第二行通过偏移值计算结构体地址，这样就可以得到结构体内所有元素的值
//第三个参数member 为节点元素中，链表变量名
//第二个参数为节点元素类型名
#define GET_ENTRY(ptr, type, member) \
({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - OFFSET(type,member) ); \
})
/**
* list_for_each iterate over a list
* @pos:the &struct list_head to use as a loop cursor.
* @head:the head for your list.
*/
#define LIST_FOR_EACH(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
LIST_FOR_EACH(pos,&test_list){
entry = GET_ENTRY(pos,test,list);
printf("%d\n",entry->a);
}
// 同理, LIST_DEL_ENTRY()之类的宏定义都是同样的实现。
实例:list_test.c
/*
* FileName:list_test.c
* Version: 1.0
* Description: The file test my list if it is right
* Created On:2016-5-15
* Modified date:
* Author:Sky
*
*/
#include <stdio.h>
#include "Y_List/Y_List.h"
typedef struct {
int a;
Y_LISTHEAD list;
} test;
test* ptr_test;
int main(int argc, char * argv[]){
//test head;
LIST_HEAD(test_list);
Y_LISTHEAD * pos;
test * entry;
//INIT_LIST_HEAD(head->list);
ptr_test = (test *)malloc(sizeof(test));
ptr_test->a = 0;
LIST_ADD(&ptr_test->list,&test_list);
ptr_test = (test *)malloc(sizeof(test));
ptr_test->a = 2;
LIST_ADD_TAIL(&ptr_test->list,&test_list);
ptr_test = (test *)malloc(sizeof(test));
ptr_test->a = 4;
LIST_ADD(&ptr_test->list,&test_list);
ptr_test = (test *)malloc(sizeof(test));
ptr_test->a = 8;
LIST_ADD_TAIL(&ptr_test->list,&test_list);
LIST_FOR_EACH(pos,&test_list){
entry = GET_ENTRY(pos,test,list);
printf("%d\n",entry->a);
}
LIST_DEL_ENTRY(&(ptr_test->list));
LIST_FOR_EACH(pos,&test_list){
entry = GET_ENTRY(pos,test,list);
printf("%d\n",entry->a);
}
LIST_FOR_EACH(pos,&test_list){
entry = GET_ENTRY(pos,test,list);
free(entry);
}
return 0;
}
// LIST_ADD在给出地址后添加一个元素
// LIST_ADD_TAIL在给出地址前添加一个元素
// LIST_DEL_ENTRY删除指定地址的节点
运行截图：
其实链表只有几个部分要主要：
-
链表结构体
-
节点结构体
-
链表头
-
链表增删改查
而在Linux的链表实现中，要注意下面这个东西，怎么确定的节点结构体地址，这是LInux链表实现的核心。搞清楚了这个，Ｌｉｎｕｘ链表你就会了GET_ENTRY（）
如果希望查看上面项目代码，移步:https://github.com/flyinskyin2013/Y_LINUX_FRAME/tree/master/include/Y_List
后记
无
参考文献
- 无
PS: 请尊重原创，不喜勿喷。
PS: 要转载请注明出处，本人版权所有。
PS: 有问题请留言，看到后我会第一时间回复。