データ構造基礎：Linked list
Linked listとは？
コーディングインタビューの問題で出題される事の多いLinked listですが、Linked ListはPythonの標準ライブラリでは実装されておらず、名前は知っていてもその詳細を把握していない方は多いと思います。
コーディングインタビュー以外でも、Linked listはデータ構造の１つとして把握しておいた方がいい内容なので、今回の記事ではLinked listの解説をします。
Linked listとは？
それでは、早速Linked listの構造について解説を進めていきます。こちらは図解して説明をした方が早いので、以下にLinked listのイメージ図を示します。
Nodeというのが値を格納する箱だと思って下さい。この場合は３つの箱があり、それぞれに値が格納されています。
このNodeを繋ぐ役割なのが、nextという文字が書いてあるポインタです。Nodeにはこのポインタの情報も格納されていて、これにより次のNodeの場所を知る事ができます。このように、NodeとNodeを数珠繋ぎで表現するものをLinked listといいます。
Linked listの強みとは？listとは何が違うの？
Linked listの構造の解説を行いましたが、正直それを聞いても「普通のlistと比べて何がいいのか分からない」と、思われた方が多いかと思います。
むしろ逆に、Nodeやポインタの定義が必要な分、Linked listは複雑なだけと思われた方も多いのではないでしょうか？
それでは、両者を比較して考えてみましょう。
通常のlistの構成
fig2は通常のリストの構造です。皆様、普段listはよく使用されていると思うので、ここで特段解説すべき事は無いかもしれないですが、listはindexで値を参照でき、その際にO(1)で中の値を取り出す事ができます。
また、同様に値の置き換えもO(1)で完結します。
ただし、常にindexを参照しなければいけないため、値の追加（fig2の場合に2と3の間に値を追加する場合等）や、値の削除にはO(N)の計算量がかかります。
Linked listの構成
それでは、Linked listについて計算量の観点で各オペレーションを考えてみたいと思います。
Linked listはindexが存在しないため、値の参照は、常にポインタを進める必要があるため、O(N)となります。
値の置き換えに関しては、置き換え対象の値を探すところまでは同様にO(N)ですが、置き換え行為そのものは、ポインタを差し替えるだけで済むため、O(1)となります。
また、値の削除も、置き換え同様に、削除行為そのものはO(1)で完結します。
Linked listの実装
それでは、Linked listの実装作業に進んでいきたいと思います。以下、実装方法を解説していきます。
【１】Nodeクラスの実装
fig1を見て、再度Linked listの構造を思いだしてください。Linked listはNodeブロックから構成されていて、Nodeには、何らかの値と、次のNodeへのポインタが格納されています。これを、実装すると以下のようなクラスで表現されます。
Nodeクラスを生成する度に、valに値が格納され、また、nextにはNoneが代入されます。次のNodeブロックが連結される際に、nextにはそのNodeブロックへのポインタが保持されるイメージです。
【２】Linked listクラスの実装
それでは次に、上記のNodeクラスを用いてLinked listの機能を実装していく事を考えます。Linked listは上述の通り、NodeとNodeをポインタで繋ぐ数珠つなぎのデータ構造であるため、Nodeの先頭（head）と、現在のNodeの位置（current）がわかっている必要があります。
まずはLinked listクラスを宣言し、最初に値が追加された時に、headとcurrentのポインタが一番最初（先頭）のNodeを指すようにします。
次に、値を追加するメソッド（add）を実装します。ここで大事な点は以下を正しく実装する事です。
headの位置は最初のNodeブロックから動かない
新しくNodeを生成し、値を格納する
現在のNode（current）のnextポインタが、新しいNodeを参照する
現在のNode（current）を追加した新しいNodeにする
こちらは以下のように単純に実装できます。
ここまで実装できれば、Linked listの基本は実装できた事になります。他にもNodeブロックを削除するメソッド等もあった方がいいですが、それはまたの機会に。。。
一旦、ここでLinked listが正しく動作するかテストをしたいので、Linked listのNodeをプリントするメソッドを用意します。
実装は極めて単純で、先頭のNodeブロックを取得し、nextポインタの参照がなくなるまで（Noneになるまで）、ループを回します。
ここまで実装ができたら、以下のような簡単なテストを実装し、動作確認をしてください。
この場合、コードを実行し、1, 2, 3とコンソールに表示されればOKです。
さいごに
ここまでお疲れ様でした。
次回は、このLinked listを使用して、コーディングインタビューによく出題される、「Linked listを逆に並べ替える」という典型的な問題を解いてみたいと思います。
この記事が気に入ったらサポートをしてみませんか？