[파이썬 자료구조] 더블 링크드리스트 (이중 연결리스트)

이중 연결리스트는 한 노드에서 뒤로도 이동하고 앞으로도 이동할 수 있는 연결리스트를 의미합니다.

따라서 Node class에 데이터에 대한 정보와 그 다음 노드에 대한 정보, 그리고 추가로 그 이전에 노드에 대한 정보도 담아 두어야 합니다. 

 

그리고 여기 이중 연결리스트에서는 head 와 tail 부분에 dummy node를 하나씩 추가로 두어 모든 노드의 생김새가 똑같도록 하였습니다.

 

이 외에 부분은 기본 연결리스트와 거의 동일하며 코드가 조금 더 간결해 진 것을 볼 수 있습니다.

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


class DoublyLinkedList:

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

    def __repr__(self):
        if self.nodeCount==0:
            return 'DoubleLinkedList is empty'
        s = ''
        curr = self.head.next
        while curr.next is not None:
            s += repr(curr.data)
            if curr.next is not self.tail:
                s += ' -> '
            curr = curr.next
        return s


    def getLength(self):
        size=0
        curr= self.head.next
        while curr is not None:
            size+=1
            curr=curr.next
        size-=1
        return(size)

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


    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None

        if pos > self.nodeCount // 2:
            i = 0
            curr = self.tail
            while i < self.nodeCount - pos + 1:
                curr = curr.prev
                i += 1
        else:
            i = 0
            curr = self.head
            while i < pos:
                curr = curr.next
                i += 1

        return curr


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


    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)


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


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


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

	
    def concat(self, L):
        self.tail.prev.next=L.head.next
        L.head.next.prev=self.tail.prev
        self.tail=L.tail
        self.nodeCount+=L.nodeCount