[TIL]Day 6

スタックヘッダ付き接続リストノードの削除
エラーコード

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

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

コードの変更

    def popAfter(self, prev):
        delNode = prev.next
        prev.next = delNode.next
        if delNode.next == None:
            self.tail = prev
        self.nodeCount -= 1
        return delNode.data

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

なぜ間違っているのか分析してみましょう.

Doubly Linked Lists

すべてのノードが同じデータを持っていることを確認します.
頭部と尾部にノードの山を配置します.
ループ文は、次の操作を行います.

while curr.next.next

双方向接続リストを反転
エラーコード

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

コードの変更

    def reverse(self):
        answer = []
        curr = self.tail
        while curr.prev.prev:
            answer.append(curr.prev.data)
            curr = curr.prev
        if curr.prev.data != None:
            answer.append(curr.prev.data)
        return answer

まちがった理由
条件を戻して変更しない
先生コード

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

もっときれいに...
データはHeadとTail NoneではなくNoneです.
双方向接続リストノードの挿入
エラーコード

    def insertBefore(self, next, newNode):
        prevNode = next.prev
        prevNode.next = newNode
        next.prev = newNode
        newNode.prev = prevNode
        newNode.next = next

まちがった理由
ノードカウント増加、true returnなし
双方向接続リストの削除
エラーコード

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


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

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

エラー原因popat条件文から+1を削除
双方向接続リストのマージ
エラーコード

    def concat(self, L):
        last = self.getAt(self.nodeCount)
        last.next = L.getAt(1)
        L.getAt(1).prev = last
        self.nodeCount += L.nodeCount

条件を変更しましたが、コードが間違っています.

    def concat(self, L):
        if self.nodeCount == 0 and L.nodeCount > 0:
            self = L
        elif self.nodeCount > 0 and L.nodeCount > 0:
            last = self.getAt(self.nodeCount)
            last.next = L.getAt(1)
            L.getAt(1).prev = last
            self.tail.prev = L.getAt(L.nodeCount)
            self.nodeCount += L.nodeCount

最終変更コード

    def concat(self, L):
        if self.nodeCount == 0 and L.nodeCount > 0:
            self.head.next = L.getAt(1)
            self.tail.prev = L.getAt(L.nodeCount)
            self.nodeCount += L.nodeCount
        elif self.nodeCount > 0 and L.nodeCount > 0:
            last = self.getAt(self.nodeCount)
            last.next = L.getAt(1)
            L.getAt(1).prev = last
            self.tail.prev = L.getAt(L.nodeCount)
            self.nodeCount += L.nodeCount