[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

더 깔끔하다...
데이터가 None 인거지 헤드와 테일이 None이 아니다.

양방향 연결 리스트 노드 삽입
틀린 코드

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

틀린이유
노드카운트 증가와 트루 리턴 안함

양방향 연결 리스트 삭제
틀린코드

    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