Python으로 이중 연결 리스트 맨 앞에 새 노드 삽입하기

이중 연결 리스트의 시작 부분에 노드 추가하기

이중 연결 리스트(Doubly Linked List)의 시작 부분에 새로운 노드를 삽입하려면 먼저 Node 클래스를 정의해야 합니다. 이 클래스는 세 가지 속성을 가집니다. 노드에 저장될 데이터, 다음 노드를 가리키는 참조, 그리고 이전 노드를 가리키는 참조입니다.

이중 연결 리스트는 각 노드가 양방향(이전/다음)을 모두 참조할 수 있어, 단일 연결 리스트보다 유연한 탐색이 가능하다는 장점이 있습니다. 아래 예제를 통해 실제 구현 방법을 살펴보겠습니다.

예제 코드

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

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

    def add_data_at_start(self, my_data):
        new_node = Node(my_data)
        if(self.head == None):
            # 리스트가 비어 있는 경우
            self.head = self.tail = new_node
            self.head.prev = None
            self.tail.next = None
        else:
            # 기존 노드가 있는 경우
            self.tail.prev = new_node
            new_node.next = self.head
            new_node.prev = None
            self.head = new_node

    def print_it(self):
        curr = self.head
        if (self.head == None):
            print("The list is empty")
            return
        print("The nodes in the doubly linked list are :")
        while curr != None:
            print(curr.data)
            curr = curr.next

my_instance = double_list()
print("Elements are being added to the beginning of doubly linked list")
my_instance.add_data_at_start(10)
my_instance.print_it()
my_instance.add_data_at_start(24)
my_instance.print_it()
my_instance.add_data_at_start(54)
my_instance.print_it()
my_instance.add_data_at_start(77)
my_instance.print_it()
my_instance.add_data_at_start(92)
my_instance.print_it()

실행 결과

Elements are being added to the beginning of doubly linked list
The nodes in the doubly linked list are :
10
The nodes in the doubly linked list are :
24
10
The nodes in the doubly linked list are :
54
24
10
The nodes in the doubly linked list are :
77
54
24
10
The nodes in the doubly linked list are :
92
77
54
24
10

코드 설명

• 먼저 데이터와 prev, next 참조를 저장하는 Node 클래스를 생성합니다.
• 연결 리스트 전체를 관리하는 double_list 클래스를 별도로 정의합니다.
• add_data_at_start 메서드는 새 노드를 생성하여 리스트의 시작 부분에 삽입하는 역할을 합니다.
• 리스트가 비어 있으면(head가 None이면) 새 노드가 head와 tail이 됩니다.
• 기존 노드가 있으면 새 노드의 next를 현재 head로 연결하고, 기존 head의 prev를 새 노드로 설정한 뒤 head를 새 노드로 갱신합니다.
• print_it 메서드는 head부터 순차적으로 탐색하며 모든 노드의 데이터를 출력합니다.
• 객체를 생성하고 각 값(10, 24, 54, 77, 92)을 순서대로 삽입할 때마다 리스트 상태를 콘솔에 출력합니다.

실행 결과에서 확인할 수 있듯이, 매번 리스트의 맨 앞에 요소가 추가되므로 마지막에 삽입된 92가 출력 결과의 첫 번째로 나타납니다. 이처럼 시작 위치에 노드를 삽입하는 작업은 포인터 재배치만으로 처리되므로 시간 복잡도는 O(1)입니다.