---
tags: data structure, linux kernel, doubly linked list
---
# Linux Kernel 中的 Doubly Linked List
Linux Kernel 中的 Doubly Linked List 的相關 API 與 巨集被定義在 [linux/list.h](https://elixir.bootlin.com/linux/latest/source/include/linux/list.h) 中。
為了要寫程式操作 doubly linked list ，我把 Linux kerenel 的 `linux/list.h` 中關於 doubly linked list 的程式碼節錄到自己的 [list.h](https://github.com/hsuedw/data_structures_and_algorithms/blob/main/linux_kernel_linked_list/src/list.h) 中。並撰寫程式操作 double linked list 。
## Doubly Linked List 重要資料結構與 API
### 串列節點的定義
資料結構 `struct list_head` 被定義在 [linux/types.h](https://elixir.bootlin.com/linux/latest/source/include/linux/types.h#L178) 中。
```c
struct list_head {
struct list_head *next, *prev;
};
```
### 串列節點的初始化
串列節點的初始化有 [LIST_HEAD_INIT 巨集](https://elixir.bootlin.com/linux/latest/source/include/linux/list.h#L23) ， [LIST_HEAD 巨集](https://elixir.bootlin.com/linux/latest/source/include/linux/list.h#L25) 與 [INIT_LIST_HEAD 函式](https://elixir.bootlin.com/linux/latest/source/include/linux/list.h#L35) 等方式。
不論使用哪一種初始化方式，都會得到如下圖所示之 empty doubly linked list 。
```c
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
static inline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}
```
### 在 Doubly Linked List 加入一個串列節點
在 Linux kernel 中，有兩個 API 可以把節點加入 doubly linked list: [list_add](https://elixir.bootlin.com/linux/latest/source/include/linux/list.h#L86) 與 [list_add_tail](https://elixir.bootlin.com/linux/latest/source/include/linux/list.h#L100) 。
簡單的講， `list_add` 與 `list_add_tail` 中的 `new` 參數是個指向準備要加入 doubly linked list 之節點的指標。而 `head` 參數則是指向已經存在 doubly linked list 中某節點的指標。
`list_add` 與 `list_add_tail` 都是 `__list_add` 的 wrapper function 。
#### `list_add`
`list_add` 會把 `new` 所指向的節點加入 doubly linked list ，使其成為 `head->next` 所指向的節點。假設 doubly linked list 一開始的狀態如圖(1)所示。
當 `list_add` 呼叫了 `__list_add` 後，一開始的狀態如圖(2)所示。
當第 14 行執行完畢後， doubly linked list 的狀態如圖(3)所示。
當第 15 行執行完畢後， doubly linked list 的狀態如圖(4)所示。
當第 16 行執行完畢後， doubly linked list 的狀態如圖(5)所示。
當第 17 行執行完畢後， doubly linked list 的狀態如圖(6)所示。此時， `new` 指標所指向的節點已完全插入 doubly linked list ，且 `head->next` 指向此新插入的節點。
##### Example 1: Add several nodes right after the head of the doubly linked list ([github](https://github.com/hsuedw/data_structures_and_algorithms/blob/main/linux_kernel_linked_list/src/example1.c))
```c
#include <stdio.h>
#include "list.h"
/*
* Add several nodes right after the head of the doubly linked list.
*/
int main(int argc, char *argv[])
{
LIST_HEAD(head);
LIST_HEAD(node1);
list_add(&node1, &head);
LIST_HEAD(node2);
list_add(&node2, &head);
LIST_HEAD(node3);
list_add(&node3, &head);
/*
* Now, the doubly linked list is head <-> node3 <-> node2 <-> node1
* ^ ^
* |____________________________|
*/
return 0;
}
```
#### `list_add_tail`
另一方面， `list_add_tail` 則是把 `new` 所指向的節點加入 doubly linked list ，並使其成為 `head->prev` 所指向的節點。假設 doubly linked list 一開始的狀態如圖(1)所示。
當 `list_add_tail` 呼叫了 `__list_add` 後，一開始的狀態如圖(7)所示。
當第 14 行執行完畢後， doubly linked list 的狀態如圖(8)所示。
當第 15 行執行完畢後， doubly linked list 的狀態如圖(9)所示。
當第 16 行執行完畢後， doubly linked list 的狀態如圖(10)所示。
當第 17 行執行完畢後， doubly linked list 的狀態如圖(11)所示。此時， `new` 指標所指向的節點已完全插入 doubly linked list ，且 `head->prev` 指向此新插入的節點。
``` c=
/*
* 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)
{
if (!__list_add_valid(new, prev, next))
return;
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;
}
/**
* list_add - add a new entry
* @new: new entry to be added
* @head: list head to add it after
*
* Insert a new entry after the specified head.
* This is good for implementing stacks.
*/
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
/**
* list_add_tail - add a new entry
* @new: new entry to be added
* @head: list head to add it before
*
* Insert a new entry before the specified head.
* This is useful for implementing queues.
*/
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
```
##### Example 2: Add several nodes at the tail of the doubly linked list ([github](https://github.com/hsuedw/data_structures_and_algorithms/blob/main/linux_kernel_linked_list/src/example2.c))
```c
#include <stdio.h>
#include "list.h"
/*
* Add several nodes the tail of the doubly linked list.
*/
int main(int argc, char *argv[])
{
LIST_HEAD(head);
LIST_HEAD(node1);
list_add_tail(&node1, &head);
LIST_HEAD(node2);
list_add_tail(&node2, &head);
LIST_HEAD(node3);
list_add_tail(&node3, &head);
/*
* Now, the doubly linked list is head <-> node1 <-> node2 <-> node3
* ^ ^
* |____________________________|
*/
return 0;
}
```
### 拜訪 Doubly Linked List 中的所有節點
#### `list_for_each` 與 `list_for_each_prev`
```c
/**
* list_for_each - iterate over a list
* @pos: the &struct list_head to use as a loop cursor.
* @head: the head for your list.
*/
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
/**
* list_for_each_prev - iterate over a list backwards
* @pos: the &struct list_head to use as a loop cursor.
* @head: the head for your list.
*/
#define list_for_each_prev(pos, head) \
for (pos = (head)->prev; pos != (head); pos = pos->prev)
```
##### Example 3: Traverse all the nodes in a doubly linked list ([github](https://github.com/hsuedw/data_structures_and_algorithms/blob/main/linux_kernel_linked_list/src/example3.c))
```c
#include <stdio.h>
#include "list.h"
/*
* Add several nodes into the doubly linked list.
* Then traverse all the nodes.
*/
int main(int argc, char *argv[])
{
LIST_HEAD(head);
/* Add node1 at the head of the doubly linked list */
LIST_HEAD(node1);
printf("node1: 0x%p\n", &node1);
list_add(&node1, &head);
/* Add node2 at the head of the doubly linked list */
LIST_HEAD(node2);
printf("node2: 0x%p\n", &node2);
list_add(&node2, &head);
/* Add node3 at the tail of the doubly linked list */
LIST_HEAD(node3);
printf("node3: 0x%p\n", &node3);
list_add_tail(&node3, &head);
/* Add node4 at the tail of the doubly linked list */
LIST_HEAD(node4);
printf("node4: 0x%p\n", &node4);
list_add_tail(&node4, &head);
/*
* Now, the doubly linked list is "head <-> node2 <-> node1 <-> node3 <-> node4".
* ^ ^
* |_______________________________________|
*/
struct list_head *it = NULL;
printf("list_for_each: ");
list_for_each(it, &head) {
printf("0x%p ", it);
}
printf("\n");
it = NULL;
printf("list_for_each_prev: ");
list_for_each_prev(it, &head) {
printf("0x%p ", it);
}
printf("\n");
return 0;
}
```
#### `list_for_each_entry` 與 `list_for_each_entry_reverse`
```c
/**
* list_for_each_entry - iterate over list of given type
* @pos: the type * to use as a loop cursor.
* @head: the head for your list.
* @member: the name of the list_head within the struct.
*/
#define list_for_each_entry(pos, head, member) \
for (pos = list_first_entry(head, typeof(*pos), member); \
&pos->member != (head); \
pos = list_next_entry(pos, member))
/**
* list_for_each_entry_reverse - iterate backwards over list of given type.
* @pos: the type * to use as a loop cursor.
* @head: the head for your list.
* @member: the name of the list_head within the struct.
*/
#define list_for_each_entry_reverse(pos, head, member) \
for (pos = list_last_entry(head, typeof(*pos), member); \
&pos->member != (head); \
pos = list_prev_entry(pos, member))
```
##### Example 4: Traverse all the nodes in a doubly linked list ([github](https://github.com/hsuedw/data_structures_and_algorithms/blob/main/linux_kernel_linked_list/src/example4.c))
```c
#include <stdio.h>
#include "list.h"
/*
* Add several nodes into the doubly linked list.
* Then traverse all the nodes.
*/
struct test {
int value;
struct list_head node;
};
void init_list_node(struct test *pdata, int value)
{
pdata->value = value;
INIT_LIST_HEAD(&pdata->node);
}
int main(int argc, char *argv[])
{
LIST_HEAD(head);
/* Add data1 at the head of the doubly linked list */
struct test data1;
init_list_node(&data1, 1);
list_add(&data1.node, &head);
/* Add data2 at the head of the doubly linked list */
struct test data2;
init_list_node(&data2, 2);
list_add(&data2.node, &head);
/* Add data3 at the tail of the doubly linked list */
struct test data3;
init_list_node(&data3, 3);
list_add_tail(&data3.node, &head);
/* Add data4 at the tail of the doubly linked list */
struct test data4;
init_list_node(&data4, 4);
list_add_tail(&data4.node, &head);
/*
* Now, the doubly linked list is "head <-> node2 <-> node1 <-> node3 <-> node4".
* ^ ^
* |_______________________________________|
*/
struct test *it = NULL;
printf("list_for_each_entry: ");
list_for_each_entry(it, &head, node) {
printf("%d ", it->value);
}
printf("\n");
it = NULL;
printf("list_for_each_entry_reverse: ");
list_for_each_entry_reverse(it, &head, node) {
printf("%d ", it->value);
}
printf("\n");
return 0;
}
```
### 自 Doubly Linked List 中移除一節點
Linux kernel 中提供 `list_del` 與 `list_del_init` 這兩個 API 移除 doubly linked list 中的節點。
只要把欲移除的節點的記憶體位址傳給 `list_del` 或 `1ist_del_init` 就可以把該節點自 doubly linked list 中移除。
#### `list_del` 與 `list_del_init`
假設目前有一個如圖(1) 所示的 doubly linked list ，且想要刪除第一個節點。
當透過 `list_del` 或 `1ist_del_init` 呼叫到 `__list_del` 時， doubly linked list 的狀態如圖(12) 所示。
當第 10 行執行完畢後， doubly linked list 的狀態如圖(13)所示。
當第 11 行執行完畢後， doubly linked list 的狀態如圖(14)所示。
如果是使用 `list_del_init` ，當第 42 行執行完畢後， doubly linked list 的狀態如圖(15)所示。
```c=
/*
* 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;
}
/**
* list_del - deletes entry from list.
* @entry: the element to delete from the list.
* Note: list_empty() on entry does not return true after this, the entry is
* in an undefined state.
*/
static inline void __list_del_entry(struct list_head *entry)
{
if (!__list_del_entry_valid(entry))
return;
__list_del(entry->prev, entry->next);
}
static inline void list_del(struct list_head *entry)
{
__list_del_entry(entry);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
/**
* list_del_init - deletes entry from list and reinitialize it.
* @entry: the element to delete from the list.
*/
static inline void list_del_init(struct list_head *entry)
{
__list_del_entry(entry);
INIT_LIST_HEAD(entry);
}
```
##### Example 5
```c
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
/*
* Add several nodes into the doubly linked list.
* Then traverse all the nodes.
*/
struct test {
int value;
struct list_head node;
};
struct test *create_node(int value)
{
struct test *pdata = calloc(1, sizeof(struct test));
pdata->value = value;
INIT_LIST_HEAD(&pdata->node);
return pdata;
}
#define LIST_SZ (5)
int main(int argc, char *argv[])
{
struct list_head *head = calloc(1, sizeof(struct list_head));
INIT_LIST_HEAD(head);
for (int i = 0; i < LIST_SZ; ++i) {
struct test *new_data = create_node(i);
list_add_tail(&new_data->node, head);
}
/* Now, the doubly linked list has following nodes: 0 1 2 3 4 */
printf("List all the data in the doubly linked list: ");
struct test *it = NULL;
list_for_each_entry(it, head, node) {
printf("%d ", it->value);
}
printf("\n");
printf("Delete the first node from the doubly linked list.\n");
struct list_head *x = head->next;
list_del_init(x);
free(container_of(x, struct test, node));
/* Now, the doubly linked list has following nodes: 1 2 3 4 */
printf("List the rest data in the doubly linked list: ");
list_for_each_entry(it, head, node) {
printf("%d ", it->value);
}
printf("\n");
printf("Delete the node at the tail of the doubly linked list.\n");
x = head->prev;
list_del_init(x);
free(container_of(x, struct test, node));
/* Now, the doubly linked list has following nodes: 1 2 3 */
printf("List the rest data in the doubly linked list: ");
list_for_each_entry(it, head, node) {
printf("%d ", it->value);
}
printf("\n");
printf("Delete the whole doubly linked list.\n");
struct test *it2 = NULL;
list_for_each_entry_safe(it, it2, head, node) {
list_del_init(&it->node);
free(it);
}
if (list_empty(head)) {
printf("All the data have been deleted from the doubly linked list.\n");
}
free(head);
return 0;
}
```
Sign in with Wallet
Connect another wallet