[Python 자료구조 #연결리스트3] 이중연결리스트 : 연결된 덱

* 이중연결리스트의 응용 : 연결된 덱(linked deque)

• 먼저 덱을 단순연결리스트로도 구현할 수 있다.

• 그러나 deleteRear연산에서 문제가 생긴다. 다른 연산들은 모두 O(1)에 처리가 가능한데 비해 이 연산은 O(n)이 걸린다. 후단을 삭제하고 나면 rear가 한 칸 앞으로 움직여야 하는데, 선행 노드의 정보가 없어서 front부터 탐색해야 하기 때문이다.
• 이 문제를 해결하는 방법은 이중연결리스트를 사용하는 것이다.

출처 : 파이썬으로 쉽게 풀어쓴 자료구조

※ 이중연결리스트를 이용하면 전후단 삭제의 시간 복잡도는 모두 O(1)이 된다.

class DNode:    # 이중연결리스트는 2개의 링크를 갖는다.
    def __init__(self, elem, prev=None, next=None):
        self.data = elem    # 노드 내의 데이터필드.
        self.prev = prev    # 이전 노드를 가리키는 링크 (전단링크)
        self.next = next    # 다음 노드를 가리키는 링크 (후단링크)


class DoublyLinkedDeque:    #이중연결리스트를 이용한 연결된 데크 클래스 생성
    def __init__(self):
        self.front = None
        self.rear = None

    def isEmpty(self):
        return self.front == None

    def clear(self):
        self.front = self.rear = None

    def size(self):
        node = self.front
        count = 0
        while not node == None:
            node = node.next
            count += 1
        return count

    def display(self, msg="LinkedDeque:"):
        print(msg, end="")
        node = self.front
        while not node == None:
            print(node.data, end=" ")
            node = node.next
        print()

    def addFront(self, item):   # 전단 삽입
        node = DNode(item, None, self.front)
        if self.isEmpty():  # 덱이 비어있는 경우
            self.front = self.rear = node   
        else:
            self.front.prev = node  # front 노드의 전단링크에 새 노드의 주소를 넣음
            self.front = node   # front 변수에 새 노드의 주소를 넣음

    def addRear(self, item):    # 후단 삽입
        node = DNode(item, self.rear, None)
        if self.isEmpty():
            self.front = self.rear = node
        else:
            self.rear.next = node   # rear 노드의 후단링크에 새 노드를 넣음
            self.rear = node    # rear 변수에 새 노드의 주소를 넣음

    def deleteFront(self):  # 전단 삭제
        if not self.isEmpty():  # 덱이 비어있지 않은 경우
            data = self.front.data  
            self.front = self.front.next    # front 변수에 front 노드의 후단링크를 넣음
            if self.front == None:  # (1개의 노드를 갖는 덱일 경우)
                self.rear = None    # rear 변수에 None값을 넣는다.
            else:   # 2개 이상의 노드를 갖는 덱일 경우
                self.front.prev = None # front의 전단링크에 None값을 넣음
            return data 

    def deleteRear(self):   # 후단 삭제
        if not self.isEmpty():  # 덱이 비어있지 않은 경우
            data = self.rear.data   
            self.rear = self.rear.prev  # rear 변수에 rear 노드의 전단 링크를 넣음
            if self.rear == None:   # (1 개의 노드를 갖는 덱일 경우)
                self.front = None   # front 변수에 None값을 넣는다.
            else:   # 2개 이상의 노드를 갖는 덱일 경우
                self.rear.next = None   # rear의 후단링크에 None값을 넣음
            return data

연결된 덱 예시

dq = DoublyLinkedDeque()
for i in range(9):
    if i % 2 == 0:
        dq.addRear(i)
    else:
        dq.addFront(i)
dq.display()
for i in range(2):
    dq.deleteFront()
for i in range(3):
    dq.deleteRear()
dq.display()
for i in range(9, 14):
    dq.addFront(i)
dq.display()
------------------------------
LinkedDeque:7 5 3 1 0 2 4 6 8     
LinkedDeque:3 1 0 2 
LinkedDeque:13 12 11 10 9 3 1 0 2