[Data Structure] Doubly Linked List

do yeon kim·2022년 9월 6일

Doubly Linked List

한방향 연결리스트의 경우 단점은 한쪽으로만 연결되어 있기 때문에 예를 들어 데이터를 찾을 경우 head부터 시작해서 하나하나 확인을 해야 한다는 것이다.

만약 데이터가 마지막에 있다면, 처음부터 끝까지 모든 데이터를 확인 해야 한다. 그렇기때문에 시간복잡도는 O(n)이 된다.

이러한 단점을 보완한 자료구조가 양방향연결리스트이다. 양방향연결리스트는 자신의 뒤에 해당하는 노드의 주소값 뿐만아니라 앞에 해당하는 노드의 주소값 역시 가지고 있기 때문에 만약 맨 마지막 노드의 전 노드에 접근하는 방법은 tail.prev로 접근할 수 있다. 그렇기 때문에 시간복잡도는 상수인 O(1)이 된다.

양방향연결리스트 중에서도 이번에 다룰 것이 원형연결리스트이다.
원형연결리스트는 tail의 next가 None이 아닌 head를 가르키게 하고,
head의 prev가 None이 아닌 tail를 가르키게 한다.

이렇게 되면 어디가 head이고 tail인지 모르기 때문에 dummy node를 하나 만들어서 head로서 기준점이 되게 한다. dummy node의 key값은 None으로 한다.

Node Class

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

원형양방향 연결리스트의 노드는 값에 해당하는 key, 다음링크인 next, 이전링크인 prev를 가진다.
또한 처음 생성하는 노드의 next와 prev는 자기자신을 가르키게 해서 원형을 만든다.

Doubly_Linked_List Class

class Doubly_Linked_List:
    def __init__(self):
        self.head = Node()
        self.size = 0
    
    def __len__(self):
        return self.size

    def __iter__(self):
        node = self.head
        while node.next != self.head:
            yield node.key
            node = node.next
        return StopIteration

처음 생성할 때 생성자로 dummy_node를 하나 생성해준다. dummy_node의 key값은 default값인 None가 된다. 그리고 size는 0이다.

splice 연산

기본 splice메서드의 개념
a노드와 b노드를 포함하여 그 사이에 있는 노드들을 떼어내서 x노들 뒤에 붙여넣는다.

def splice(self, a, b, x): 
        # a, b, x 는 모두 Node이다.
        # 조건1
        # a의 next를 따라가다보면 b가 있다.
        # a,b 가 모두 a,a일 수도 있다.

        # 조건2
        # a와 b사이에 head(dummy node)가 있으면 안된다.
        # 원형으로 연결되어있기 때문에 next를 해서 a-b사이에 dummy가 올수도 있기 때문에 이점을 주의하자
        
        # 조건3
        # a와 b사이에 x가 있으면 안된다.

        # cut하기
        a.prev.next = b.next
        b.next.prev = a.prev
        
        # paste하기
        x.next = a
        a.prev = x
        b.next = x.next
        x.next.prev = b

원형양뱡향 연결리스트에서 리스트내의 메서드를 수행하기 위해서 공통적으로 필요로 하는 splice 메서드를 정의했다.

splice메서드를 이용해서 노드를 잘라내고 붙여넣기 하는 것으로 노드에 대한 추가적인 메서드 구현이 가능하다.

이동연산과 삽입연산

위에서 정의한 splice메서드를 이용해서 간단히 이동연산과 삽입연산의 구현이 가능하다.

이동연산이란 노드를 다른 위치로 이동시키는 것을 의미한다. 다른 위치는
특정노드의 앞 또는 뒤가 될 수 있다.

move_After는 a라는 노드를 x노드 뒤로 이동시키는 것이다.
이때 splice메서드를 이용해서 a-a사이를 잘라낸 다음 x 다음으로 붙여 넣을 수 있다.

move_Before는 a라는 노드를 x노드 앞에 이동시키는 것으로 a-a사이를 잘라낸 다음 x.prev에 붙여 넣는 것이다.

이렇게 spice메서드를 이용해서 이동연산의 구현이 가능하다.

 
 # 이동연산
    # 노드 a를 노드 x 다음으로 이동시킨다.
    def move_After(self, a, x):
        self.splice(a, a, x)

    # 노드 a를 노드 x 앞으로 이동시킨다.
    # x의 앞에 해당하므로 splice에서는 x.prev에 해당한다.
    def move_Before(self, a, x):
        self.splice(a, a, x.prev)

삽입연산에는 4가지가 있다. 특정위치의 앞과 뒤에 넣기, 맨 앞에 넣기, 맨 뒤에 넣기이다.

특정 위치의 앞과 뒤에 넣기는 이동연산을 이용해서 구현할 수 있다.
새롭게 추가되는 노드는 다시 말하면, 특정위치로 이동된다는 것을 말한다. 그러므로 위에서 정의한 이동연산으로 구현할 수 있다.

맨 앞과 맨뒤에 넣는 것은 다시 바로 앞에서 설명한 삽입 연산을 통해서 구현할 수 있다.

# 삽입연산 
    # 이동연산을 다시 불러서 활용한다.
    def insert_After(self, x, key):
        self.move_After(Node(key), x)
        self.size += 1

    def insert_Before(self, x, key):
        self.move_Before(Node(key), x)
        self.size += 1

    def push_Front(self, key):
        self.insert_After(self.head, key)
        self.size += 1

    def push_Back(self, key):
        self.insert_Before(self.head, key) 
        self.size += 1

move_After/move_Before는 splice메서드를 부르고,
insert_After/insert_Before는 move_After/move_Before를 부르며
push_Front/push_Back는 insert_After/insert_Before를 부르는 형식이다.

결국은 모든 메서드가 splice메서드를 이용해서 구현되는 것이다.

탐색연산과 삭제연산


    # 탐색연산
    # 헤드부터 차례대로 비교하면서 링크를 따라간다.
    def search(self, key):
        node = self.head
        while node.next != self.head:
            if node.key == key:
                return node
            node = node.next
        return None

    
    def remove(self, x):
        x = self.search(x)
        if x == None or x == self.head:
            return None
        x.prev.next = x.next
        x.next.prev = x.prev
        self.size -= 1
        del x

    def pop_Front(self):
        if self.size == 0:
            return None
        self.remove(self.head.next)
    
    def pop_Back(self):
        if self.size == 0:
            return None
        self.remove(self.head.prev)