用户名: 密码: 忘记密码? 注册

Linux内核中链表的实现

作者:  时间: 2010-12-20

开发Linux内核不需要天赋,不需要有什么魔法,连Unix开发者普遍长着的络腮胡子都不一定要有。                                                   Robert Love

 

内核中链表O(1)的添加、删除操作

Linux内核中标准链表实现上采用的是环形双向链表。链表结构的定义在<linux/list.h>中,

struct list_head {

         struct list_head *next, *prev;

}

在内核中,链表中的任何一个节点都可以作为头节点,从另外一个角度而言,也就是说,链表中没有头节点。

 

(1)       由于是双向链表,所以链表很容易实现向前或向后访问

(2)       由于是环形链表,所以我们很容易从任意一个节点开始遍历整个链表

(3)       由于是双向环形链表,我们很容易实现O(1)的链表添加、删除操作

 

链表的插入

/*

 * Insert a new entry between two known consecutive entries.

 *

 * This is only for internal list manipulation where we know

 * the prev/next entries already!

 */

static inline void __list_add(struct list_head *new,

                                  struct list_head *prev,

                                  struct list_head *next)

{

         next->prev = new;

         new->next = next;

         new->prev = prev;

         prev->next = new;

}

已知插入的位置,只需进行四次赋值就可完成链表元素的插入

双向链表的使用一般支持节点的前向插入和后向插入,通过上述__list_add我们都可以实现,例如,对于特定的头节点struct list_head *head,前向插入可以通过

__list_add(new, head->prev, head)

实现,后向插入可以通过

__list_add(new, head, head->next)

实现

 

链表的删除

/*

 * Delete a list entry by making the prev/next entries

 * point to each other.

 *

 * This is only for internal list manipulation where we know

 * the prev/next entries already!

 */

static inline void __list_del(struct list_head * prev, struct list_head * next)

{

         next->prev = prev;

         prev->next = next;

}

 

显然,上述插入和删除操作显然是O(1)的。

 

实际上,对于单项链表,我们也能够实现O(1)的插入和删除操作的

假设单向链表的定义为

struct list_node {

    int data;

         struct list_node *next;

}

对于单向链表,一般为了操作方便,会加上一个链表头,链表头指向链表的第一个元素,当链表头的next指针为0时,链表为空。

对于上述定义的单向链表,我们O(1)的插入和删除操作实现如下:

/*Insert a new node before specified node*/

static inline void __list_add(struct list_node *new,

                                  struct list_node *node)

{

         int tmp = node->data;

node->data = new->data;

new->data = tmp;

new->next = node->next;

node->next = new;

}

前向插入的难点在于单向链表中我们无法以O(1)的代价得到当前节点的前一个节点,但如果我们将newnode的内容交换以后,问题变成了在node后向插入一个节点,这个问题就会很简单。

删除操作

static inline void __list_del(struct list_node *head,

                                  struct list_node *node)

{

         if (head == node){

       return;

}else if (node->next == 0){

   struct list_node *tmp = head;

   while (tmp->next != node){

      tmp = tmp->next;

   }

   tmp->next = 0;

} else {

   struct list_node *tmp = node->next;

   node->data = tmp->data;

   node->next = tmp->next;

   free_node(tmp);

}

}

上述代码中,当被删除节点不是链表尾节点时,我们只需将被删除节点的后一个节点拷贝到被删除节点,然后释放掉后一个节点即可;当被删除节点是链表尾节点时,由于我们必须重置被删除节点的前一个节点的next指针为空,因此需要从头遍历链表。

删除操作的复杂度分析可以这样来做:假设链表的长度为n,当删除的是第1n-1个节点时,需要查找n-1次(每个节点各超找一次),当删除的是第n个节点时,需要查找n-1次,所以平均的查找次数为(2*(n-1))/n,可以看出,平均计算复杂度仍然是O(1)