今回はプログラムのデータ構造のひとつである単連結リストについてお話します。
目次
配列
数値計算のプログラムを書くうえでよく出てくるものとして配列というのがあります。配列は通し番号（インデックス、index）のついた箱に値が入っているデータ構造をしています。
配列
何か複数あるデータをまとめて扱うときには、配列はよく使われます。インデックスがついているので、プログラム上はfor文などでループさせて配列データを参照し演算処理をしていきます。
連結リスト
一方、個々のデータを電車の連結器のようなものでつないだイメージのデータ構造を考えることができます。
単連結リスト
これを連結リストと呼びます。電車に例えると、各車両はデータの値（value）と次に連結している車両がどれかという情報（next）を持っています。
連結リストのノード
この車両のことをノード（node）とかセル（cell）と呼んだりします。
headが先頭のノードで、各ノードは矢印の方向に連結されてつながっています。このように一方向に連結されているリストを単連結リストといいます。
連結リストも配列と同じようにデータを格納するための物ですが、どのような特徴があるのでしょうか。
連結リストのメリット
連結リストのメリットは、リストの途中にデータを挿入しやすいというのがあげられます。例えば、５と17の間に10の値のデータを挿入したい場合には、5と17の連結を切って、５から10に10から17につなぎ替えることで、挿入することができます。
連結リストへの挿入
これを配列で行おうとすると、まず配列のサイズを一つ増やした後、32、24、17をひとつずつ後ろにシフトしてインデックスをずらしてやる必要があります。それでようやく空いた２番の箱に10を挿入することができるわけです。
配列への挿入
このように配列の途中にデータを挿入する場合は計算量が多くなります。
逆に、途中のデータを削除する場合も同様です。連結リストの場合は、削除したいデータの連結を切って、直前のデータと直後のデータをつなぎ替えるだけの作業ですみます。
連結リストからの削除
一方、配列の場合は削除したいデータ以降のデータを今度は前方にシフトしてインデックスをずらし、最後に配列のサイズを一つ減らしてやる必要があるので、挿入と同様計算量が多くかかります。
また、配列の場合は予めデータのサイズを決めておくのが普通です。連結リストではデータが増えた分だけ連結を増やせばよいので、データサイズが予め分からないようなデータにも柔軟に対応できます。
連結リストのデメリット
反対に、連結リストのデメリットとしては、データの参照に手間がかかるということがあげれます。
配列の場合、あるインデックスのデータを参照したいときには、 a[3] のように添字の番号を指定することで、すぐに参照することができます。このような方法をランダムアクセスと言います。
一方で、連結リストの場合、指定した番号のデータをすぐに参照することは出来ません。上記のようなリストでは先頭から順番にアクセスしていき、該当するデータが見つかるまでリストをたどって行く必要があります。このようなアクセスの仕方をシーケンシャルアクセスと言います。
また、ここであげた単連結リストは矢印の方向にしかたどることが出来ません。これは先頭のデータであればすぐにアクセスできますが、末尾のデータにアクセスするためには全てのデータをたどらなければならないことを意味します。（連結リストは逆方向にもたどれるようにしたものもあります。これはこちらで解説しています。）
配列にしても連結リストにしてもメリット、デメリットがあるため、使いたいデータの処理がどのようなものかによって、どのデータ構造が適しているか考えてやる必要があります。
単連結リストのプログラム
では実際にPythonを使って単連結リストのプログラムを実装してみましょう。データとして与えられた数字を小さいものから順に並べてリストを作ることにします。リストの機能（メソッド）としては、
①データを挿入する
②データを削除する
③リストを出力する
の３つを作ります。（これら以外にも必要に応じて様々なメソッドが考えられます。）
ノードのクラス
まず、ノードを表すクラスListNodeを作ります。
class ListNode:
def __init__(self, value = None):
self.value = value
self.next = Noneノードはデータの値（value）と次に連結しているノード（next）の２つのプロパティを持っています。引数でデータの値valueを受け取り、valueプロパティに定義します。連結されている次のノード（next）は、ひとまずNone（空を意味し、連結先がない）としておきます。
リストのクラス
次に単連結リストのクラスLinkedListを定義します。
class LinkedList:
def __init__(self):
self.head = ListNode()コンストラクターでは、リストのheadプロパティにListNode()で新しいノードを作ります。headノードはリストの先頭のノードで、値は持っていないものとします。
データを挿入するメソッド
次にデータを挿入するメソッドinsertを定義します。
def insert(self, value):
node = self.head.next
prev = self.head
while (node != None) and (node.value < value):
prev = node
node = node.next
new = ListNode(value)
prev.next = new
new.next = node最初にnode、prevという２つを定義しますが、nodeが現在アクセスしているノードで、prevはその一つ前のノードを表します。最初は、実際データが入っている先頭のノード（head.next：headの次のノード）をnodeに、headノードをprevに定義しています。
次のwhile文でリストをたどっていきます。
prev = node
node = node.next
とすることで、prevを現在のnode、nodeをその次のノードに更新しています。
while文は、nodeがNoneではない間、かつnodeの値が引数valueより小さい間繰り返されます。nodeがNoneになるということは、リストの最後まで来たということを意味しています。また、valueの大小を比較することにより、valueより大きな値のノードまで来たらリストをたどるのをやめることになります。
最後に、ノードのつなぎ替えを行います。
new = ListNode(value)
prev.next = new
new.next = node
newに引数valueをデータにもつノードを新しく作成し、prev.next（prevの次のノード）をnewとし、new.next（newの次ノード）をnodeとします。
データを削除するメソッド
続いてデータを削除するメソッドdeleteを定義します。
def delete(self, value):
node = self.head.next
prev = self.head
while node != None:
if node.value == value:
prev.next = node.next
node = None
node = prev.next
else:
prev = node
node = node.next挿入とよく似ていますが、whileの繰り返しはリストの末尾まで行っています。これはリストの中に複数の削除対象のノードがある場合に対応するためです。
if文でノードの値と引数valueが一致すると、その対象ノードnodeを削除するようにしています。削除はまずprev.next（prevの次ノード）をnode.next（nodeの次ノード）としてprevの連結をつなぎ替えます。これで、nodeは切り離されたので、node=Noneでnodeを空にします。その後でnode=prev.nextとすることで、次のノードに更新されます。
リストを出力するメソッド
最後にリストを出力するメソッドprintを作成します。
def print(self):
node = self.head.next
while node != None:
print(node.value, end=" ")
node = node.next
print() リストを最後までたどり、print関数（これはメソッドではなく、Pythonの標準関数）でノードの値を出力しています。
リストの作成
リストを作成するのは例えば以下のように行います。
list = LinkedList()
list.insert(10)
list.insert(5)
list.insert(32)
list.insert(17)
list.insert(24)
list.insert(3)
list.print()list=LinkedList()で、list変数に新しくリストを定義します。次のlist.insert(10)は10をデータとしてリストに挿入しています。以下数値データを挿入し、最後list.print()で出力します。すると、次のように整列したリストデータが出力されます。
3 5 10 17 24 32
続けて、このリストから17を削除するには、
list.delete(17)
list.print()とします。
3 5 10 24 32
全体のプログラム
ここで説明したプログラム全体を以下にあげておきます。
class ListNode:
def __init__(self, value = None):
self.value = value
self.next = None
class LinkedList:
def __init__(self):
self.head = ListNode()
def insert(self, value):
node = self.head.next
prev = self.head
while (node != None) and (node.value < value):
prev = node
node = node.next
new = ListNode(value)
prev.next = new
new.next = node
def delete(self, value):
node = self.head.next
prev = self.head
while node != None:
if node.value == value:
prev.next = node.next
node = None
node = prev.next
else:
prev = node
node = node.next
def print(self):
node = self.head.next
while node != None:
print(node.value, end=" ")
node = node.next
print()
list = LinkedList()
list.insert(10)
list.insert(5)
list.insert(32)
list.insert(17)
list.insert(24)
list.insert(3)
list.print()
list.delete(17)
list.print()