悩んでいる人
C言語の連結リストを教えて！
こういった悩みにお答えします．
本記事の信頼性
- リアルタイムシステムの研究歴12年．
- 東大教員の時に，英語でOS（Linuxカーネル）の授業．
- 2012年9月～2013年8月にアメリカのノースカロライナ大学チャペルヒル校（UNC）コンピュータサイエンス学部で客員研究員として勤務．C言語でリアルタイムLinuxの研究開発．
- プログラミング歴15年以上，習得している言語: C/C++，Python，Solidity/Vyper，Java，Ruby，Go，Rust，D，HTML/CSS/JS/PHP，MATLAB，Assembler (x64，ARM)．
- 東大教員の時に，C++言語で開発した「LLVMコンパイラの拡張」，C言語で開発した独自のリアルタイムOS「Mcube Kernel」をGitHubにオープンソースとして公開．
- 2020年1月～現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務．2022年6月～現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO．
- 最近は自然言語処理AIとイーサリアムに関する有益な情報発信に従事．
- （AI全般を含む）自然言語処理AIの論文の日本語訳や，AIチャットボット（ChatGPT，Auto-GPT，Gemini（旧Bard）など）の記事を50本以上執筆．アメリカのサンフランシスコ（広義のシリコンバレー）の会社でプロンプトエンジニア・マネージャー・Quality Assurance（QA）の業務委託の経験あり．
- （スマートコントラクトのプログラミングを含む）イーサリアムや仮想通貨全般の記事を200本以上執筆．イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり．
こういった私から学べます．
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
連結リスト
連結リスト（linked list）とは，順序付きデータ構造として定義されるデータ構造です．
※連結リストのことを単にリストと省略することが多いです．
また，C言語ではリストは，主に構造体で定義されます．
構造体を学びたいあなたはこちらからどうぞ．
また，C言語のリストを理解するためには，ポインタの知識が必須です．
ポインタを学びたいあなたはこちらからどうぞ．
C言語のリスト
C言語のリストを紹介していきます．
本記事のリストの実装では，番兵ノード（ダミーノード）を利用しています．
また，リストを操作する関数の名前は，C++言語のstd::listクラスのメンバ関数を参考にしています．
- push_back_list()：末尾に要素を追加
- insert_list()：任意の位置に要素の挿入
- erase_list()：任意の位置にある要素の削除
- clear_list()：全要素削除
それでは，線形リストの片方向リストと双方向リスト，循環リストの双方向循環リストを紹介していきます．
片方向リスト
片方向リスト（singly linked list）は，最も単純な連結リストであり，ノード毎に1つのリンクを持つリストです．
このリンクはリスト上の次のノードを指し，リストの最後尾ならNULL値を格納します．
※片方向リストは単方向リストと表記されることがあります．
片方向リストのコードは以下になります．
|
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> struct list_node { struct list_node *next; int value; }; void print_list(struct list_node *list) { struct list_node *p = list->next; printf("print_list(): "); while (p) { printf("value(%d)->", p->value); p = p->next; } printf("NULL\n"); } void init_list(struct list_node *list) { list->next = NULL; list->value = 0; } void push_back_list(struct list_node *list, int value) { struct list_node *node; struct list_node *p = list; if ((node = (struct list_node *) malloc(sizeof(struct list_node))) == NULL) { fprintf(stderr, "Error cannot allocate memory %zu\n", sizeof(struct list_node)); exit(1); } while (p->next) { p = p->next; } p->next = node; node->value = value; node->next = NULL; } int insert_list(struct list_node *list, int value, size_t index) { struct list_node *prev_node = list; struct list_node *node; size_t i; for (i = 0; i < index; i++) { if (prev_node == NULL) { fprintf(stderr, "Error: cannot find the node of index %lu.\n", i); return 1; } prev_node = prev_node->next; } if (prev_node == NULL) { fprintf(stderr, "Error: cannot find the node of index %lu.\n", i); return 2; } if ((node = (struct list_node *) malloc(sizeof(struct list_node))) == NULL) { fprintf(stderr, "Error cannot allocate memory %zu\n", sizeof(struct list_node)); exit(1); } node->next = prev_node->next; node->value = value; prev_node->next = node; return 0; } int erase_list(struct list_node *list, size_t index) { struct list_node *prev_node = list; struct list_node *node; size_t i; for (i = 0; i < index; i++) { if (prev_node == NULL) { fprintf(stderr, "Error: cannot find the node of index %lu.\n", i); return 1; } prev_node = prev_node->next; } node = prev_node->next; if (node == NULL) { fprintf(stderr, "Error: cannot find the node of index %lu.\n", i); return 2; } prev_node->next = node->next; free(node); return 0; } void clear_list(struct list_node *list) { struct list_node *prev_node = list->next; struct list_node *node; while (prev_node) { node = prev_node->next; free(prev_node); prev_node = node; } init_list(list); } int main(void) { struct list_node list; init_list(&list); print_list(&list); push_back_list(&list, 1); print_list(&list); push_back_list(&list, 3); print_list(&list); push_back_list(&list, 2); print_list(&list); erase_list(&list, 1); print_list(&list); insert_list(&list, 100, 1); print_list(&list); clear_list(&list); print_list(&list); return 0; } |
実行結果は以下になります．
|
1 2 3 4 5 6 7 8 9 |
$ gcc singly_linked_list.c $ a.out print_list(): NULL print_list(): value(1)->NULL print_list(): value(1)->value(3)->NULL print_list(): value(1)->value(3)->value(2)->NULL print_list(): value(1)->value(2)->NULL print_list(): value(1)->value(100)->value(2)->NULL print_list(): NULL |
双方向リスト
双方向リスト（doubly linked list）は，各ノードには2つのリンクがあり，1つが次のノード（前方リンク），もう1つが後ろのノード（後方リンク）を指すリストです．
片方向リストと比較して，双方向リストは前方リンクがあるので，前のノードにアクセスすることが容易になります．
双方向リストのコードは以下になります．
|
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> struct list_node { struct list_node *next, *prev; int value; }; void print_list(struct list_node *list) { struct list_node *p = list->next; printf("print_list(): "); while (p) { printf("value(%d)->", p->value); p = p->next; } printf("NULL\n"); } void init_list(struct list_node *list) { list->next = list->prev = NULL; list->value = 0; } void push_back_list(struct list_node *list, int value) { struct list_node *node; struct list_node *p = list; if ((node = (struct list_node *) malloc(sizeof(struct list_node))) == NULL) { fprintf(stderr, "Error cannot allocate memory %zu\n", sizeof(struct list_node)); exit(1); } while (p->next) { p = p->next; } p->next = node; node->prev = p; node->value = value; node->next = NULL; } int insert_list(struct list_node *list, int value, size_t index) { struct list_node *prev_node = list; struct list_node *node; size_t i; for (i = 0; i < index; i++) { if (prev_node == NULL) { fprintf(stderr, "Error: cannot find the node of index %lu.\n", i); return 1; } prev_node = prev_node->next; } if (prev_node == NULL) { fprintf(stderr, "Error: cannot find the node of index %lu.\n", i); return 2; } if ((node = (struct list_node *) malloc(sizeof(struct list_node))) == NULL) { fprintf(stderr, "Error cannot allocate memory %zu\n", sizeof(struct list_node)); exit(1); } node->prev = prev_node; node->next = prev_node->next; node->value = value; prev_node->next = node; if (node->next) { node->next->prev = node; } return 0; } int erase_list(struct list_node *list, size_t index) { struct list_node *prev_node = list; struct list_node *node; size_t i; for (i = 0; i < index; i++) { if (prev_node == NULL) { fprintf(stderr, "Error: cannot find the node of index %lu.\n", i); return 1; } prev_node = prev_node->next; } node = prev_node->next; if (node == NULL) { fprintf(stderr, "Error: cannot find the node of index %lu.\n", i); return 2; } prev_node->next = node->next; if (node->next) { node->next->prev = prev_node; } free(node); return 0; } void clear_list(struct list_node *list) { struct list_node *prev_node = list->next; struct list_node *node; while (prev_node) { node = prev_node->next; free(prev_node); prev_node = node; } init_list(list); } int main(void) { struct list_node list; init_list(&list); print_list(&list); push_back_list(&list, 1); print_list(&list); push_back_list(&list, 3); print_list(&list); push_back_list(&list, 2); print_list(&list); erase_list(&list, 1); print_list(&list); insert_list(&list, 100, 1); print_list(&list); clear_list(&list); print_list(&list); return 0; } |
実行結果は以下になります．
|
1 2 3 4 5 6 7 8 9 |
$ gcc doubly_linked_list.c $ a.out print_list(): NULL print_list(): value(1)->NULL print_list(): value(1)->value(3)->NULL print_list(): value(1)->value(3)->value(2)->NULL print_list(): value(1)->value(2)->NULL print_list(): value(1)->value(100)->value(2)->NULL print_list(): NULL |
双方向循環リスト
双方向循環リスト（doubly circular linked list）は，各ノードは線形の双方向リストと同じように2つのリンクを持ち，先頭ノードの後方リンクは最後尾ノードを指し，最後尾ノードの前方リンクは先頭ノードを指すことで循環するリストです．
※片方向循環リストもありますが，あまり利用されていないので省略します．
双方向循環リストのコードは以下になります．
|
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> struct list_node { struct list_node *next, *prev; int value; }; void print_list(struct list_node *list) { struct list_node *p = list->next; printf("print_list(): "); while (p != list) { printf("value(%d)->", p->value); p = p->next; } printf("HEAD\n"); } void init_list(struct list_node *list) { list->next = list->prev = list; list->value = 0; } void push_back_list(struct list_node *list, int value) { struct list_node *node; struct list_node *p = list; if ((node = (struct list_node *) malloc(sizeof(struct list_node))) == NULL) { fprintf(stderr, "Error cannot allocate memory %zu\n", sizeof(struct list_node)); exit(1); } while (p->next != list) { p = p->next; } p->next->prev = node; p->next = node; node->prev = p; node->value = value; node->next = list; } int insert_list(struct list_node *list, int value, size_t index) { struct list_node *prev_node = list; struct list_node *node; size_t i; for (i = 0; i < index; i++) { prev_node = prev_node->next; if (prev_node == list) { fprintf(stderr, "Error: cannot find the node of index %lu.\n", i + 1); return 1; } } if ((node = (struct list_node *) malloc(sizeof(struct list_node))) == NULL) { fprintf(stderr, "Error cannot allocate memory %zu\n", sizeof(struct list_node)); exit(1); } node->prev = prev_node; node->next = prev_node->next; node->value = value; prev_node->next = node; node->next->prev = node; return 0; } int erase_list(struct list_node *list, size_t index) { struct list_node *prev_node = list; struct list_node *node; size_t i; for (i = 0; i < index; i++) { prev_node = prev_node->next; if (prev_node == list) { fprintf(stderr, "Error: cannot find the node of index %lu.\n", i + 1); return 1; } } node = prev_node->next; if (node == list) { fprintf(stderr, "Error: cannot find the node of index %lu.\n", i); return 2; } prev_node->next = node->next; node->next->prev = prev_node; free(node); return 0; } void clear_list(struct list_node *list) { struct list_node *prev_node = list->next; struct list_node *node; while (prev_node != list) { node = prev_node->next; free(prev_node); prev_node = node; } init_list(list); } int main(void) { struct list_node list; init_list(&list); print_list(&list); push_back_list(&list, 1); print_list(&list); push_back_list(&list, 3); print_list(&list); push_back_list(&list, 2); print_list(&list); erase_list(&list, 1); print_list(&list); insert_list(&list, 100, 1); print_list(&list); clear_list(&list); print_list(&list); return 0; } |
実行結果は以下になります．
|
1 2 3 4 5 6 7 8 9 |
$ gcc circular_doubly_linked_list.c $ a.out print_list(): HEAD print_list(): value(1)->HEAD print_list(): value(1)->value(3)->HEAD print_list(): value(1)->value(3)->value(2)->HEAD print_list(): value(1)->value(2)->HEAD print_list(): value(1)->value(100)->value(2)->HEAD print_list(): HEAD |
リストの実例：Linuxカーネル
リストの実例としてLinuxカーネルを紹介します．
Linuxカーネルでは，list_head構造体としてリストが実装されています．
Linuxカーネルを学びたいあなたはこちらからどうぞ．
list_head構造体の定義とデータの参照
list_head構造体の定義は，include/linux/types.hにあります．
Linuxカーネルはリンクとデータが分離されています．
つまり，list_node構造体のvalueがありません．
これにより，同じ構造体で異なるデータを管理することができます．
|
1 2 3 |
struct list_head { struct list_head *next, *prev; }; |
list_head構造体のデータの参照は，include/linux/list.hにあるlist_entryマクロを利用します．
|
1 2 3 4 5 6 7 8 |
/** * list_entry - get the struct for this entry * @ptr: the &struct list_head pointer. * @type: the type of the struct this is embedded in. * @member: the name of the list_head within the struct. */ #define list_entry(ptr, type, member) \ container_of(ptr, type, member) |
container_ofマクロはinclude/linux/kernel.hにあり，引数は以下になります．
- ptr：メンバのアドレス
- type：構造体の型
- member：構造体のメンバの名前
ptrからoffsetofマクロでtypeとmemberのオフセットを引き算すればデータのアドレスを計算できます．
「((type *)(__mptr - offsetof(type, member)))」の部分です．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
/** * container_of - cast a member of a structure out to the containing structure * @ptr: the pointer to the member. * @type: the type of the container struct this is embedded in. * @member: the name of the member within the struct. * */ #define container_of(ptr, type, member) ({ \ void *__mptr = (void *)(ptr); \ BUILD_BUG_ON_MSG(!__same_type(*(ptr), ((type *)0)->member) && \ !__same_type(*(ptr), void), \ "pointer type mismatch in container_of()"); \ ((type *)(__mptr - offsetof(type, member))); }) |
list_head構造体の初期化
list_head構造体の静的な初期化は，include/linux/list.hにあるLIST_HEADマクロを利用します．
|
1 2 3 4 |
#define LIST_HEAD_INIT(name) { &(name), &(name) } #define LIST_HEAD(name) \ struct list_head name = LIST_HEAD_INIT(name) |
list_head構造体の動的な初期化は，include/linux/list.hにあるINIT_LIST_HEAD関数を利用します．
|
1 2 3 4 5 |
static inline void INIT_LIST_HEAD(struct list_head *list) { WRITE_ONCE(list->next, list); list->prev = list; } |
list_head構造体の要素の追加と削除
list_head構造体の要素の追加は，include/linux/list.hにあるlist_add関数を利用します．
list_add関数では__list_add関数を呼び出しています．
双方向循環リストを理解していると処理がイメージできます．
|
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 |
/* * 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; WRITE_ONCE(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_head構造体の要素の削除は，list_del関数を利用します．
list_del関数は__list_del_entry関数，__list_del_entry関数は__list_del関数を呼び出します．
|
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 |
/* * 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; WRITE_ONCE(prev->next, next); } static inline void __list_del_entry(struct list_head *entry) { if (!__list_del_entry_valid(entry)) return; __list_del(entry->prev, entry->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(struct list_head *entry) { __list_del_entry(entry); entry->next = LIST_POISON1; entry->prev = LIST_POISON2; } |
まとめ
C言語の連結リストを紹介しました．
具体的には，片方向リスト，双方向リスト，双方向循環リスト，Linuxカーネルにおける実例を解説しました．
これらのコードを読むことで，C言語の連結リストを深く理解できます．
他のデータ構造を知りたいあなたはこちらからどうぞ．
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
