파이썬으로 이중 연결 리스트 끝에 새 노드 삽입하는 방법

이중 연결 리스트(Doubly Linked List)의 끝에 새 노드를 삽입하려면 먼저 'Node' 클래스를 정의해야 합니다. 이 클래스에는 세 가지 핵심 속성이 포함됩니다.

• data: 노드에 실제로 저장되는 값
• next: 연결 리스트상 다음 노드에 대한 참조
• prev: 연결 리스트상 이전 노드에 대한 참조

이어서 head(첫 번째 노드)와 tail(마지막 노드)을 관리하는 별도의 리스트 클래스를 만들고, 끝에 데이터를 추가하는 메서드를 구현합니다. tail 포인터를 유지하므로 리스트 전체를 순회하지 않고도 O(1) 시간 복잡도로 새 노드를 마지막에 추가할 수 있다는 점이 이 방식의 장점입니다.

아래는 전체 구현 예제입니다.

예제 코드

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_end(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:
            # 기존 tail 뒤에 새 노드를 연결
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
            self.tail.next = None

    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 end of doubly linked list")
my_instance.add_data_at_end(10)
my_instance.print_it()
my_instance.add_data_at_end(24)
my_instance.print_it()
my_instance.add_data_at_end(54)
my_instance.print_it()
my_instance.add_data_at_end(77)
my_instance.print_it()
my_instance.add_data_at_end(92)
my_instance.print_it()

실행 결과

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

코드 설명

• 'Node' 클래스 생성: 각 노드가 data, prev, next 세 가지 속성을 가지도록 정의합니다.
• 'double_list' 클래스 생성: head와 tail 두 개의 포인터를 관리하며, 초기 상태에서는 모두 None입니다.
• 'add_data_at_end' 메서드: 리스트가 비어 있으면(head가 None) 새 노드가 곧 head이자 tail이 됩니다. 비어 있지 않다면 기존 tail의 next를 새 노드로 연결하고, 새 노드의 prev를 기존 tail로 지정한 뒤 tail을 새 노드로 갱신합니다.
• 'print_it' 메서드: head부터 시작해 next 참조를 따라가며 리스트의 모든 노드 값을 순서대로 출력합니다.
• 객체 생성 및 호출: 'double_list' 클래스의 인스턴스를 만들고, 여러 값을 차례로 추가할 때마다 현재 리스트의 상태를 콘솔에 출력해 변화를 확인합니다.

실행 결과에서 알 수 있듯이, 요소가 추가될 때마다 리스트의 길이가 하나씩 늘어나며 항상 맨 끝에 새 값이 붙는 것을 확인할 수 있습니다.