Doubly Liked List : 양 방향 연결 리스트

기존의 한 방향 리스트의 단점은 tail node까지 가기 위해서는 한 번에 찾을 수는 없고, head node부터 차례로 링크를 따라가며 찾아야 했다.

이렇게 되면 만약 연결 리스트의 길이가 너무나 길 때, prev node를 계속 따라가며 오랜 시간이 걸리게 되고 비효율적일 것이다. O(n)

이럴 때 오른쪽 방향으로만 가는 것이 아니라, 왼쪽 방향으로도 갈 수 있다면 좋겠는데 이렇게 양 방향으로 갈 수 있게 한 것이 양 방향 연결 리스트이다.

이렇게 구성하기 위해서는 우선 Node를 key, link가 아닌, key와 next, prev 로 구성되어 있어야 한다.

이제는 뒤에 있는 노드라도 tail부터 가면 되기에 효과적이다. 물론 더 복잡해지긴 하겠지만 얻는 것이 더 크다고 생각된다.

• 원형 양 방향 연결 리스트
  왠만하면 이 Circularly Doubly Linked List를 사용한다. 이유로는 이렇게 함으로 삽입 삭제 연산들이 simple해지고 조금 더 유연해진다. 여기에서 볼 점은 tail이 가리키는 것은 None이 아니라, head node를 가리키는 것이고 반대 방향을 고려할 때는 head node는 tail node를 가리키게 된다.

중요한 점이 하나 있는데, 여기서 dummy node를 사용한다. 이것만 있으면 빈 리스트로 사실상 head node라고 할 수 있다. 하지만 실질적으로 구성하기 보다는 연결해주기 위한 노드라고 생각하면 된다.

class Node(self):
	def __init__(self, key=None):
    	self.key = key
        self.next = self
        self.prev = self
        
class DoublyLinkedList:
	def __init__(self):
    	self.head = Node() # dummy node
        self.size = 0
    def __iterator__(): # generator
    def __str__(): # print
    def __len__(): # 노드 개수
    

이제 삽입 삭제 연산을 만들텐데, 여기서 계속해서 사용되는 중요한 연산을 알아보자.

• Splice 연산

def splice(self, a, b, x): # 세 개 노드 a,b,x
	# 조건 1: a를 따라가다 보면 b가 있다
    # 조건 2: a와 b 사이에 head node와 x node가 없어야 한다.
    # 목적 : a와 b를 cut해서 어딘가에 있는 x node 다음에 넣는 것이다.
    # 이렇게 6개의 링크만 바꾸면 cut paste를 진행할 수 있다.

def splice(self, a, b, x):
	ap = a.prev
    bn = b.next
    xn = x.next
    
    # cut
    ap.next = bn
    bn.prev = ap
    
    # paste
    x.next = a
    a.prev = x
    b.next = xn
    xn.prev = b
    
    # 이렇게 6개만 바꿔주면 cut paste작업을 진행할 수 있다.

삽입, 삭제 연산

우선 이동연산부터 살펴보자면, 위에서 언급한 splice를 활용한다.

• moveAfter(self, a, x)
  노드 a를 x 다음으로 이동
  => splice(a,a,x)

• moveBefore(self, a, x)
  노드 a를 x 전으로 이동
  => splice(a,a,x.prev)

이제 삽입 연산을 살펴보자

• insertAfter(x.key)
  moveAfter(Node(key), x)

• insertBefore(x.key)
  moveBefore(Node(key), x)

• pushFront(key)
  insertAfter(self.head, key)

• pushBack(key)
  insertBefore(self.head, key)

이제는 삭제 연산을 살펴보기 전 탐색 연산을 살펴보자.

def search(self, key):
	v = self.head # dummy node
    while v.next != self.head: # 아직 한 바퀴를 돌지 않았다면
    	if v.key == key:
        	return v
        v = v.next
    return None

다음은 삭제 연산을 살펴보자.

remove(x)로 노드 x를 삭제하는 것이다.

remove(x):
	if x == None or x == self.head:
		return
	x.prev.next = x.next
    xn.prev = x.prev
    
    del x

++
popFront - head node뒤에 있는 값이 있는 실질적 head node를 remove를 통해 없앤다.
popBack - head에서 tail로 가서 맨 뒤의 값을 없앤다.

이와 같이 임의의 값을 search 로 찾고, 이를 remove를 통해 제거하면 되는 것이다!

join : 두 리스트를 하나의 리스트로 합치는 것
split : 한 리스트를 쪼개는 것

지금까지 여러 연산들을 알아봤는데, 각각의 연산 시간 복잡도를 알아보자!

moveAfter/Before(a,x)
insertAfter/Before(x.key)
pushFront/Back(key) - 이 세 가지는 splice 사용

remove(x)
popFront/Back()

n개 노드를 갖는 이중연결리스트
search(key): # O(n)
splice(a,b,x) : 6개 링크 수정 # O(1)
remove(x)도 지울 노드를 지정하는 것 이기에 앞 뒤 링크만 수정
O(1) O(1)인데 우선 search를 해야 하기에 여기서 시간이 좀 걸릴 수 있다.