[실용적인 자료구조] 이중 연결 리스트(Doubly Linked List)

이중 연결 리스트(Doubly Linked List)는 각 노드가 이전 노드와 다음 노드를 참조하는 구조입니다. 이중 연결 리스트를 구현하기 위해서는 노드 클래스(Node)를 정의하고, 이 노드들을 관리하는 리스트 클래스(DoublyLinkedList)를 정의해야 합니다.

파이썬의 list는 배열 기반 자료구조이므로, 직접적으로 상속해서 이중 연결 리스트를 구현하는 것은 권장되지 않습니다. 대신 이중 연결 리스트를 클래스로 직접 구현할 수 있습니다. 여기에서는 list를 상속하지 않고, 이중 연결 리스트의 구조를 더 자연스럽게 구현하는 방식을 제안합니다.

1. Node 클래스 정의

각 노드는 세 가지 속성을 가집니다:

• data: 저장되는 값
• prev: 이전 노드를 가리키는 참조
• next: 다음 노드를 가리키는 참조

2. DoublyLinkedList 클래스 정의

이중 연결 리스트는 여러 노드를 관리하며, 주로 다음과 같은 작업을 지원합니다:

• 앞이나 뒤에 노드 삽입
• 앞이나 뒤에서 노드 삭제
• 리스트 순회

코드 구현

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

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

    def append(self, data):
        """리스트의 끝에 데이터를 추가"""
        new_node = Node(data)
        if self.head is None:  # 리스트가 비어 있는 경우
            self.head = new_node
            self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node

    def prepend(self, data):
        """리스트의 앞에 데이터를 추가"""
        new_node = Node(data)
        if self.head is None:  # 리스트가 비어 있는 경우
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node

    def delete_from_front(self):
        """앞에서 노드 삭제"""
        if self.head is None:  # 빈 리스트
            return None
        removed_node = self.head
        if self.head == self.tail:  # 노드가 하나만 있는 경우
            self.head = None
            self.tail = None
        else:
            self.head = self.head.next
            self.head.prev = None
        return removed_node.data

    def delete_from_back(self):
        """뒤에서 노드 삭제"""
        if self.tail is None:  # 빈 리스트
            return None
        removed_node = self.tail
        if self.head == self.tail:  # 노드가 하나만 있는 경우
            self.head = None
            self.tail = None
        else:
            self.tail = self.tail.prev
            self.tail.next = None
        return removed_node.data

    def display(self):
        """리스트의 모든 요소를 출력"""
        current = self.head
        while current:
            print(current.data, end=" <-> " if current.next else "\n")
            current = current.next

    def display_reverse(self):
        """리스트를 역순으로 출력"""
        current = self.tail
        while current:
            print(current.data, end=" <-> " if current.prev else "\n")
            current = current.prev

# 테스트 코드
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.prepend(0)

print("리스트 출력:")
dll.display()

print("역순 리스트 출력:")
dll.display_reverse()

print("앞에서 삭제:", dll.delete_from_front())
dll.display()

print("뒤에서 삭제:", dll.delete_from_back())
dll.display()

코드 설명

• Node 클래스: 각 노드가 데이터(data), 이전 노드(prev), 다음 노드(next)를 갖습니다.
• DoublyLinkedList 클래스: 이 클래스는 이중 연결 리스트를 관리합니다. 이 클래스의 head는 첫 번째 노드를, tail은 마지막 노드를 가리킵니다.
  • append: 리스트 끝에 노드를 추가합니다.
  • prepend: 리스트 앞에 노드를 추가합니다.
  • delete_from_front: 리스트의 앞에서 노드를 삭제합니다.
  • delete_from_back: 리스트의 뒤에서 노드를 삭제합니다.
  • display: 리스트의 모든 요소를 출력합니다.
  • display_reverse: 리스트를 역순으로 출력합니다.

실행 결과 예시

리스트 출력:
0 <-> 1 <-> 2 <-> 3
역순 리스트 출력:
3 <-> 2 <-> 1 <-> 0
앞에서 삭제: 0
1 <-> 2 <-> 3
뒤에서 삭제: 3
1 <-> 2

이 코드로 이중 연결 리스트를 생성하고, 삽입 및 삭제 작업을 수행할 수 있습니다.