이중연결리스트(Doubly Linked List) 이론과 파이썬 구현

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

이중연결리스트(Doubly Linked List)는 각 노드가 두 개의 레퍼런스를 가지고 각각 이전 노드와 다음 노드를 가리키는 연결리스트를 구현한 자료구조입니다.

 

이중연결리스트는 단순연결리스트의 단점(역방향으로 노드 탐색 불가능, 삽입이나 삭제시 반드시 이전 노드를 가리키는 레퍼런스를 추가로 알아야 함)을 보완하기 위해 나왔습니다.

하지만 노드마다 2개의 레퍼런스를 저장해야 한다는 단점이 있습니다.

 

이중연결리스트의 기본 구조

 

이중연결리스트의 기본 구조입니다.

head는 이중연결리스트의 첫 번째 노드가 무엇인가 의미하는 정보입니다.

tail은 이중연결리스트의 마지막 노드가 무엇인가 의미하는 정보입니다.

node는 아이템과 레퍼런스 2개를 가집니다.

item은 항목으로 node값이 저장됩니다.

reference1는 메모리 주소를 의미하며 이전 노드의 위치를 알려줍니다.

reference2는 메모리 주소를 의미하며 다음 노드의 위치를 알려줍니다.

 

__init__(self) : DList 객체 생성

 

insert_before() : p가 가리키는 노드 앞에 새 노드를 삽입

insert_after() : p가 가리키는 노드 뒤에 새 노드를 삽입

 

delete() : 노드 x 삭제

 

 

이중연결리스트의 파이썬 코드입니다.

class DList:
    
    class Node:
        def __init__(self, item, prev, link):  # 노드 생성자
            self.item = item  # 항목
            self.prev = prev  # 앞노드 레퍼런스
            self.next = link  # 뒤노드 레퍼런스

    def __init__(self):  # 이중 연결 리스트 생성자
        # head, tail, 항목수로 구성
        # 두 더미노드(head, tail)에는 실제 항목 저장하지 않음
        self.head = self.Node(None, None, None)
        self.tail = self.Node(None, self.head, None)
        self.head.next = self.tail
        self.size = 0

    def size(self):
        return self.size

    def isempty(self):
        return self.size == 0

    def insert_before(self, p, item):  # p가 가리키는 노드 앞에 새 노드를 삽입
        t = p.prev # p 앞의 기존 노드
        n = self.Node(item, t, p)  # 삽입할 노드
        p.prev = n  # 새 노드와 뒤 노드 연결
        t.next = n  # 새 노드와 앞 노드 연결
        self.size += 1 

    def insert_after(self, p, item):  # p가 가리키는 노드 뒤에 새 노드를 삽입
        t = p.next # p 뒤의 기존 노드
        n = self.Node(item, p, t)  # 삽입할 노드
        t.prev = n  # 새 노드와 뒤 노드 연결
        p.next = n  # 새 노드와 앞 노드 연결
        self.size += 1

    def delete(self, x):  # 노드 x 삭제
        f = x.prev # x 앞의 기존 노드
        r = x.next # x 뒤의 기존 노드
        f.next = r  # x를 건너뛰고 x의 앞뒤 노드를 연결
        r.prev = f  # x를 건너뛰고 x의 앞뒤 노드를 연결
        self.size -= 1
        return x.item

    def print_list(self):
        if self.isempty():
            print('List is empty.')
        else:
            p = self.head.next
            while p != self.tail:
                if p.next != self.tail:
                    print(p.item, ' <=> ', end='')
                else:
                    print(p.item)
                p = p.next  # 노드를 차례로 방문

class EmptyError(Exception):  # Underflow시 에러 처리
    pass


s = DList() # 이중 연결 리스트 생성
s.insert_after(s.head, 'apple') 
s.insert_before(s.tail, 'orange')
s.insert_before(s.tail, 'cherry')
s.insert_after(s.head.next, 'pear')
s.print_list()

print('마지막 노드 삭제 후:\t', end='')
s.delete(s.tail.prev)
s.print_list()

print('맨 끝에 포도 삽입 후:\t', end='')
s.insert_before(s.tail, 'grape')
s.print_list()

print('첫 노드 삭제 후:\t', end='')
s.delete(s.head.next)
s.print_list()

print('두 번째 노드 삭제 후:\t', end='')
s.delete(s.head.next.next)
s.print_list()

print('첫 노드 삭제 후:\t', end='')
s.delete(s.head.next)
s.print_list()

print('첫 노드 삭제 후:\t', end='')
s.delete(s.head.next)
s.print_list()

위의 개념과 소스코드는 생능출판의 '파이썬과 함께하는 자료구조의 이해'를 보고 이해하여 정리한 것입니다.