双向循环链表linux中C语言实现双向循环链表

查了好多资料，发现还是不全，干脆自己整理吧，至少保证在我的做法正确的，以免误导读者，也是给自己做个记录吧！

原创作者：南京邮电大学通信与信息系统专业研二魏清

阅读linux2.6.32.2中双向循环链表的实现，借鉴其内核代码，在应用层实现双向循环链表的建立，插入，删除，以及遍历操纵。包括两个文件，list.h是双向循环链表实现函数，test.c是其测试代码,有必定的参考价值！

list.h

#include <stdio.h>
#include <stdlib.h>

#define LIST_POISON1 ((void *) 0x00100100)
#define LIST_POISON2 ((void *) 0x00200200)

#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_entry(ptr, type, member) \
container_of(ptr, type, member)

static inline void prefetch(const void *addr)
{
//__asm__("ldw 0(%0), %%r0" : : "r" (addr)); //just aimed at improving the speed of iterating the list
}

    #define list_for_each_entry(pos, head, member)    \
for (pos = list_entry((head)->next, typeof(*pos), member); \
      prefetch(pos->member.next), &pos->member != (head); \
      pos = list_entry(pos->member.next, typeof(*pos), member))

struct list_head {
struct list_head *next, *prev;
};

static inline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}

每日一道理
巴尔扎克说过“不幸，是天才的进升阶梯，信徒的洗礼之水，弱者的无底深渊”。风雨过后，眼前会是鸥翔鱼游的天水一色；走出荆棘，前面就是铺满鲜花的康庄大道；登上山顶，脚下便是积翠如云的空蒙山色。在这个世界上，一星陨落，黯淡不了星空灿烂，一花凋零，荒芜不了整个春天。人生要尽全力度过每一关，不管遇到什么困难不可轻言放弃。

static inline void __list_add(struct list_head *new,
         struct list_head *prev,
         struct list_head *next)
{
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;
}
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}

static inline void __list_del(struct list_head * prev, struct list_head * next)
{
next->prev = prev;
prev->next = next;
}
static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}

static inline int list_empty(const struct list_head *head)
{
return head->next == head;
}

test.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"

struct student{
char *name;
int age;
struct list_head list;
};

int main()
{
struct student a={"lili",10},b={"wang",11},c={"du",12};
struct student *wq,*f;
wq=(struct student *)malloc(sizeof(struct student));
memset(wq,0,sizeof(struct student));
INIT_LIST_HEAD(&wq->list);
list_add(&a.list,&wq->list);
list_add(&b.list,&wq->list);
list_add(&c.list,&wq->list);
//list_del(&c.list);

f=(struct student *)malloc(sizeof(struct student));
memset(f,0,sizeof(struct student));
list_for_each_entry(f,&wq->list,list){
printf("name:%-10s age:%d\n",f->name,f->age);
}

free(wq);

wq=NULL;
return 0;
}

文章结束给大家分享下程序员的一些笑话语录：马云喜欢把自己包装成教主，张朝阳喜欢把自己包装成明星，李彦宏喜欢把自己包装成的很知性，丁磊喜欢把自己包装的有创意，李开复总摆出一副叫兽的样子。看来的。其实我想说，缺啥补啥，人之常情。