トップ > データ構造 Part3「連結リスト」

データ構造 Part3「連結リスト」

はじめに

前回の記事では動的配列について解説しました。
動的配列はリストという抽象データ構造を実装したものの1つでした。

リストを実装したもう1つのデータ構造に連結リストです。
静的配列を使わず素朴なアイデアで設計されています。
動的配列との比較も注目ポイントです。

 

目次

  1. 連結リストとは
  2. プログラムでの連結リスト
  3. 連結リストのアイデア
  4. 想定される操作とその最悪時間計算量
  5. 動的配列との比較
  6. さいごに

 

連結リストとは

必要最低限のメモリ領域で動く様に設計されています。
要素が追加された際に必要なメモリ領域を確保し、
その領域のアドレスを覚えることでリストとします。

 

プログラムでの連結リスト

 

連結リストのアイデア

最初の要素と最後の要素のアドレスも覚えておきます。
例えば i 番目の要素を参照された場合は
最初の要素から順番に次の要素を参照することで実現します。

List<Int> linkedList = new LinkedList<>();
linkedList.add(1);
linkedList.add(2);
System.out.println(linkedList.get(1));

linkedList
 ┣━ size  : 2
 ┣━ first : 1000
 ┗━ last  : 500

{
  value  : 1
  before : null
  next   : 500
} (1000)

{
  value  : 2
  before : 1000
  next   : null
} (500)

 

想定される操作とその最悪時間計算量

参照（ get(i) ）

i 番目の要素を参照する場合は、先頭もしくは末尾から辿ります。
最悪の場合は n / 2 回辿ることになりますので O(n) です。

挿入と削除（ insert(e, i), delete(i) ）

挿入や削除の際は、参照と同様にアドレスを辿る必要があります。
参照が完了したらアドレスを書き換えるだけなので O(1) で大丈夫です。
参照に O(n) かかるので、全体の最悪時間計算量は O(n) です。

最初と最後の要素の場合は、辿る必要がないので特別に O(1) です。

リストの想定される操作 時間計算量
参照 get(i) O(n)
挿入 insert(e, i) O(n) （先頭と末尾の要素は O(1) ）
削除 delete(i) O(n) （先頭と末尾の要素は O(1) ）

 

動的配列との比較

リストの想定される操作 動的配列 連結リスト
参照 get(i) O(1) O(n)
挿入 insert(e, i) O(n) O(n)
削除 delete(i) O(n) O(n)

 

さいごに

この記事では連結リストをのアイデアや性能を紹介しました。
リストを実装したもう1つのデータ構造である動的配列と
比較すると特定の条件で優秀な場合があります。

キューを実装する場合には使えるかもしれませんが、
参照が遅いというデメリットがあるので、
相当自信がある場合のみ使うのが良いと思います。

ここまでリストについて紹介してきましたが少し考え方を変えます。
リストに制限を加えることで高速に動作させるという考え方もあります。
次回以降でスタックやキューを紹介したいと思います。