Algorithm & Data Structure - Linked List(3/Doubly Linked List)

Doubly Linked List

これまで,我々が処理してきた接続リストは,いずれも自分の後ノードのみを見て,片側にしか移動できない接続リストである.

(少なくとも一度はどこかで見たことがありますが、前の人だけを見て、自分の帽子の色を調整します)
このように接続リストを実現すると,値の増加が速く,これらはいずれも良好であるが,後の要素を得るためには長い時間がかかり,またあるノードの前のノードを知るためには最初から巡回しかできないなどの欠点が多い.
そこで、今回はもう少し適用して、双方向接続リストを作成し、各ノードに後ノードの情報だけでなく、自分の前ノードの情報も格納したいと思います.
つまり、今回作成する双方向接続リストは、ヘッダとテールにノードが山積みになり、各ノードを前後に移動できる接続リストです.
まず,各ノードには独自の前後ノードの情報が必要であるため,まずノードの構造を変える.

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

に示すようにprevプロパティを追加することで実現できます.
次に、双方向接続リストが実装され、デフォルトの空のリストの構造はヘッダ<>テール構造であり、ヘッダの後ろはテールであり、テールの前はヘッドリード構造である.

class LinkedList:
    def __init__(self):
    	self.head = Node(None)
        self.tail = Node(None)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.nodeCount = 0

に示すように、ヘッダとテールに空のスタックノードを配置し、両者の関係(next,prev)を指定します.
これで、ヘッドとフレームは同じ形状(両端にスタックノードが1つある)で、前後とも実行でき、以前に実現した演算をより簡単にすることができます.
前に作成した演算手順に従って実現します.

特定の要素を参照

一部の要素参照と

def getAt(self, pos):
    if pos < 0 or pos > self.nodeCount+1:
    	return None
    i = 0
    curr = self.head
    while curr.next.next:
    	curr = curr.next
        i+=1
    return curr

として表すことができるしかし,このように実現すると,後続ノードへのアクセス時間は以前と同じであるためprevを作成する意味がないため,リストの後続ノードへのアクセス時に末尾からprevドメインへのアクセスを実現する.

def getAt(self, pos):
    if pos < 0 or pos > self.nodeCount+1:
    	return None
    if pos > self.nodeCount // 2:
    	i = self.nodeCount+1
        curr = self.tail
        while i > pos:
            curr = curr.prev
            i-=1
    else:
    	i = 0
        curr = self.head
        while i < pos:
            curr = curr.next
            i+=1
    return curr

に示すように、取得するノードに後でアクセスするインデックスがリストの全長の半分を超え、そうでなければ前からアクセスする論理を作成できます.

リスト巡回

リスト巡回は末尾にスタックノードがあるため,前と似ているが,繰返し文の条件としてcur.next.nextが存在するかどうかを確認する必要があります(tail前ノードよりもパレードに出ないでください).

def traverse(self):
    arr = []
    curr = self.head
    while curr.next.next:
    	curr = curr.next
        arr.append(curr.data)
    return arr

として表すことができる
また、prev属性がノードに付与されているため、逆巡回も可能である.

def reverse(self):
    arr = []
    curr = self.tail
    while curr.prev.prev:
    	curr = curr.prev
        arr.append(curr.data)
    return arr

末尾と同様に、ヘッダにもスタックノードがあるため、重複文の条件をチェックするとcurrになります.prev.prevで確認します.

全長の取得

ましてや、nodeCountプロパティで入手できることがわかります.

要素の挿入

要素挿入の場合、ヘッダとテールにスタックノードを追加することでヘッダとテールを調整する煩わしいプロセスはなくなりましたが、prevプロパティがノードに追加されるにつれてnext関係だけでなくprev関係も指定します.

def insertAfter(self, prev, newNode):
    next = prev.next
    newNode.next = next
    newNode.prev = prev
    prev.next = newNode
    next.prev = newNode
    self.nodeCount += 1
    return True

に示すように、insertAfterを実装することができる.
今回はgetAtを利用してinsertAtを実現します.

def insertAt(self, pos, newNode):
    if pos < 1 or pos > self.nodeCount+1:
    	return False
    prev = self.getAt(pos-1)
    return self.insertAfter(prev, newNode)

として表すことができる
頭部と尾部の構造が同じであるため、insertAfterと同じ機能を実現するために、双方向の特性を用いてinsertBeforeを実現することもできる.

def insertBefore(self, next, newNode):
    prev = next.prev
    newNode.prev = prev
    newNode.next = next
    next.prev = newNode
    prev.next = newNode
    self.nodeCount += 1
    return True

3つの要素挿入演算が実現されました.
ちなみに、上記の例ではinsertAfterによりinsertAtを実現しているが、insertBeforeにより実現してもよい.

要素の削除

今回は挿入要素と同様にpopat,popAfter,popBeforeを実現
まずpopAfterを実現します

def popAfter(self, prev):
    curr = prev.next
    next = curr.next
    prev.next = next
    next.prev = prev
    self.nodeCount -= 1
    return curr.data

として表すことができるここでprevは、消去するノード(cur)の前のノードであるため、消去する必要があるノードはcurに格納され、消去する必要があるノード(cur)の次のノードはnextに格納される.
リストからcurrを削除するとprevとnextが接続されなければならないので、両方を接続してnodeCountを1つ減らすことができます.
次に、ノードを削除するデータを返します.
popbeforeは、双方向接続リストの構造(対称構造)のため、popAfterと同じであってもよい.

def popBefore(self, next):
    curr = next.prev
    prev = curr.prev
    prev.next = next
    next.prev = prev
    self.nodeCount -= 1
    return curr.data

として表すことができる論理はpopAfterと同じです.
popAfter、popBeforeで簡単にpopAtを実現することも可能です.

def popAt(self, pos):
    if pos < 1 or pos > self.nodeCount:
    	raise IndexError
    prev = self.getAt(pos-1)
    return self.popAfter(prev)
    ## or
    # next = self.getAt(pos+1)
    # return self.popBefore(next)

に示すように、popAfterで実現するかpopBeforeで実現するか(論理が同じなので効率が同じ)を任意に選択できます.
popAtは誤ったインデックスが入力されたことのみを確認し,実際の削除ロジックはpopAfter/popBeforeに委任する.

集計リスト

リストのマージは、以前に作成した接続リストと同様に実行できます.ただし、ヘッダノード、テールノードにはスタックノードが含まれており、prevプロパティがノードに追加されていることに注意してください.
このような変更点selftail.next=L.headはselfにアクセスできません.tail.prev.next = L.head.スタックノード以外のノードをnextで接続します.

def concat(self, L):
    if L.nodeCount == 0:
    	return
    elif self.nodeCount == 0:
        self.__dict__.update(L.__dict__)
    self.tail.prev.next = L.head.next
    L.head.prev = self.tail.prev
    self.tail = L.tail
    self.nodeCount += L.nodeCount

として表すことができる
この演算は、Lとself(双方向接続リストインスタンス)への演算であり、戻り値はありません.selfを変更する操作であるため、selfが空の接続リストである場合、self=Lのようにselfを変更することはできない.dict__.updateを使用してselfを構成するすべての要素をLを構成する要素に変更することで、selfをLに変換する効果が得られます.

整理する

このように,一方向接続リストと双方向接続リストまで調べた.次の記事では、双方向リンクリストを使用してLeetCodeの質問に答えます.
接続リストは不思議で、リストの要素同士がチェーンのように接続されて移動します.ある角度から見ると、地下鉄路線、ネットの後ろ/前へ行くなどに似ています.