pythonで双方向リスト

目的

双方向リストとは何か，Pythonでの実装を通して理解を深めましょう．
この記事で実装した双方向リストは，以下のリポジトリから利用できます．
(TBU)

双方向リストとは

双方向リストの仕様

• ランダムアクセス不可
• Nodeが連結してできており，各Nodeは，次のNodeを示すポインタと，前のNodeを示すポインタを持つ
• Headは先頭の要素を示すポインタ，Tailは末尾の要素を示すポインタである
• リストの長さを表すLengthプロパティをもつ

双方向リストの各種メソッドの計算量

先頭，末尾の要素に対するInsertion，RemovalはO(1)となります．SinglyLinkedListは，末尾の要素の削除はO(N)でしたから，それにくらべると，計算量小さいです．Searching，AccessはO(N)となります．Technicalには，探すインデックスがLengthの半分より大きいか小さいかで場合を分けるので，計算量はO(N/2)ですが，以前としてO(N)のオーダにとどまります．
双方向リストは，単方向リストに比べ，Previousのポインタを持つことで便利になっています．Searchingは半分の時間で行うことが可能です．しかしながら，Previousポインタをもつことにより，メモリの使用量は増します．

双方向リストの骨組みの実装例

class Node:
    def __init__(self, val):
        val = self.val
        next = None
        prev = None

class DoublyLinkedList:
    def __init__(self):
        head = None
        tail = None
        length = 0

Push

• 新しいNodeをつくる
• HeadプロパティがNoneであるならば，HeadとTailを新しく作ったNodeにする
• そうでないならば，TailのNextプロパティを新しく作ったNodeにする
• 新しく作ったNodeのPrevプロパティを元のTailにする
• Lengthをインクリメントする
• リスト全体を返す

    def push(self,val):
        newNode = Node(val)
        if (not self.head):
            self.head = newNode
            self.tail = self.head
        else:
            self.tail.next = newNode
            newNode.prev = self.tail
            self.tail = newNode

        self.length = self.length + 1
        return self

Pop

• Headが存在しなければ，Noneを返す
• のちに返却するため，現在のTailを変数に保存する
• Lengthが１のとき，HeadとTailをNoneにする
• TailをひとつまえのNodeにする
• 新しいTailのNextをNoneにする
• Lengthをデクリメントする
• 取り除いたNodeを返す

    def pop(self):
        if(not self.head):
            return None

        currentTail = self.tail
        if (self.length == 1):
            self.tail = None
            self.head = None
        else:
            self.tail = self.tail.prev
            self.tail.next = None
            currentTail.prev = None

        self.length = self.length - 1
        return currentTail

shift

• lengthが０ならば，Noneをかえす
• 現在のHeadを変数に保存する（OldHead）
• Lengthが１のとき，HeadをNoneにし，TailをNoneにする
• HeadをOldHeadのNextにする
• Legthをデクリメントする
• 取り除いたNodeを返す

    def shift(self):
        if (self.length == 0):
            return None
        oldHead = self.head
        if (self.length == 1):
            self.head = None
            self.tail = None
        else:
            self.head = oldHead.next

        self.length = self.length - 1
        return oldHead

unshift

• 受け取った値でNodeをつくる
• もし，Lengthが０ならば，Headを新しいNodeにし，Tailも新しいNodeにする
• HeadのPrevを新しいNodeにする
• 新しいNodeのNextをHeadにむける
• Headを新しいNodeにする
• Lengthをインクリメントする
• リストを返却する

    def unshift(self, val):
        newNode = Node(val)
        if (self.length == 0):
            self.head = newNode
            self.tail = newNode
        else:
            self.head.prev = newNode
            newNode.next = self.head
            self.head = newNode
        self.length = self.length + 1
        return self

get

• インデックスが０より小さいか，Lengthと等しいまたはより大きい場合，Noneを返す
• インデックスがLengthの半分よりも小さいまたは等しい場合，Headからリストを順にたどり，指定されたインデックスのNodeを返す
• インデックスがLengthの半分よりも大きい場合，Tailからリストを順にたどり，指定されたインデックスのNodeを返す

    def get(self, index):
        if ((index < 0) or (index > self.length)):
            return None

        halfOfLength = self.length // 2
        if (index <= halfOfLength):
            counter = 0
            current = self.head
            while(counter != index):
                current = current.next
                counter = counter + 1
            return current
        elif (index > halfOfLength):
            counter = self.length - 1
            current = self.tail
            while(counter != index):
                current = current.prev
                counter = counter - 1
            return current

set

• 受け取ったインデックスのGetメソッドの結果を変数に格納する
• 結果がValidであれば，受け取った値をそのNodeのValueとする
• Trueをかえす
• そうでなければFalseを返す

    def set(self, index, val):
        targetNode = self.get(index)
        if(targetNode):
            targetNode.val = val
            return True
        else:
            return False

insert

• インデックスが０より小さいか，Lengthより大きい場合，Falseを返す
• インデックスが０のとき，Unshiftする
• インデックスがLengthと同じ時，Pushする
• 受け取ったインデックスより１小さいNodeをGetメソッドで得る
• 受け取った値でNodeをつくる
• index - 1のNodeのNextを新しいNodeにし，新しいNodeのPrevをindex - 1のNodeにする．index + 1のNodeのPrevを新しいNodeにし，新しいNodeのNextをindex + 1のNodeにする
• Lengthをインクリメントし，Trueを返す

    def insert(self, index, val):
        if((index < 0) or (index > self.length)):
            return False
        if (index == 0):
            self.unshift(val)
        if (index == self.length):
            self.push(val)
        prevNode = self.get(index - 1)
        newNode = Node(val)
        nextNode = prevNode.next
        prevNode.next = newNode
        newNode.prev = prevNode
        nextNode.prev = newNode
        newNode.next = nextNode
        self.length = self.length + 1

        return True

remove

• indexが０より小さいか，Lengthより大きいか，Lengthとおなじ時はNoneを返す
• Indexが０ならば，Shiftする
• IndexがLength-1と等しいならば，Popする
• とりのぞくNodeをGetメソッドを使って得る
• 見つかったNodeのNextをひとつまえのNodeのNextにし，PrevをひとつあとのNodeのPrevにする
• 見つかったNodeのNextとPrevをNoneにする
• Lengthをデクリメントする
• 取り除いたNodeを返す

    def remove(self, index):
        if((index < 0) or (index >= self.length)):
            return None
        if (index == 0):
            self.shift()
        if (index == self.length - 1):
            self.pop()
        removedNode = self.get(index)
        removedNode.prev.next = removedNode.next
        removedNode.next.prev = removedNode.prev
        removedNode.next = None
        removedNode.prev = None

        self.length = self.length - 1
        return removedNode

reverse

• リストのHeadとTailを入れ替える
• リストを走査し，各NodeのNextをPrevに，PrevをNextに置き換える

    def reverse(self):
        node = self.head
        self.head = self.tail
        self.tail = node

        tmpPrev = None
        tmpNext = None
        while(node):
            tmpPrev = node.prev
            tmpNext = node.next
            node.next = tmpPrev
            node.prev = tmpNext
            node = node.prev

        return self