파이썬으로 이중 연결 리스트의 시작 부분에서 노드 삭제하기

이중 연결 리스트(doubly linked list)의 시작 부분에서 노드를 삭제하려면 먼저 'Node' 클래스를 정의해야 합니다. 이 클래스는 세 가지 속성을 가집니다. 노드에 저장된 데이터(data), 다음 노드에 대한 참조(next), 그리고 이전 노드에 대한 참조(prev)입니다.

이어서 리스트 전체를 관리하는 'double_list' 클래스를 만들고, 데이터 추가·출력·삭제 기능을 메서드로 구현합니다. 아래 예제를 통해 시작 노드(head)를 삭제하는 과정을 살펴보겠습니다.

예제 코드

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(self, my_data):
        new_node = Node(my_data)
        if(self.head == None):
            self.head = self.tail = new_node
            self.head.previous = None
            self.tail.next = None
        else:
            self.tail.next = new_node
            new_node.previous = 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

    def delete_from_beginning(self):
        if(self.head == None):
            return
        else:
            if(self.head != self.tail):
                self.head = self.head.next
                self.head.previous = None
            else:
                self.head = self.tail = None

my_instance = double_list()
print("Elements are being added to the doubly linked list")
my_instance.add_data(10)
my_instance.add_data(24)
my_instance.add_data(54)
my_instance.add_data(77)
my_instance.add_data(92)
my_instance.print_it()
while(my_instance.head != None):
    my_instance.delete_from_beginning()
    print("The list after deleting the element from the beginning is : ")
    my_instance.print_it()

실행 결과

Elements are being added to the doubly linked list
The nodes in the doubly linked list are :
10
24
54
77
92
The list after deleting the element from the beginning is :
The nodes in the doubly linked list are :
24
54
77
92
The list after deleting the element from the beginning is :
The nodes in the doubly linked list are :
54
77
92
The list after deleting the element from the beginning is :
The nodes in the doubly linked list are :
77
92
The list after deleting the element from the beginning is :
The nodes in the doubly linked list are :
92
The list after deleting the element from the beginning is :
The list is empty

코드 설명

• 'Node' 클래스 생성: 각 노드는 데이터와 이전 노드 참조(prev), 다음 노드 참조(next)를 가집니다.
• 'double_list' 클래스 생성: 리스트 전체를 관리하기 위한 head(첫 번째 노드)와 tail(마지막 노드) 속성을 가지며, 초기값은 모두 None입니다.
• 'add_data' 메서드: 새 노드를 만들어 이중 연결 리스트의 끝(tail 뒤)에 추가합니다. 리스트가 비어 있다면 새 노드가 head이자 tail이 됩니다.
• 'print_it' 메서드: head부터 시작해 각 노드의 데이터를 순서대로 출력하고, 리스트가 비어 있으면 "The list is empty"라는 메시지를 표시합니다.
• 'delete_from_beginning' 메서드: 리스트의 첫 번째 노드(head)를 삭제하고, 그다음 노드를 새로운 head로 지정합니다. 삭제 후 새 head의 previous를 None으로 설정하여 연결을 정리합니다. 노드가 하나뿐이라면 head와 tail을 모두 None으로 만들어 빈 리스트로 초기화합니다.
• 객체 생성 및 메서드 호출: 'double_list' 클래스의 인스턴스를 만들고, 5개의 데이터(10, 24, 54, 77, 92)를 추가한 뒤 출력합니다.
• 반복 삭제: while 반복문을 사용해 리스트가 완전히 빌 때까지 시작 노드를 계속 삭제하고, 매번 'print_it' 메서드로 현재 상태를 콘솔에 출력합니다.

이처럼 이중 연결 리스트에서 시작 노드를 삭제할 때는 head 포인터만 다음 노드로 옮기고, 새 head의 이전 참조를 None으로 설정하면 됩니다. 시간 복잡도는 O(1)로 매우 효율적입니다.