이중 연결 리스트 (Doubly Linked List)

한 방향 연결리스트의 단점(tail node를 찾아가려면 head node부터 링크를 따라 찾아가야 하는 어려움)을 prev node 링크를 통해 보완한 연결리스트

상대적 단점으로는 관리해야 할 링크의 개수가 2배이나, 복잡도 대비 얻는 이익이 크다고 본다.

구조

key와 2개의 link(prev,next)로 구성된 노드의 연결로 이루어져 있다.

None⇆노드⇆ ... ⇆노드⇆None

대체로 이중 연결리스트는 원형 이중 연결리스트를 말한다. 즉,

head.prev = tail
tail.next = head 이며,

원형 이중 연결리스트의 Head 노드는 key=None인 Dummy 노드이다.

class Node: 
    def __init__(self,key=None):
        self.key = key
        self.prev = self
        self.next = self
    
    def __str__(self):
        return str(self.key)

class DoublyLinkedList:
    def __init__(self):
        self.head = Node() # 원형 양방향 연결리스트의 더미 노드
        self.size = 0
    
    def __str__(self):
        s = ""
        v = self.head
        while v.next != self.head:
            s += str(v.key) + "->"
            v = v.next
        s += str(v.key) + "->" + "None" # 위 반복문은 v = 마지막 노드, 즉 head의 전 노드일 때 끝나기 때문에 마지막 노드를 위한 연산이 한번 더 필요하다
        return s

Splice

이중 연결리스트에서 이동/삽입 연산은 splice를 통해 간단하게 나타낼 수 있다.

전제 1) a -> ... -> b 노드에서 a == b 는 가능하지만, b가 a보다 앞 노드여서는 안된다.
전제 2) a 노드와 b 노드 사이에 Head 노드가 없을 것

Splice 과정은 a.prev 와 b.next 노드의 링크를 연결하여 a.prev 노드와 a 노드, b 노드와 b.next 노드의 링크를 끊는 cut, x 노드와 a 노드, b 노드와 x.next 노드의 링크를 연결하는 과정이 있다.

이 과정에서 수정되는 링크는 총 6개

def splice(self,a,b,x): # a 노드부터 b 노드까지를 잘라내어 x 노드 뒤에 붙이는 연산
        if a == None or b == None or x == None:
            return
        ap = a.prev
        bn = b.next
        #cut a to b
        ap.next = bn     # a와 a 전 노드의 연결을 끊고, a 전 노드를 b 다음 노드에 연결 
        bn.prev = ap     # b와 b 다음 노드의 연결을 끊고, b 다음 노드를 a 전 노드에 연결
        #insert a to b after x
        xn = x.next
        x.next = a       # a와 x 양방향 연결
        a.prev = x
        
        xn.prev = b      # b와 x 다음 노드 양방향 연결
        b.next = xn

Splice를 활용한 이동/삽입 연산

    # 이동
    def moveAfter(self,a,x): # 노드 a를 노드 x 다음으로 이동
        DoublyLinkedList.splice(self,a,a,x)
    
    def moveBefore(self,a,x):
        DoublyLinkedList.splice(self,a,a,x.prev)
    
    # 삽입
    def insertAfter(self,x,key): # Node(key) 를 노드 x 다음에 삽입
        DoublyLinkedList.moveAfter(self,Node(key),x) # -> splice(self,Node(key),Node(key),x)

    def insertBefore(self,x,key):
        DoublyLinkedList.moveBefore(self,Node(key),x)
    
    def pushFront(self,key): # Node(key)를 연결리스트 맨 앞에서 push
        DoublyLinkedList.insertAfter(self,self.head,key)

    def pushBack(self,key):
        DoublyLinkedList.insertBefore(self,self.head,key)  

탐색 연산

    # 탐색
    def search(self,key): # 해당 키를 가진 노드를 검색해서 출력(head노드의 다음 노드부터 시작해서 그 다음 노드가 head인 tail이 올 때까지)
        v = self.head
        i = 0
        while v.next != self.head:
            if v.key == key:
                return i
            v = v.next
            i += 1
        if v.key == key: # __str__과 마찬가지로 마지막 노드의 연산이 한번 더 필요하다.
            return i
        return None

삭제 연산

삭제 연산은 삭제할 노드의 prev, next의 링크를 연결시키고, 삭제할 노드의 메모리를 초기화하는 remove를 활용한다.

    # 삭제
    def remove(self,x): # 노드 x를 삭제
        if x == None or x == self.head:
            return
        else:           # x 전 노드와 다음 노드의 링크를 연결 후 x 노드 메모리 초기화
            xp = x.prev
            xn = x.next
            xp.next = xn
            xn.prev = xp
        del x

    def popFront(self): # 맨 앞 노드 삭제
        DoublyLinkedList.remove(self,self.head.next)
    
    def popBack(self): # 맨 뒷 노드 삭제
        DoublyLinkedList.remove(self,self.head.prev)

s = DoublyLinkedList()
s.insertAfter(s.head,3) 		# Head 노드 다음에 3 노드 삽입
s.pushFront(2)				# 맨 앞에 2 노드 삽입
s.pushFront(4)				# 맨 앞에 4 노드 삽입
print(s.head.key) 			# None
print(s.head.next.key)			# 4
print(s.head.next.next.key)		# 2
print(s.head.next.next.next.key) 	# 3
print(s)				# None->4->2->3->None
print(s.search(2))			# 2  2번째 노드
print(s.search(3))			# 3  3번째 노드
s.popFront()				# 4 노드 삭제
s.popBack()				# 3 노드 삭제
print(s)				# None->2->None

수행시간

splice(a,b,x) => O(1) (6개 링크를 수정하는 연산이기 때문에 상수시간)

remove(x) => O(1) (2개 링크를 수정하기 때문에 상수시간)

이동/삽입 연산
moveAfter/Before, insertAfter/Before, pushFront/Before는 모두 splice이므로 O(1)

삭제 연산
remove, popFront/Back은 모두 remove이므로 O(1)

탐색 연산
search(key)는 모든 노드를 한번씩 거쳐가므로 O(N)