アルゴリズムとデータ構造 - リスト

bmf-san アルゴリズムとデータ構造
#連結リスト#片方向リスト

概要

アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。

実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。

リスト（線形リストの片方向リスト）

  • データを一直線上に並べた構造
    • 各ノードは次のノードへのポインタを持つ
  • データの追加や削除は容易だが、アクセスには時間がかかる
  • リストでは、データは連続したメモリ領域に格納される必要はない
    • 一般的には離れた領域に格納される

計算時間

リストに格納されているデータ数をnとする。

データへのアクセス

  • O(n)
    • データの先頭から順次アクセス（シーケンシャルアクセス）する必要があるため、線形時間となる

データの追加

  • O(₁)
    • 追加箇所へのデータアクセスは完了しているという前提で、ポインタを2つ差し替えるだけなので定数時間で済む

データの削除

  • データの追加と同様

実装

線形リスト

片方向リスト

  • 構造体Listにはリストの先頭ノードを格納しておく
    • リストのデータアクセスを順次アクセスで行うため
  • add
    • リストの末尾にノードを追加するメソッド
  • insert
    • リストの指定したノードの手前にノードを追加追加するメソッド
      • 追加する位置を特定する→追加位置の一つ手前のポインタと追加するノードのポインタを調整
      • 追加する位置を特定する時は、ループ内で次のノードのポインタを参照して次のノードの値が指定した値とマッチするか判定する
  • ノート singly_linked_list

参考

関連