以前の記事で連結リストの実装を簡単に紹介しました。
実を言うと前回は連結リストの中でも一番シンプルで簡単な線形リストの片方向連結リストの解説を行いました。
ですが実際は連結リストはいくつかの種類があり、今回の記事ではそれらを解説したいと思います。
片方向リスト vs 双方向リスト
以前の記事(上に貼っている記事)で紹介した連結リストは片方向リストでした。片方向リストは先頭があってそこから最後のノードに向かって順番に接続している状態です。
それに対して双方向リストは先頭から最後のノードという向きだけでなく、最後から先頭の向きもノードが接続している状態です。
＊ノードは下の図の箱のことです。
前回の記事のおさらいですが、(片方向)連結リストは先頭から最後のノードまでの繋がりを(最後のノードを除く)各々全てのノードが次のノードの情報を持つことで表現していました。
なので、双方向リストは次のノードの情報に加えて前のノードの情報も持つことで前後の繋がりを表現しています。
双方向リストを実際に実装してみましょう。
class LinkedList:
class Node:
def __init__(self, payload):
self.payload = payload
self.next = None
self.prev = None
def __init__(self):
self.head = None
def addNode(self, newpayload):
newnode = LinkedList.Node(newpayload)
if self.head == None:
self.head = newnode
return
else: #最後のノードに連結するケース
runner = self.head
while runner.next != None:
runner = runner.next
runner.next = newnode
runner.next.prev = runner
links = LinkedList()
links.addNode(26)
links.addNode(99)
links.addNode(127)
links.addNode(42)
links.addNode(367)
＊わかりやすくするために双方向リストにするために片方向リストから追加したコードをこの書体に変えています
コードとしては、
(片方向)連結リストはnextという変数で次のノードの情報を持っていましたが、双方向リストはそれに加えてprev(previouの略)という変数で前の情報を持っています。
それにより双方向リストでは先頭から最後のノードまで、最後のノードから先頭までの向きのルートも接続させることはできます。
連結リストの続きの記事が気になる方はこちらから
参考文献
学術論文ではアウトですが..
ご勘弁を
