一、双向链表相比于单向链表增加一个指针域保存前驱结点的地址方便向前或者向后索引。1.双向链表数据类型的构造typedef struct stu { char name[32]; int age; int score; }Date_t; typedef struct dnote { Date_t date; struct dnote *pnetx; struct dnote *ppre; }Dnote_t; typedef struct dlink { Dnote_t *phead; int clen; }Dlink_t;2.双向链表的头插int insert_dlink_head(Dlink_t *pdlink,Date_t date) { Dnote_t *pinsert malloc(sizeof(Dnote_t)); if(NULL pinsert) { printf(malloc error\n); return -1; } pinsert-date date; pinsert-pnetx NULL; pinsert-ppre NULL; if(is_empty_link(pdlink)) { pdlink-phead pinsert; } else { pinsert-pnetx pdlink-phead; pdlink-phead-ppre pinsert; pdlink-phead pinsert; } pdlink-clen; return 0; }3.双向链表的尾插int insert_dlink_tail(Dlink_t *pdlink,Date_t date) { Dnote_t *pinsert malloc(sizeof(Dnote_t)); Dnote_t *ptmp NULL; if(NULL pinsert) { printf(malloc error\n); return -1; } pinsert-date date; pinsert-pnetx NULL; pinsert-ppre NULL; if(is_empty_link(pdlink)) { pdlink-phead pinsert; } else if (NULL pdlink-phead-pnetx) { pinsert-pnetx NULL; pdlink-phead-pnetx pinsert; pinsert-ppre pdlink-phead; } else { ptmp pdlink-phead; while(NULL ! ptmp-pnetx) { ptmp ptmp-pnetx; } pinsert-pnetx NULL; ptmp-pnetx pinsert; pinsert-ppre ptmp; } pdlink-clen; return 0; }4.双向链表的头删int delete_link_head(Dlink_t *pdlink) { Dnote_t *pfree NULL; if(is_empty_link(pdlink)) { return -1; } pfree pdlink-phead; if(NULL pdlink-phead-pnetx) { pdlink-phead NULL; } else { pdlink-phead pfree-pnetx; pfree-pnetx-ppre NULL; } free(pfree); pdlink-clen--; return 0; }5.双向链表的尾删int delete_link_tail(Dlink_t *pdlink) { Dnote_t *pfree NULL; if(is_empty_link(pdlink)) { return -1; } pfree pdlink-phead; if(NULL pdlink-phead-pnetx) { pdlink-phead NULL; } else { while(NULL ! pfree-pnetx) { pfree pfree-pnetx; } pfree-ppre-pnetx NULL; } free(pfree); pdlink-clen--; return 0; }6.双向链表的遍历void show_dlink(Dlink_t *pdlink, int dir) { if(is_empty_link(pdlink)) { return ; } Dnote_t *ptmp NULL; ptmp pdlink-phead; if(dir) { while(ptmp ! NULL) { printf(%s %d %d \n,ptmp-date.name,ptmp-date.age,ptmp-date.score); ptmp ptmp-pnetx; } } else { while(ptmp-pnetx ! NULL) { ptmp ptmp-pnetx; } while(ptmp ! NULL) { printf(%s %d %d \n,ptmp-date.name,ptmp-date.age,ptmp-date.score); ptmp ptmp-ppre; } } printf(\n); return ; }7.双向链表的查找Dnote_t *find_select_age_dlink(Dlink_t *pdlink, int age) { if(is_empty_link(pdlink)) { return NULL; } Dnote_t *ptmp NULL; ptmp pdlink-phead; while(NULL ! ptmp) { if(age ptmp-date.age) { return ptmp; } ptmp ptmp-pnetx; } return NULL; }8.双向链表的修改void find_name_modify_score(Dlink_t *pdlink,char *pname,int nscore) { if(is_empty_link(pdlink)) { return ; } Dnote_t *ptmp NULL; ptmp pdlink-phead; while(NULL ! ptmp) { if(strcmp(ptmp-date.name,pname) 0) { ptmp-date.score nscore; } ptmp ptmp-pnetx; } return ; }二、内核链表Linux内核中使用到的一种链表形式。本质双向循环链表和普通链表得区别1.普通链表将数据存储在结点中程序中一点确定了结点中存储得数据得数据类型该链表再无法存储其他类型的数据。2.内核链表将结点嵌入到要存储的数据结构体中在项目工程中一套链表操作可以用来存储不同类型的数据。内核提供宏offsetof:获取链表结点首地址到结构体开头的偏移量。container_of利用结点的首地址-偏移量获得结构体首地址。
)
