C LANGUAGE TECHNOLOGY

【C言語】連結リストとは【片方向リスト,双方向リスト,双方向循環リスト】

2021年9月5日

悩んでいる人

C言語の連結リストを教えて!

こういった悩みにお答えします.

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOS(Linuxカーネル)の授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校(UNC)コンピュータサイエンス学部で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発.
  • プログラミング歴15年以上,習得している言語: C/C++PythonSolidity/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値を格納します.

※片方向リストは単方向リストと表記されることがあります.

片方向リストのコードは以下になります.

実行結果は以下になります.

双方向リスト

双方向リスト(doubly linked list)は,各ノードには2つのリンクがあり,1つが次のノード(前方リンク),もう1つが後ろのノード(後方リンク)を指すリストです.

片方向リストと比較して,双方向リストは前方リンクがあるので,前のノードにアクセスすることが容易になります.

双方向リストのコードは以下になります.

実行結果は以下になります.

双方向循環リスト

双方向循環リスト(doubly circular linked list)は,各ノードは線形の双方向リストと同じように2つのリンクを持ち,先頭ノードの後方リンクは最後尾ノードを指し,最後尾ノードの前方リンクは先頭ノードを指すことで循環するリストです.

※片方向循環リストもありますが,あまり利用されていないので省略します.

双方向循環リストのコードは以下になります.

実行結果は以下になります.

リストの実例:Linuxカーネル

リストの実例としてLinuxカーネルを紹介します.

Linuxカーネルでは,list_head構造体としてリストが実装されています.

Linuxカーネルを学びたいあなたはこちらからどうぞ.

list_head構造体の定義とデータの参照

list_head構造体の定義は,include/linux/types.hにあります.

Linuxカーネルはリンクとデータが分離されています.

つまり,list_node構造体のvalueがありません.

これにより,同じ構造体で異なるデータを管理することができます.

list_head構造体のデータの参照は,include/linux/list.hにあるlist_entryマクロを利用します.

container_ofマクロはinclude/linux/kernel.hにあり,引数は以下になります.

  • ptr:メンバのアドレス
  • type:構造体の型
  • member:構造体のメンバの名前

ptrからoffsetofマクロでtypeとmemberのオフセットを引き算すればデータのアドレスを計算できます.

「((type *)(__mptr - offsetof(type, member)))」の部分です.

list_head構造体の初期化

list_head構造体の静的な初期化は,include/linux/list.hにあるLIST_HEADマクロを利用します.

list_head構造体の動的な初期化は,include/linux/list.hにあるINIT_LIST_HEAD関数を利用します.

list_head構造体の要素の追加と削除

list_head構造体の要素の追加は,include/linux/list.hにあるlist_add関数を利用します.

list_add関数では__list_add関数を呼び出しています.

双方向循環リストを理解していると処理がイメージできます.

list_head構造体の要素の削除は,list_del関数を利用します.

list_del関数は__list_del_entry関数,__list_del_entry関数は__list_del関数を呼び出します.

まとめ

C言語の連結リストを紹介しました.

具体的には,片方向リスト,双方向リスト,双方向循環リスト,Linuxカーネルにおける実例を解説しました.

これらのコードを読むことで,C言語の連結リストを深く理解できます.

他のデータ構造を知りたいあなたはこちらからどうぞ.

C言語を独学で習得することは難しいです.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

私のキャパシティもあり,一定数に達したら終了しますので,今すぐ追加しましょう!

友だち追加

独学が難しいあなたは,元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

-C LANGUAGE, TECHNOLOGY
-, , , , , , ,