单向链表
单向链表是一种顺序存储结构,物理层面是一段地址不一定连续的存储空间
链表的头指针标志着链表的起始位置
结点是链表的最小单位,每个结点都有有唯一指向
存储结构
结点用结构体表示,由存储的数据data和指向下一个结构体的指针域组成
在头结点中,data用于表示链表的结点个数
在非头结点中,data存放数据元素
1 2 3 4 5
| typedef struct Node { int data; struct Node* next; }Node;
|
链表初始化
链表节点数为0,头结点指针域指向空,头结点的data域为零
1 2 3 4 5 6 7
| struct Node* InitList() { struct Node* L=(struct Node*)malloc(sizeof(struct Node)); L->next=NULL; L->data=0; return L; }
|
头插法和尾插法
头插法:在链表头结点之后进行插入
给定一个序列1,2,3,4,5使用头插法进行插入,得到的链表序列为5,4,3,2,1
1 2 3 4 5 6 7 8 9
| void HeadInsert(struct Node* L,int data) { struct Node* p=(struct Node*)malloc(sizeof(struct Node)); p->data=data; p->next=L->next; L->next=p; L->data++; }
|
尾插法
通过逐个访问链表结点,将指针定位到链表的尾部,在尾部进行插入操作
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| void TailInsert(struct Node* L,int data) { struct Node* p=L; struct Node* node=(struct Node*)malloc(sizeof(struct Node)); node->data=data; node->next=NULL; while(p->next!=NULL) { p=p->next; } p->next=node; L->data++;
}
|
链表的删除操作
按索引删除时
index变量用于记录当前指针指向结点的索引,当前索引值等于要删除结点的索引值时进行删除操作
通过将当前结点的前驱结点指针域指向当前结点的后继结点完成删除操作,
使用双指针pre和cur分别记录当前结点的前驱结点和当前结点,以便进行删除
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| Status DeleteKth(struct Node* L,int k) { int index=0; struct Node* pre=L; struct Node* cur=L->next; if(k>(L->data)){ printf("k out of range\n"); return ERROR; } while(cur!=NULL){ if(index==k){ pre->next=cur->next; L->data--; free(cur); return OK; } else{ index++; pre=cur; cur=cur->next; } } return OK; }
|
按值删除
在遍历结点过程中,如果当前结点的值等于要删除结点值时,改变当前结点的前驱结点指针域
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| Status DeleteValue(struct Node* L,int value) { struct Node* pre=L; struct Node* cur=L->next; while(cur!=NULL){ if(cur->data==value){ pre->next=cur->next; L->data--; free(cur); return OK; } else{ pre=cur; cur=cur->next; } } printf("not find the node value equal %d\n",value); return ERROR;
}
|
链表的插入操作
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| Status InsertValBefore(struct Node* L,int value,int data) { struct Node* pre=L; struct Node* cur=L->next; struct Node* node=(struct Node*)malloc(sizeof(struct Node)); node->data=data; node->next=NULL; while(cur!=NULL){ if(cur->data==value){ node->next=cur; pre->next=node; L->data++; return OK; } else{ pre=cur; cur=cur->next; } } printf("not the node value equ %d\n",value); free(node); return ERROR; }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| Status InsertValAfter(struct Node* L,int value,int data) { struct Node* p=L->next; struct Node* node=(struct Node*)malloc(sizeof(struct Node)); node->next=NULL; node->data=data; while(p!=NULL) { if(p->data==value){ node->next=p->next; p->next=node; L->data++; return OK; } else{ p=p->next; } } printf("can not find the node value equal %d\n",value); free(node); return ERROR; }
|
链表的遍历
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| Status PrintList(struct Node* L) { struct Node* node=L->next; if(node==NULL){ printf("list is empty\n"); return ERROR; } printf("node number is %d ",L->data); while(node){ printf("%d->",node->data); node=node->next; } printf("NULL\n"); return OK; }
Status RecurPrint(struct Node* node) { if(node==NULL){ printf("NULL\n"); return OK; } printf("%d->",node->data); RecurPrint(node->next); return OK; }
Status RecurReversePrint(struct Node* node) { if(node==NULL){ return OK; } RecurReversePrint(node->next); printf("%d->",node->data); return OK; }
|
清空链表
1 2 3 4 5 6 7 8 9 10 11
| Status FreeList(struct Node* L) { struct Node* cur=L->next; while(cur!=NULL){ struct Node* temp=cur; cur=cur->next; free(temp); } L->next=NULL; return OK; }
|
单向循环链表
链表结构
1 2 3 4 5
| typedef struct Node { int data; struct Node* next; }Node;
|
初始化
1 2 3 4 5 6 7
| struct Node* InitList() { struct Node* L=(struct Node*)malloc(sizeof(struct Node)); L->next=L; L->data=0; return L; }
|
头插法和尾插法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| void HeadInsert(struct Node* L,int data) { struct Node* node=(struct Node*)malloc(sizeof(struct Node)); node->data=data; node->next=L->next; L->next=node; L->data++; } void TailInsert(struct Node* L,int data) { struct Node* tail=L; struct Node* node=(struct Node*)malloc(sizeof(struct Node)); node->data=data; while(tail->next!=L) { tail=tail->next; } node->next=L; tail->next=node; L->data++; }
|
删除操作
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| Status DeleteVal(struct Node* L,int value) { Node* pre=L; Node* cur=L->next; while(cur!=L){ if(cur->data==value){ pre->next=cur->next; free(cur); L->data--; return OK; } pre=cur; cur=cur->next; } printf("cant not find the value equal %d in the linklist\n",value); return ERROR; }
|
遍历链表
1 2 3 4 5 6 7 8 9 10
| void PrintList(struct Node* L) { struct Node* node=L->next; printf("L->"); while(node!=L){ printf("%d->",node->data); node=node->next; } printf("L\n"); }
|
插入数据
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| Status InsertNodeAfterVal(struct Node* L,int value,int node_data) { struct Node* cur=L->next; struct Node* node=(struct Node*)malloc(sizeof(struct Node)); node->data=node_data; while(cur!=L){ if(cur->data==value){ node->next=cur->next; cur->next=node; return OK; } cur=cur->next; } printf("cant not find the value equal %d in the linklist\n",value); free(node); return ERROR; }
|
双向链表
链表结构
1 2 3 4 5
| typedef struct Node{ struct Node* pre; int data; struct Node* next; }Node;
|
链表初始化
1 2 3 4 5 6 7 8
| struct Node* InitList() { struct Node* L=(struct Node*)malloc(sizeof(struct Node)); L->pre=NULL; L->next=NULL; L->data=0; return L; }
|
头插法和尾插法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| void HeadInsert(struct Node*L,int data) { struct Node* node=(struct Node*)malloc(sizeof(struct Node)); node->data=data; if(L->next==NULL){ node->pre=L; node->next=L->next; L->next=node; } else{ node->next=L->next; node->pre=L; L->next->pre=node; L->next=node; } L->data++; } void TailInsert(struct Node* L,int data) { struct Node* node=L->next; struct Node* new_node=(struct Node*)malloc(sizeof(struct Node)); new_node->data=data; new_node->next=NULL; while(node->next){ node=node->next; } node->next=new_node; new_node->pre=node; L->data++; }
|
遍历链表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| void PrintList(struct Node* L) { struct Node* node=L->next; printf("L<=>"); while(node){ printf("%d<=>",node->data); node=node->next; } printf("NULL\n"); } void ReversePrintList(struct Node* L) { struct Node* node=L->next; while(node->next){ node=node->next; } while(node!=L){ printf("%d->",node->data); node=node->pre; } printf("L\n"); }
|
删除
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| int Delete(struct Node* L,int data) { struct Node* node=L->next; while(node){ if(node->data==data){ (node->next)->pre=node->pre; (node->pre)->next=node->next; free(node); L->data--; return 1; } node=node->next; } return 0; }
|
linux内核链表
链表
linux中的链表将数据域与指针域进行分离。
通过list_head怎么访问其他成员变量?
这就要依靠container_of宏了。指针域相对于结构体首地址的偏移量是固定的
指针域地址-相当偏移地址=结构体首地址。偏移量求解的办法offset
宏
1 2 3
| #define container_of(ptr,type,member) \ const typeof((type *)0->member) *_ptr=(ptr); \ (type *)((char *)_ptr-offset(type,member))
|
offset是内置的函数,也可以用上面的方法实现
1
| #define offset(type,member) (unsigned long)(&(type)(0)->member)
|
使用0地址作为结构体的起始地址,成员的地址就是相对与0号地址的偏移地址
链表头
静态创建链表头
1 2 3 4
| struct Node Head{ .data=data; .list=List_Head_Init(Head.list), }
|
动态创建链表头
1 2 3
| struct Node* HeadNode=malloc() Head->data; List_Head_Init(Head->list);
|
添加节点
在某一位置插入
1
| list_add(struct list_head *new,struct list_head *head)
|
在尾部插入
1
| list_add_tail(struct list_head *new,struct list_head *head);
|
删除节点
1
| list_del(struct list_head *entry)
|
具体实现
1 2 3 4 5 6 7
| 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); }
|
是否为空
1
| list_empty(struct list_head *head);
|
遍历链表
p表示循环中的临时变量,list表示遍历的起始位置
遍历实体
可以这样遍历
1 2 3 4
| list_for_each(p,list){ entry=list_entry() }
|
进行封装
1 2 3 4 5 6 7
|
list_for_each_entry(pos,head,member)
|
1 2 3
| list_for_each_entry(pos,head,member){ printf(pos->member) }
|
反向遍历链表
1
| list_for_each_reverse(pos,head,member)
|
线程安全的链表