C LANGUAGE TECHNOLOGY

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

悩んでいる人

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

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

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOSの授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校コンピュータサイエンス学部2021年の世界大学学術ランキングで20位)で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発
  • プログラミング歴15年以上,習得している言語: C/C++,Java,Python,Ruby,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開

こういった私から学べます.

連結リスト

連結リスト(linked list)とは,順序付きデータ構造として定義されるデータ構造です.

※連結リストのことを単にリストと省略することが多いです.

また,C言語ではリストは,主に構造体で定義されます.

構造体を学びたいあなたはこちらからどうぞ.

C言語 構造体
【C言語】構造体とは【定義,変数,アクセス,引数,戻り値,ポインタ,ビットフィールド】

こういった悩みにお答えします. こういった私から学べます. 目次1 構造体2 構造体の定義3 構造体の変数4 構造体のアクセス4.1 構造体メンバへのアクセス 4.2 構造体変数の初期化4.3 構造体 ...

続きを見る

また,C言語のリストを理解するためには,ポインタの知識が必須です.

ポインタを学びたいあなたはこちらからどうぞ.

C言語 ポインタ
【C言語】ポインタとは

こういった悩みにお答えします. こういった私から学べます. 目次1 ポインタ2 ポインタ変数2.1 ポインタ演算子の使い方2.2 ポインタ変数を利用するコード3 ポインタと関数の引数:値渡しと参照渡し ...

続きを見る

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カーネルを学びたいあなたはこちらからどうぞ.

Linuxカーネル
元東大教員から学ぶLinuxカーネル

こういった私から学べます. Linuxカーネルとは,C言語で開発されたオープンソースのOSです. Linuxカーネルは主に以下のコンピュータで広く利用されています. スーパーコンピュータ サーバ An ...

続きを見る

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言語】スタックとは【x64のアセンブリ言語で解説】

こういった悩みにお答えします. こういった私から学べます. 目次1 スタック2 C言語のスタック3 x64の命令セットアーキテクチャでスタックを操作するpush/pop命令4 まとめ スタック スタッ ...

続きを見る

C言語 キュー
【C言語】キューとは【優先度キューの二項ヒープを紹介】

こういった悩みにお答えします. こういった私から学べます. 目次1 キュー2 C言語のキュー3 C言語の優先度キューの例「二項ヒープ」4 まとめ キュー キューとは,データを先入れ先出し(First ...

続きを見る

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

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

友だち追加

独学が難しいあなたは,C言語を学べるおすすめのオンラインプログラミングスクール4社で自分に合うスクールを見つけましょう.

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