当前位置：首页 > news >正文

数据结构----＞内核链表

news 来源：原创 2024/9/20 14:50:09

一、内核链表的基本概念

1. 定义

内核链表是一种线性数据结构，其中每个节点包含了数据元素本身以及指向下一个节点的指针。在Linux内核中，这种链表通常被实现为双向链表或循环链表，以支持更高效的插入、删除和遍历操作。

2. 节点结构

内核链表的节点通常包含至少两个指针：一个指向前一个节点（prev），另一个指向后一个节点（next）。在某些实现中，还可能包含一个指向数据本身的指针，但在Linux内核的链表中，节点本身并不直接存储用户数据，而是将用户数据保存在包含链表节点的结构体中。

3. 链表头

链表头是一个特殊的节点，它通常不包含有效数据，但用于标识链表的开始位置。在双向链表中，链表头还可能包含指向链表最后一个节点的指针，以及一个指向链表第一个节点的指针。

二、内核链表的特点

1. 高效性

内核链表通过指针将节点连接在一起，使得插入、删除和遍历操作可以在O(1)或O(n)的时间

复杂度内完成，这取决于操作的具体位置和链表的长度。

2. 灵活性

由于节点之间通过指针连接，因此不需要像数组那样在物理内存中占用连续的空间。这使得

内核链表能够灵活地管理动态分配的内存，并且可以根据需要动态地添加或删除节点。

3. 稳定性

内核链表在操作系统内核中广泛使用，因此其实现必须稳定可靠。Linux内核中的链表实现经

过了严格的测试和验证，以确保在各种情况下都能正常工作。

三、内核链表的操作

1. 初始化

在创建链表之前，需要先对链表头进行初始化。这通常包括设置链表头的指针为NULL（对于

单向链表）或指向自身（对于双向循环链表）。

typedef struct knode
{struct knode *ppre;struct knode *pnext;}Knode_t;typedef struct klink
{Knode_t *phead;int clen;pthread_mutex_t mutex;
}Klink_t;

2. 插入节点

在链表中插入节点时，需要找到插入位置的前一个节点，并修改该节点和待插入节点的指

针。对于双向链表，还需要更新待插入节点的前驱指针。

int push_klink_head(Klink_t *pklink, void *p)
{Knode_t *pnode = (Knode_t *)p;pnode->pnext = NULL;pnode->ppre = NULL;pnode->pnext = pklink->phead;if (pklink->phead != NULL){pklink->phead->ppre = pnode;}pklink->phead = pnode;pklink->clen++;return 0;
}
int push_klink_tail(Klink_t *pklink,void *p)
{Knode_t *pnode = (Knode_t *)p;pnode->pnext =NULL;pnode->ppre =NULL;if(pklink->phead!=NULL){Knode_t *p = pklink->phead;while(p->pnext!=NULL){p=p->pnext;}p->pnext=pnode;pnode->ppre=p;}else if(pklink->phead==NULL){pklink->phead = pnode;}pklink->clen++;return 0;
}

3. 删除节点

删除链表中的节点时，需要找到该节点的前一个节点和后一个节点，并修改它们的指针以绕

过被删除的节点。对于双向链表，还需要更新被删除节点的前驱指针的指向。

int pop_klink_head(Klink_t *pklink)
{if(pklink->phead ==NULL){return 0;}Knode_t *p = pklink->phead;pklink->phead = p->pnext;p->ppre = NULL;free(p);if(pklink->phead !=NULL){pklink->phead->ppre=NULL;}pklink->clen--;return 0;
}
int pop_klink_tail(Klink_t *pklink)
{if(pklink->phead==NULL){return 0;}Knode_t *p = pklink->phead;while(p->pnext != NULL){p=p->pnext;}if(p->ppre!= NULL){p->ppre->pnext=NULL;}else{pklink->phead = NULL;}free(p);pklink->clen--;return 0;
}

4. 遍历链表

遍历链表通常从链表头开始，依次访问每个节点直到链表末尾。在双向链表中，可以从链表

头或链表尾开始遍历。

void klink_for_each(Klink_t *pklink, void (*pfun)(void *))
{Knode_t *pnode = pklink->phead;while (pnode != NULL){pfun(pnode);pnode = pnode->pnext;}printf("\n");
}

5.查找

KNode_t *find_klink(KLink_t *pklink, void *t, CMP_t pfun)
{KNode_t *pnode = pklink->phead;while (pnode != NULL){if (pfun(t, pnode)){return pnode;}pnode = pnode->pnext;}return NULL;
}

6.销毁

int is_empty_klink(KLink_t *pklink)
{return NULL == pklink->phead;
}
void destroy_klink(KLink_t *pklink)
{while (!is_empty_klink(pklink)){pop_klink_head(pklink);}free(pklink);
}