[자료구조] Doubly LinkedList(이중 연결리스트)(Python)

* 개요

이번 포스트에 다룰 내용은 Doubly LinkedList(이중 연결리스트)이다. 이전 노드를 참조할 수 없어 단방향으로만 노드에 접근이 가능했던 SIngly LinkedList(단순 연결리스트)와 달리 Doubly LinkedList(이중 연결리스트)는 이전 노드 참조가 가능하다. 또한 양방향으로 노드에 접근할 수 있어 삽입/삭제/탐색이 단순 연결리스트에 비해 속도가 더 빠르다는 특징이 있다.

 

* Doubly LinkedList(이중 연결리스트)

Doubly LinkedList(이중 연결리스트)는 다음 노드의 참조 뿐만이 아니라 이전 노드의 참조도 같이 가리킬 수 있다. 뒤로 탐색하는게 빠르다는 단순한 장점 외에도 한 가지 장점이 더 있는데, 단순 연결리스트는 현재 가리키고 있는 노드를 삭제하는 것이 한 번에 안되고 시간복잡도가 O(N)이 될 수밖에 없는 데에 비해, 이중 연결리스트에서 현재 노드를 삭제하는 것은 훨씬 간단하다. 대신 관리해야 할 참조가 2개나 있기 때문에 삽입이나 정렬의 경우 작업량이 더 많고, 자료구조의 크기가 약간 더 커진다. 이중 연결리스트는 단순 연결리스트보다는 손상에 강한 편이다. Head나 Tail 노드를 갖고 있다면, 둘 중 하나를 가지고 전체 리스트를 순회할 수 있기 때문에 끊어진 체인을 복구하는 것이 가능하다. 단일 연결리스트는 Tail 노드로는 리스트 순회가 불가능하고 Head 노드 유실 시, 전체 자료를 다 잃어버리게 된다. 하지만 이중 연결리스트의 단점은 보정 알고리즘을 구현하지 않았을 경우, 오히려 손상에 더 취약해진다는 점이다. 예를 들어, next 포인터는 갱신을 했는데 prev 포인터는 갱신하지 않았을 경우 prev 포인터를 따라가는 순회에서 도달 불가능한 '잃어버린' 노드가 발생한다.

 

* 파이썬으로 구현한 Doubly LinkedList(이중 연결리스트)

이중 연결리스트를 객체지향적으로 구현해보았다. 먼저 단순 연결리스트처럼 노드 부분부터 구현한다. 단순 연결리스트와 다른 점은, 다음 노드만 참조하는 단순 연결리스트(next 포인터만 존재)와는 달리 prev와 next 포인터가 존재한다는 것이다.

# 노드 구현
class Node :
    def __init__(self, data) :
        self.data = data
        self.prev = None
        self.next = None

다음은 이중 연결리스트의 초기화 상태를 구현한다.

 

class Doubly_LinkedList :
    def __init__(self) :
        self.head = None
        self.tail = self.head

이중 연결 리스트는 시작을 나타내는 head와 끝을 나타내는 tail을 가진다.  head는 리스트의 첫번째 원소, tail은 리스트의 마지막 원소를 나타낸다. 다음은 tail 노드의 오른쪽 부분에 노드를 추가하는 코드이다.

# 노드 추가(tail 노드의 오른쪽)
    def append(self, data) :
        # head에 노드가 존재하지 않는 경우
        if self.head is None :
            self.head = Node(data)
            self.tail = self.head

        # head에 노드가 존재하는 경우
        else :
            node = self.tail
            new_node = Node(data)
            new_node.prev = node
            node.next = new_node
            self.tail = new_node

head에 노드가 존재하지 않는 경우 새로운 노드를 만들고, head에 노드가 존재하는 경우, 기존의 리스트의 마지막 값(tail)의 next가 new_node를 가리키고(오른쪽에 추가할 것이기 때문에), 리스트의 마지막 값(tail)은 new_node가 된다. 다음은 head 노드의 왼쪽 부분에 노드를 추가하는 코드이다. 

# 노드 추가(head 노드의 왼쪽)
    def append_left(self, data) :
        if self.head is None :
            self.head = Node(data)
            self.tail = self.head

        else :
            node = self.head
            new_node = Node(data)
            new_node.next = node
            node.prev = new_node
            self.head = new_node

기존 head의 prev가 new_node를 가리키고(왼쪽에 추가할 것이기 때문에),  리스트의 첫번째 값(head)은 new_node가 된다. 다음은 기존 노드의 왼쪽에 새로운 노드를 삽입하는 코드이다. 이중 연결리스트는 이전 노드를 참조할 수 있기 때문에 기존 노드의 왼쪽에 삽입하는 것이 더 수월하다고 할 수 있겠다.

def insert_before(self, data, new_data) :
        if self.head is None :
            self.head = Node(new_data)
            self.tail = self.head

        else :
            node = self.tail
            while node.data != data :
                node = node.prev
                if node is None :
                    return False

            prev_node = node.prev
            new_node = Node(new_data)
            new_node.prev = prev_node
            new_node.next = node
 
            # prev_node가 None이 아니라면
            if prev_node :
                prev_node.next = new_node

            # prev_node가 None이라면
            else :
                self.head = new_node

            node.prev = new_node

head가 존재하지 않는다면, 새로운 노드를 생성한다.  head가 존재한다면 기존 노드의 왼쪽에 삽입을 하는 것이기 때문에 뒷쪽(tail) 노드부터 탐색을 진행한다. 기존 노드가 None이라면 False를 반환한다. new_node의 prev는 기존 노드의 prev포인터가 가리키는 노드를 가리키게 된다. prev_node가 None이 아니라면(값이 존재한다면) prev_node의 다음 노드는 new_node가 된다. 그러나 prev_node가 None이라면, head 노드는 new_node가 된다. 다음은 기존 노드의 오른쪽에 새로운 노드를 삽입하는 코드이다.

def insert_after(self, data, new_data) :
        if self.head is None :
            self.head = Node(new_data)
            self.tail = self.head

        else :
            node = self.head
            while node.data != data :
                node = node.next
                if node is None :
                    return False

            next_node = node.next
            new_node = Node(new_data)
            new_node.prev = node
            new_node.next = next_node

            # next_node가 None이 아니라면
            if next_node :
                next_node.prev = new_node

            # next_node가 None이라면
            else :
                self.tail = new_node

            node.next = new_node

head가 존재하지 않는다면, 새로운 노드를 생성한다.  head가 존재한다면 기존 노드의 오른쪽에 삽입을 하는 것이기 때문에 앞쪽(head) 노드부터 탐색을 진행한다. 기존 노드가 None이라면 False를 반환한다. new_node의 next는 기존 노드의 next포인터가 가리키는 노드를 가리키게 된다. next_node가 None이 아니라면(값이 존재한다면) next_node의 이전 노드는 new_node가 된다. 그러나 next_node가 None이라면, tail 노드는 new_node가 된다. 다음은 전체 리스트를 출력하는 코드이다.

def print_all(self) :
        node = self.head
        while node is not None :
            print(node.data, end = ' ')
            node = node.next

앞쪽(head) 노드부터 리스트 순회하여 node의 data를 출력한다. 만약 역순으로 출력하고 싶다면, 뒷쪽(tail) 노드부터 리스트 순회하면 된다. 역순 출력이 쉬운 것도 이중 연결 리스트의 장점이다. 다음은 실행 예제 코드이다.

DL = Doubly_LinkedList() # 이중 연결리스트 생성
DL.append(1) # 1
DL.append(3) # 1 3
DL.append(5) # 1 3 5
DL.append_left(100) # 100 1 3 5
DL.insert_before(5, 4) # 100 1 3 4 5
DL.insert_after(1, 2) # 100 1 2 3 4 5
DL.print_all() # 이중 연결리스트 출력