- (??? )，Hello我是祐言QAQ
- 我的博客主頁：C/C++語言,Linux基礎,ARM開發(fā)板，軟件配置等領域博主??
- 快上??，一起學習，讓我們成為一個強大的攻城獅！
- 送給自己和讀者的一句雞湯??：集中起來的意志可以擊穿頑石!
- 作者水平很有限，如果發(fā)現(xiàn)錯誤，可在評論區(qū)指正，感謝??
????????內核鏈表（Kernel Linked List）是操作系統(tǒng)內核中常用的一種數(shù)據(jù)結構，用于管理和維護一系列數(shù)據(jù)元素（節(jié)點）。它也是一種線性數(shù)據(jù)結構，其中每個節(jié)點包含了數(shù)據(jù)元素本身以及指向下一個節(jié)點的指針。內核鏈表在操作系統(tǒng)中廣泛應用于管理進程、文件描述符、內存分配等諸多場景。
一、內核鏈表概述
????????內核鏈表通常由一個特定的數(shù)據(jù)結構定義，該數(shù)據(jù)結構包含一個或多個指向鏈表中首個和最后一個節(jié)點的指針，以及其他用于操作和管理鏈表的屬性。在C語言中，內核鏈表的定義示例：
//數(shù)據(jù)
typedef int Datatype;
//節(jié)點（大結構體）
typedef struct Kernel_node
{
Datatype data; //數(shù)據(jù)域
struct kernel_list list; //指針域
}k_node;
//指針節(jié)點（小結構體）
struct kernel_list {
struct kernel_list *prev;//前驅指針
struct kernel_list *next;//后繼指針
};
? ? ? ? kernel_list結構體定義了一個內核鏈表的節(jié)點，其中prev指向前一個節(jié)點，next指向下一個節(jié)點，這一點在某種意義上與常規(guī)的雙向循環(huán)鏈表一致，但是還是有區(qū)別的。我們再來看看之前所學習的雙向循環(huán)鏈表的節(jié)點定義：
//數(shù)據(jù)
typedef int Datatype;
//節(jié)點
typedef struct Node
{
DataType data; //數(shù)據(jù)域
struct Node *prev; //指針域：前驅指針
struct Node *next; //指針域：后繼指針
}node;? ? ? ? 這樣一對比，就會發(fā)現(xiàn)常規(guī)鏈表與內核鏈表最大的區(qū)別就是嵌套，內核鏈表的節(jié)點結構通常嵌套在某個容器數(shù)據(jù)結構中，可以理解為能單獨對指針域進行操作，而不影響數(shù)據(jù)。
?所以這也暴露了常規(guī)鏈表的缺陷：
????????（1）每一種應用中，節(jié)點都是特殊的，導致每一條鏈表都是特殊的，因此每一種鏈表的增刪查改這些算法也都是特殊的；
????????（2）當一個節(jié)點處于變化的數(shù)據(jù)結構網絡中的時候，節(jié)點指針無法指向穩(wěn)定不變的節(jié)點。
? ? ? ? 這樣的描述或許不能讓你有直觀的感覺，但當你往下看，真正去理解了內核鏈表再回過頭來，你就會豁然開朗。
二、內核鏈表的原理
????????內核鏈表的節(jié)點結構通常嵌套在某個容器數(shù)據(jù)結構中，以實現(xiàn)緊密關聯(lián)。節(jié)點結構中至少包含兩個指針，一個指向前一個節(jié)點，一個指向后一個節(jié)點。這樣的設計使得在鏈表中插入、刪除節(jié)點的操作更加高效，無需像數(shù)組那樣移動大量元素。我們可以這樣理解：
????????（1）將鏈表的結構抽象出來，去除節(jié)點中的具體數(shù)據(jù)，只保留邏輯的雙向指針，形成一條只包含邏輯的“純粹的鏈表”。
????????（2）將鏈表“寄宿”于具體的數(shù)據(jù)節(jié)點之中，使他貫穿這些節(jié)點，可以借助一定的方式通過“純粹鏈表“的指針域得到數(shù)據(jù)節(jié)點。
?? ? ? ? ? ?內核鏈表做到了將數(shù)據(jù)和邏輯（指針）分開，在紅色方框內的這樣只有前后兩指針的鏈表形式被稱為Linux標準雙向循環(huán)鏈表。
三、內核鏈表的操作
? ? ? ? 在學習內核鏈表的操作之前，我們先要來了解一下list.h文件。list.h 是一個常見的頭文件，通常用于實現(xiàn)內核鏈表（雙向鏈表）的相關功能。在 Linux 內核中，list.h 提供了一種高效的方式來操作鏈表，包括插入、刪除、遍歷等操作。完整的該文件可從網上各處找到，接下來我們將只舉例用到的結構體。
1. 節(jié)點聲明
//數(shù)據(jù)
typedef int Datatype;
//鏈表節(jié)點（大結構體）
typedef struct Kernel_node
{
Datatype data; //數(shù)據(jù)域
struct list_head list; //指針域
}k_node;?????????list_head 是在list.h中已經定義好的指針域部分，我們可以將其稱之為小結構體，用它來構建“純粹鏈表”。
struct list_head {
struct list_head *next, *prev;
};2.初始化鏈表
//初始化鏈表
k_node *init_kernel_list()
{
k_node *head = malloc(sizeof(k_node));
if (head==NULL)
{
perror("malloc");
exit(0);
}
else
{
INIT_LIST_HEAD(&(head->list));//帶參宏，初始化小結構體里面的這兩個指針成員
}
return head;
}
????????INIT_LIST_HEAD也是list.h中已經定義好的帶參宏，原型如下：
#define INIT_LIST_HEAD(ptr) do { \
(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)3.創(chuàng)建節(jié)點
//創(chuàng)建節(jié)點
k_node *create_kernel_node(Datatype data)
{
k_node *new = malloc(sizeof(k_node));
if (new != NULL)
{
new->data = data;
new->list.next = NULL;
new->list.prev = NULL;
}
return new;
}
4.遍歷鏈表
//遍歷鏈表
void display(k_node *head)
{
struct list_head *pos = NULL;
k_node *Node = NULL;
list_for_each(pos, &(head->list))
{
Node = list_entry(pos, k_node, list);
printf("%d ", Node->data);
}
printf("\n");
}????????其中list_for_each和list_entry也是在list.h中定義好的帶參宏：
//遍歷鏈表的for循環(huán)，每一次循環(huán)體內得到的就是一個小結構體指針
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); \
pos = pos->next)
//小結構體指針ptr，大結構體類型type，小結構體在大結構體內部的成員名
#define list_entry(ptr, type, member) \
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
????????做完這些操作，我們就可以通過一個實例來驗證我們的操作是否正確，我們可以創(chuàng)建一個10個節(jié)點的鏈表并打印。
?????????實例代碼如下：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "list.h"
//數(shù)據(jù)
typedef int Datatype;
//鏈表節(jié)點
typedef struct Kernel_node
{
Datatype data; //數(shù)據(jù)域
struct list_head list; //指針域
}k_node;
//初始化鏈表
k_node *init_kernel_list()
{
k_node *head = malloc(sizeof(k_node));
if (head==NULL)
{
perror("malloc");
exit(0);
}
else
{
INIT_LIST_HEAD(&(head->list));
}
return head;
}
//創(chuàng)建節(jié)點
k_node *create_kernel_node(Datatype data)
{
k_node *new = malloc(sizeof(k_node));
if (new != NULL)
{
new->data = data;
new->list.next = NULL;
new->list.prev = NULL;
}
return new;
}
//遍歷鏈表
void display(k_node *head)
{
struct list_head *pos = NULL;
k_node *Node = NULL;
list_for_each(pos, &(head->list))
{
Node = list_entry(pos, k_node, list);
printf("%d ", Node->data);
}
printf("\n");
}
int main(int argc, char const *argv[])
{
k_node *head = init_kernel_list();
for (int i = 0; i < 10; ++i)
{
k_node *new = create_kernel_node(i+1);
//插入節(jié)點到鏈表
list_add_tail(&(new->list), &(head->list));
}
//遍歷鏈表
display(head);
return 0;
}
? ? ? ? 更安全的遍歷列表方法補充：
void display2(k_node *head)
{
struct list_head *pos = NULL;
struct list_head *n = NULL;//為了防止你在遍歷的時候，刪除節(jié)點，找不到下一個節(jié)點的地址
k_node *Node;
list_for_each_safe(pos, n, &(head->list))
{
Node = list_entry(pos, k_node, list);
printf("%d ", Node->data);
}
printf("\n");
}
void display3(k_node *head)
{
k_node *pos = NULL;
list_for_each_entry(pos, &(head->list), list)
{
printf("%d ", pos->data);
}
printf("\n");
}
void display4(k_node *head)
{
k_node *pos = NULL;
k_node *n = NULL;
list_for_each_entry_safe(pos, n, &(head->list), list)
{
printf("%d ", pos->data);
}
printf("\n");
}5.刪除節(jié)點
void delete_node(k_node *head, Datatype data)
{
struct list_head *pos = NULL;
struct list_head *n = NULL;//為了防止你在遍歷的時候，刪除節(jié)點，找不到下一個節(jié)點的地址
k_node *Node = NULL;
list_for_each_safe(pos, n, &(head->list))
{
Node = list_entry(pos, k_node, list);
if (Node->data == data)
{
list_del(&(Node->list));
}
}
}6.移動節(jié)點
void move_node_head(k_node *head, Datatype d1, Datatype d2)
{
k_node *p1 = find_node(head, d1);
k_node *p2 = find_node(head, d2);
if (p1==NULL || p2==NULL)
{
return;
}
list_move(&(p1->list), &(p2->list));
}
void move_node_tail(k_node *head, Datatype d1, Datatype d2)
{
k_node *p1 = find_node(head, d1);
k_node *p2 = find_node(head, d2);
if (p1==NULL || p2==NULL)
{
return;
}
list_move_tail(&(p1->list), &(p2->list));//尾插
}
//移動節(jié)點
move_node_head(head, 1, 7);
display4(head);
7.判斷是否為空鏈表
k_node *list_empty(k_node *head)
{
return head->next == head;
}8.合并鏈表
int main(int argc, char const *argv[])
{
k_node *head = init_kernel_list();
for (int i = 0; i < 10; ++i)
{
k_node *new = create_kernel_node(i+1);
//插入節(jié)點到鏈表
list_add_tail(&(new->list), &(head->list));//尾插
}
display4(head);
k_node *head1 = init_kernel_list();
for (int i = 10; i < 15; ++i)
{
k_node *new = create_kernel_node(i+1);
// 插入節(jié)點到鏈表
list_add_tail(&(new->list), &(head1->list));//尾插
}
display4(head1);
if (list_empty(&(head1->list)))
{
printf("這是空鏈表\n");
}
else
{
printf("非空，可合并\n");
}
// head的頭節(jié)點下面的第一個節(jié)點的前驅指針會斷開，head的尾節(jié)點的后繼指針會斷開，head后面不能在使用
list_splice_init(&(head->list), &(head1->list));
display4(head1);
return 0;
}????????運行結果：
?
留個作業(yè)吧
????????用內核鏈表創(chuàng)建一個數(shù)據(jù)集合，初始包含數(shù)據(jù)：1 2 3 4 5 6 7 8 9 ，將其重新排列成：9 7 5 3 1 2 4 6 8 （奇數(shù)降序，偶數(shù)升序）并顯示出來。
????????答案評論區(qū)見！
四、總結
????????與一般鏈表相比，內核鏈表有一些特點和優(yōu)勢：
????????1.容器結構體： 在內核鏈表中，節(jié)點通常嵌套在某個數(shù)據(jù)結構中，這個數(shù)據(jù)結構即所謂的容器結構體。這種設計可以讓數(shù)據(jù)元素和鏈表節(jié)點緊密關聯(lián)，方便數(shù)據(jù)的操作和管理。
????????2.穩(wěn)定性和預測性： 內核鏈表在操作系統(tǒng)內核中廣泛應用，而且內核鏈表的實現(xiàn)通常被優(yōu)化為在各種情況下都能夠穩(wěn)定和預測地工作，不容易受到異常情況的影響。
????????3.特定操作： 內核鏈表通常提供一系列針對特定操作的函數(shù)，如插入、刪除、遍歷等。這些函數(shù)經過精心的設計和優(yōu)化，能夠高效地處理鏈表操作。
????????總之，內核鏈表是操作系統(tǒng)內核中的一種重要數(shù)據(jù)結構，用于高效地管理各種資源和數(shù)據(jù)。它與一般鏈表相比，更注重穩(wěn)定性和性能優(yōu)化，以滿足操作系統(tǒng)的特定需求。
????????更多C語言、Linux系統(tǒng)、ARM板實戰(zhàn)和數(shù)據(jù)結構相關文章，關注專欄：
? ?手撕C語言
? ? ? ? ? ? 玩轉linux
????????????????????腳踢數(shù)據(jù)結構文章來源：http://www.zghlxwxcb.cn/news/detail-637404.html
?? ? ? ? ? ? ? ? ?? ? ? ? ? 6818（ARM）開發(fā)板實戰(zhàn)文章來源地址http://www.zghlxwxcb.cn/news/detail-637404.html
??寫在最后
- 今天的分享就到這啦~
- 覺得博主寫的還不錯的煩勞?
一鍵三連喔~ - ??感謝關注??
到了這里，關于【腳踢數(shù)據(jù)結構】內核鏈表的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
