원형연결리스트의 응용: 연결된 큐

6.4 원형연결리스트의 응용:연결된 큐

큐도 연결된 구조로 구현할 수 있는데, 이러한 큐를 연결된 큐(linked queue)라고 한다. 연결된 큐도 크기가 제한되지 않고 필요한 메모리만 사용한다는 장점과, 코드가 더 복잡하고 링크 필드 때문에 메모리 공간을 더 사용하는 단점.

연결된 큐를 구현하는 가장 간단한 방법은 다음과 같이 단순 연결리스트를 사용하는 것으로. 맨 앞과 뒤에 있는 노드를 front와 rear가 가리키는 구조이다. 물론 삽입은 후단(rear), 삭제는 전단(front)에서 이루어져야 한다.

약간 더 복잡한 구조를 생각할 수 있다. 다음과 같이 마지막 노드의 링크가 첫 노들르 가리키는 원형연결리스트를 이용하는 것이다.

rear == tail // front == tail.link

이 구조에서는 tail(또는 rear)만을 변수로 저장한다. front는 어떻게 알 수 있을까? tail의 다음 노드, 즉 tail.link 가 front이다.

만약 tail이 아니라 head(또는 front)만을 사용하면 어떻게 될까? 이 경우 front는 바로 접근이 가능하다. 그런데 rear도 바로 찾아갈 수 있을까? 불가능하다. 링크를 따라 후속노드 전체를 끝까지 이동해야 드디어 rear에 도착한다. 따라서 tail을 사용하는 것이 rear과 front에 바로 접근할 수 있다는 점에서 훨씬 효율적이다.

원결된 큐를 원형연결리스트로 구현할 때 필요한 멤버 변수는 tail 뿐이다. 후단은 rear == tail이고. 삭제를 위한 전단은 front == tail.link이므로 모두 O(1)만에 접근할 수 있다. 큐의 동작은 스택보다 약간 더 복잡하다.

---

클래스 정의

노드 클래스는 앞에서 공부한 스택이나 리스트에서와 동일. 원형연결리스트로 구현한 큐 클래스를 CircularLinkedQueue라 하자. 공백검사와 초기화, peek 등의 연산은 다음과 같이 매우 간단하다. peek은 큐가 공백이 아닐 경우 front(tail.link)의 data를 반환하면 된다.

class CircularLinkedQueue:
	def __init__(self):	#생성자 함수 
            self.tail = None	#tail:유일한 데이터 
            
    	def isEmpty(self) : return self.tail == None #공백검사
        def clear(self) : self.tail = None	#큐 초기화 
        def peek(self):
            if not self.isEmpty():
                return self.tail.link.data #front의 data 반환

enqueue(): 삽입 연산

항목의 삽입은 후단을 통해 이루어진다. 삽입은 큐가 공백상태인 경우와 그렇지 않은 경우가 약간 다르다. 공백상태가 더 쉽다. 다음은 공백상태의 큐에 항목을 삽입하는 과정을 보여준다.

(1) 입력 데이터 E를 이용해 새로운 노드 n을 생성함 : n = Node(E,NOne)
(2) n의 링크가 자신을 가리키도록 함 : n.link = n
(3) tail이 n을 가리키도록 함 : tail = n

만약 공백상태가 아니면 다음과 같이 약간 더 복잡해진다.

(1) 입력 데이터 E를 이용해 새로운 노드 n을 생성함 : n = Node(E, None)
(2) n의 링크가 front를 가리키도록 함: n.link = tail.link
(3) tail의 링크가 n을 가리키도록 함 : tail.link = n
(4) tail이 n을 가리키도록 함 : tail = n

def enqueue(self, item):
    node = Node(item,None)
    if self.isEmpty():
       node.link = node 
       self.tail = node 
       
    else: 
        node.link = self.tail.link 
        self.tail.link = node 
        self.tail = node
        

dequeue():삭제연산

삭제연산은 front(또는 tail.link)를 연결구조에서 꺼내고 데이터 필드를 반환하는 것이다. 큐는 반드시 공백이 아니어야 삭제가 가능하다. 큐가 항목을 하나만 가지고 있는 경우는 삭제하고 나면 공백 상태가 되므로 일반적인 경우와 분리해서 처리해야 한다.

(1) n이 전단노드(front)를 가리키도록 함: n = tail.link
(2) tail이 None을 가리키도록 함: tail = None
(3) n이 가리키는 노드의 데이터를 반환함 : return n.data

큐가 두 개 이상의 항목을 갖는 경우의 삭제는 다음과 같다.

(1) n이 전단노드(front)를 가리키도록 함: n = tail.link
(2) tail의 링크가 front의 링크를 가리키도록 함: tail.link = n.link
(3) n이 가리키는 노드의 데이터를 반환함 : return n.data

def dequeue(self): 
    if not self.isEmpty():
        data = self.tail.link.data
        if self.tail.link == self.tail: 	#항목이 하나
           self.tail = None
        else:
            self.tail.link = self.tail.link.link
        return data 

size(), print()

큐의 크기를 구하거나 큐의 내용을 출력하기 위해서 tail부터 노드를 따라가면서 한 바퀴 돌아와야 한다. size 연산을 위한 순회 방법은 그림과 같다.

def size(self):
    if self.isEmpty() : return 0 	#공백 0 반환
    else:
        count = 1
        node = self.tail.link
        while not node == self.tail:
            node = node link 
            count += 1
        return count 	#최종 count 반환 

display()

이러한 방문 방법은 display연산에서도 적용된다. 코드는 다음과 같다. 종료조건에 주의하자!

def display(self, msg = 'CircularLinkedQueue:'):
    print(msg, end='')
    
    if not self.isEmpty():
        node = self.tail.link 
        
        while not node == self.tail :
           print(node.data, end='')
           node = node.link
        print(node.data, end='')
    print()

원형큐에서는 용량이 제한되었는데, 연결된 큐에서는 이런 문제가 전혀 없다. 시간 복잡도는 삽입과 삭제가 모두 O(1)로 원형큐와 차이가 없다.

---

6.5 이중연결리스트의 응용: 연결된 덱

연결된 구조로 덱을 구현해보자. 이러한 덱을 연결된 덱(linked dequeue)라고 하다. 먼저 덱을 단순연결리스트로도 구현할 수 있다. 그림과 같이 전단과 후단을 각각 front와 rear가 가리키고, 양쪽에서 삽입과 삭제가 가능한 구조이다.

이 구조는 deleteRear연산에서 문제가 발생. 다른 연산들은 모두 O(1)에 처리가 가능한데 비해 이 연산은 O(n)이 걸린다. 왜 그럴까? 후단을 삭제하고 나면 rear가 한 칸 앞으로 움직여야 한다. 그런데 단순연결리스트의 노드에는 선행노드의 정보가 없다. 따라서 front부터 시작하여 선행노드를 찾기 위해 전체 노드를 탐색해야 한다. 이 과정은 O(n)이 소요된다.

이 문제를 해결하는 방법은 이중연결리스트를 사용하는 것이다. 다음 그림과 같이 모든 노드가 선행노드와 후속노드를 알고 있다면 deleteRear도 O(1)에 처리가 가능하다. 따라서 연결된 덱은 반드시 이중연결리스트로 구현하는 것이 좋다.

클래스 정의

이중연결리스트를 위한 노드는 두 개의 링크를 갖는다. 이들을 각각 prev, next라 하자. 노드 클래스의 이름은 DNode로 하고, 생성자에 디폴트 인자를 적용한 구현 예는 다음과 같다.

class DNode
   def __init__(self, elem, prev = None, next = None):
       self.data = data
       self.prev = prev
       self.next = netx

연결된 덱 클래스를 DoublyLinkedDeque라 하자. 전단과 후단을 위해 front와 rear를 데이터 갖는다. 공백 상태는 전단이나 후단이 None인 경우. 전단을 기준으로 하자. self.front == None이면 공백상태. 초기화는 양단을 모두 None으로 처리하면 확실

class DoublyLinkedDeque:
    def __init__(self):
       self.front = None
       self.rear = None 
       
    def isEmpty(self): return self.front == None
    def clear(self): self.front = self.front = None

이중 연결리스트를 사용하더라도 size나 display의 연산은 단순연결리스트에서의 동작과 차이가 없다. 연결된 스택의 코드를 대부분 이용. getFront와 getRear연산도 front와 rear가 가리키는 노드의 데이터를 반환하면 된다. 여기서는 삽입과 삭제 연산만!

addFront():전단 삽입

전단을 통한 삽입을 먼저 알아보자. 과정은 다음과 같다.

(1) 노드 생성 및 prev, next초기화: n = DNode(item, None, front)
(2) front가 선행노드로 n을 가리킴: front.prev = n
(3) 이제 front가 n을 가리킴: front = n

첫번째 단계에서 노드의 생성자를 이용해 링크를 초기화한다. 전단에 삽입(addFront)되는 노드의 경우 prev는 None. next는 현재의 전단, 즉 front가 되어야 한다. 만약 공백이라면 front와 rear가 n을 가리키도록.

def addFront(self, item):
    node = DNode(item, None,self.front)
    if(self.isEmpty()):
       self.front = self.rear = node 
    else:
        self.front.prev = node
        self.front = node

addRear():후단산입

후단 산입도 유사. 이제 n의 next가 None. prev의 후단인 rear이 되어야. 다음으로 rear가 새로운 노드를 가리키면 된다. 전후단 삽입의 시간 복잡도는 모두 O(1)

def addRear(self, item):
    node = DNode(item, self.rear, None)
    if(self.isEmpty()):
       self.front = self.rear = node 
       
    else:
        self.rear.prev = node
        self.rear = node

deleteFront(), deleteRear():전후단 삭제

전단 삭제를 알아보자.
(1) 삭제할 노드(front)의 데이터 복사: data = front.data
(2) front를 다음으로 옮김 : front = front.next
(3) front를 이전노드는 None: front.prev = None
(4) 데이터를 반환 : return data

만약 노드가 하나뿐이라면 rear도 None으로 설정해야 함에 유의하라. 후단 삭제 deleteRear도 거의 비슷하게 처리된다. 이들 연산은 다음 코드로 구현된다.

def deleteFront(self):
    if not self.isEmpty(): 
        data = self.front.data 
        self.front = self.front.next 
        if self.front == None:
           self.rear == None
        else:
           self.front.prev = None
        return data
        
def deleteRear(self):
    if not self.isEmpty(): 
        data = self.rear.data 
        self.rear = self.rear.prev 
        if self.rear == None:
           self.front == None
        else:
           self.rear.next = None
        return data        
        

전후단 삭제의 시간복잡도는 모두 O(1)이다 만약 단순연결리스트라면 deleteRear은 O(n).