一、概述
Linux內核中大量使用了鏈表這個基本數據結構,因此有必要去窺探一下其“葫蘆裡賣的是什麼藥”。先來些基本知識點吧:
1.數據元素間是一對一關系;
2.鏈表中的元素個數是有限的;
3.同一表中各數據元素的類型和長度相同。
二、實現
先上代碼,有個感性的認識,後面再解釋。
#include<stdio.h>
#include<malloc.h>
//鏈表頭結構
struct list_head
{
struct list_head *next,*prev;
};
//#define LIST_HEAD_INIT(name) {&(name),&(name)}
//#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)
//鏈表頭初始化
void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}
//真正實現鏈表插入操作
void _list_add(struct list_head *nnew,struct list_head *prev,struct list_head *next)
{
next->prev = nnew;
nnew->next = next;
nnew->prev = prev;
prev->next = nnew;
}
//向鏈表插入一個節點
void list_add(struct list_head *nnew,struct list_head *head)
{
_list_add(nnew,head,head->next);
}
#define list_for_each(pos,head) \
for(pos = (head)->next;pos != (head);pos = pos->next)
#define list_for_each_safe(pos,n,head) \
for(pos = (head)->next,n = pos->next;pos != (head);pos = n,n = pos->next)
//根據節點中的一個成員在節點中的偏移量找到節點的起始地址
#define list_entry(ptr,type,member) \
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
//真正實現鏈表刪除操作
void _list_del(struct list_head *prev,struct list_head *next)
{
next->prev = prev;
prev->next = next;
}
//刪除鏈表中的一個節點
void list_del(struct list_head *entry)
{
_list_del(entry->prev,entry->next);
entry->next = NULL;
entry->prev = NULL;
}
////////////////////////////////////////////////////
//默認鏈表長度
#define N 10
//定義節點的數據結構
struct numlist
{
int num;//數據域
struct list_head list;//指針域
};
//定義鏈表頭節點
struct numlist numhead;
int main()
{
struct numlist *listnode;
struct list_head *pos;
struct numlist *p;
struct list_head *t;
int i;
//初始化鏈表頭節點
INIT_LIST_HEAD(&numhead.list);
for(i=0;i<N;i++)
{
//為新節點分配內存
listnode = (struct numlist *)malloc(sizeof(struct numlist));
//為節點數據域賦值
listnode->num = i;
//將該節點插入到鏈表中
list_add(&listnode->list,&numhead.list);
printf("Node %d has been added to doublelist\n",i);
}
printf("\n\n\n\n");
//遍歷鏈表
list_for_each(pos,&numhead.list)
{
i--;
//找出一個節點
p = list_entry(pos,struct numlist,list);
printf("Node %d's data: %d\n",i,p->num);
}
list_for_each_safe(pos,t,&numhead.list)
{
//刪除節點
list_del(pos);
p = list_entry(pos,struct numlist,list);
//釋放節點的內存
free(p);
}
return 0;
}