前回、リスト型のデータ構造である単連結リストについてお話しました。
単連結リストについて解説します。連結リストのメリット、デメリット、データの挿入、削除の方法についても説明しています。また、Pythonでプログラムを作ります。
cattech-lab.com
2021-06-24 10:11
今回は同じ連結リストの一種である双方向連結リストについて解説したいと思います。
双方向リスト
単連結リストはリストの先頭から一方向にしかたどることが出来ませんでした。これに対して逆側にも連結して前方のノードの情報を持っているリストを双方向リストと呼びます。
双方向リストの各ノードは、データの値（value）と後方のノード（next）に加え前方のノード（prev）のノード情報を持っています。
双方向リストは逆向きにもリストをたどることが出来ます。また、前方のノードの情報を持っているため、途中の指定したノードに対して、挿入や削除を楽に行うことができます。
双方向リストは、例えばソフトウェアやブラウザなどで、操作やページを前に戻したり、次に進めたりする仕組みに使われていたりします。
双方向循環リスト
双方向リストの場合、リストの末尾を参照するためには、先頭からたどるか、headと同様に末尾を表すノードを作っておく必要があります。このため、次の双方向循環リストがよく使われます。
双方向循環リストは、双方向リストの末尾を先頭のheadノードに連結させた構造をしています。
こうすると、リストの末尾を参照したい場合、headの前方ノード（head.prev）を見ればよいことがわかります。これでheadを起点として前方にも後方にもリストを自由に移動したり、参照したりすることができます。
双方向循環リストのプログラム
では、双方向循環リストのプログラムをPythonで作ってみましょう。
プログラム作成にあたって具体的な問題を考えた方がイメージしやすいので、次のような問題を考えます。
問題：
A、B、C、D、E、F、Gの７人が次のように一列に並びます。
①まず、A、B、C、D、E、Fの６人がこの順番に並びました。
②先頭の一人が列から外れました。
③Gがやってきて、Dの前に割り込みました。
④Eが行列から外れました。
では現在、Cは後ろから数えて何番目にいるでしょうか？
文章で書いてあると一見ややこしそうですが、リストに必要な操作（メソッド）の形で書いてみましょう。それぞれの出来事は、次のリスト操作に対応します。
①リストの末尾にデータを追加する
②リストの先頭のデータを削除する
③指定したデータの前方にデータを挿入する
④指定したデータを削除する
⑤指定したデータの位置をリストの末尾からカウントする
⑤は最後の問題文に対応しています。
では、実際にプログラムを作っていきます。単連結リストのプログラムをベースにしていくとよいでしょう。
まず、下準備としてノードを定義するクラスListNodeを作ります。
class ListNode: def __init__(self, value = None): self.value = value self.next = None self.prev = None
双方向リストなので、value（値）、next（後方ノード）、prev（前方ノード）のプロパティを持たせます。
次に双方向循環リストのクラスDoublyLinkedListを定義します。
class DoublyLinkedList: def __init__(self): self.head = ListNode() self.head.next = self.head self.head.prev = self.head
コンストラクターでは、先頭のheadノードを作ります。最初は、データのノードがないので、headの後方（head.next）と前方（head.prev）はhead自身としておきます。
※循環リストではheadにデータを持たせる構造にすることも出来ますが、ここではheadは値を持たないダミーのノードとして扱います。
①リストの末尾にデータを追加する
ではメソッドを作っていきましょう。まずは、リストの末尾にデータを追加するメソッドadd_lastです。
def add_last(self, value): new = ListNode(value) last = self.head.prev new.next = self.head new.prev = last last.next = new self.head.prev = new
まず、newに新しくノードを作っています。lastはheadの前方を参照しているので、リストの末尾のノードです。
これを元につなぎ替えを行います。
new.next = self.head →newの後方にheadをつなぐ
new.prev = last →newの前方にlast
last.next = new →lastの後方にnew
self.head.prev = new →headの前方にnew
これでnewに連結している４本の連結器がつながりました。
②リストの先頭のデータを削除する
次にリストの先頭のデータを削除するメソッドdelete_firstを定義します。
def delete_first(self): first = self.head.next self.head.next = first.next first.next.prev = self.head first = None
firstをheadの次のノードとします。firstの接続をつなぎ替えて、firstを削除します。
self.head.next = first.next →headの後方にfirstの次のノードをつなぐ
first.next.prev = self.head →firstの次のノードの前方にhead
first = None →firstを削除
③指定したデータの前方にデータを挿入する
指定したデータの前方に新しいノードを挿入するメソッドinsertを作ります。
def insert(self, value, value2): node = self.head.next while node != self.head: if node.value == value2: new = ListNode(value) new.next = node new.prev = node.prev node.prev.next = new node.prev = new return else: node = node.next
nodeを現在アクセスしているノードとして先頭からリストをたどっていきます。nodeの値が２番めの引数value2と同じであれば、その前に新しくノードnewを挿入します。つなぎ替えはこれまでと同様に行います。
new.next = node →newの後方にnode
new.prev = node.prev →newの前方にnode.prev
node.prev.next = new →node.prevの後方にnew
node.prev = new →nodeの前方にnew
※ただし、２番目と４番目のつなぎ替えの順番が逆だと、new.prevがnewになってしまうので順番に注意してください。
④指定したデータを削除する
続いて、指定したデータを削除するメソッドdelete_valueを定義します。
def delete_value(self, value): node = self.head.next while node != self.head: if node.value == value: node.prev.next = node.next node.next.prev = node.prev node = None return else: node = node.next
これもリストの先頭からたどっていき、nodeの値と引数valueが同じになったら、そのノードを削除します。ここも同様に前後の連結をつなぎ替えます。
⑤指定したデータの位置をリストの末尾からカウントする
最後に、指定したデータの位置をリストの末尾からカウントしていくメソッドcount_backを作成します。
def count_back(self, value): node = self.head.prev count = 0 while node != self.head: count += 1 if node.value == value: return count node = node.prev return -1
末尾からカウントするため、head.prevでheadノードの前方（すなわちリストの末尾）からたどっていきます。nodeの値が引数の値と一致したら、カウントを返します。もし見つからなければ、-1を返しています。
問題を解く
プログラムが出来たので、実際に問題を解きましょう。
list = DoublyLinkedList() #リストの作成list.add_last("A") #①Aが並ぶlist.add_last("B") #①Bが並ぶlist.add_last("C") #①Cが並ぶ list.add_last("D") #①Dが並ぶ list.add_last("E") #①Eが並ぶ list.add_last("F") #①Fが並ぶ list.delete_first() #②列の先頭が外れる list.insert("G", "D") #③GがDの前に割り込む list.delete_value("E") #④Eが列から外れる list.print() #リストを出力count = list.count_back("C") #⑤Cの後ろからの順番を数えるprint(count) #答えを出力
list変数にリストを作成して、それぞれのメソッドを使い問題文のとおり順番に実行していきます。
さて答えはいくつになりましたか？
全体のプログラム
今回説明したプログラム全体をあげておきます。
class ListNode: def __init__(self, value = None): self.value = value self.next = None self.prev = Noneclass DoublyLinkedList: def __init__(self): self.head = ListNode() self.head.next = self.head self.head.prev = self.head def add_last(self, value): new = ListNode(value) last = self.head.prev new.next = self.head new.prev = last last.next = new self.head.prev = new def insert(self, value, value2): node = self.head.next while node != self.head: if node.value == value2: new = ListNode(value) new.next = node new.prev = node.prev node.prev.next = new node.prev = new return else: node = node.next def delete_first(self): first = self.head.next self.head.next = first.next first.next.prev = self.head first = None def delete_value(self, value): node = self.head.next while node != self.head: if node.value == value: node.prev.next = node.next node.next.prev = node.prev node = None return else: node = node.next def print(self): node = self.head.next while node != self.head: print(node.value, end=" ") node = node.next print() def count_back(self, value): node = self.head.prev count = 0 while node != self.head: count += 1 if node.value == value: return count node = node.prev return -1 list = DoublyLinkedList()list.add_last("A")list.add_last("B") list.add_last("C") list.add_last("D") list.add_last("E") list.add_last("F") list.delete_first() list.insert("G", "D") list.delete_value("E") list.print()count = list.count_back("C")print(count)
まとめ
数値計算では、まとまった数値データを扱うときには配列で済ませるということが多いかもしれません。ただ、問題によってはこのようなリスト構造を考えたほうがデータが扱いやすく、スマートに処理できることもよくあるので、ぜひリストも使ってみてください。
全体の目次
