파이썬으로 이중 연결 리스트 끝에서 노드 삭제하기

이중 연결 리스트(doubly linked list)는 각 노드가 데이터와 함께 이전 노드와 다음 노드에 대한 참조를 모두 가지는 자료구조입니다. 이러한 구조 덕분에 양방향 탐색이 가능하며, 특히 tail 포인터를 함께 관리하면 리스트의 맨 끝에서 노드를 삭제하는 작업을 매우 효율적으로 처리할 수 있습니다.

이번 글에서는 파이썬으로 이중 연결 리스트의 끝에서 노드를 삭제하는 방법을 예제 코드와 함께 살펴보겠습니다. 노드를 삭제하려면 먼저 'Node' 클래스를 정의해야 하며, 이 클래스에는 다음과 같은 세 가지 속성이 필요합니다.

data : 노드에 저장된 값
next : 연결 리스트의 다음 노드에 대한 참조
prev : 연결 리스트의 이전 노드에 대한 참조

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

예제 코드

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.prev = None
            self.tail.next = None
        else:
            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("리스트가 비어 있습니다")
            return
        print("이중 연결 리스트의 노드들 :")
        while curr != None:
            print(curr.data)
            curr = curr.next

    def delete_from_end(self):
        if(self.head == None):
            return
        else:
            if(self.head != self.tail):
                self.tail = self.tail.prev
                self.tail.next = None
            else:
                self.head = self.tail = None


my_instance = double_list()
print("이중 연결 리스트에 요소를 추가합니다")
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_end()
    print("끝에서 요소를 삭제한 후의 리스트 : ")
    my_instance.print_it()

실행 결과

이중 연결 리스트에 요소를 추가합니다
이중 연결 리스트의 노드들 :
10
24
54
77
92
끝에서 요소를 삭제한 후의 리스트 : 
이중 연결 리스트의 노드들 :
10
24
54
77
끝에서 요소를 삭제한 후의 리스트 : 
이중 연결 리스트의 노드들 :
10
24
54
끝에서 요소를 삭제한 후의 리스트 : 
이중 연결 리스트의 노드들 :
10
24
끝에서 요소를 삭제한 후의 리스트 : 
이중 연결 리스트의 노드들 :
10
끝에서 요소를 삭제한 후의 리스트 : 
리스트가 비어 있습니다

코드 설명

'Node' 클래스 생성 : 각 노드가 가질 data, prev, next 속성을 정의합니다.
'double_list' 클래스 생성 : 연결 리스트 전체를 관리하는 데 필요한 head와 tail 포인터를 가지는 또 다른 클래스를 정의합니다.
'add_data' 메서드 : 새 노드를 생성하여 이중 연결 리스트의 끝에 데이터를 추가합니다. 리스트가 비어 있으면 새 노드가 head이자 tail이 되고, 그렇지 않으면 기존 tail 뒤에 노드를 연결한 뒤 tail을 갱신합니다.
'print_it' 메서드 : head부터 시작해 각 노드의 데이터를 순서대로 화면에 출력합니다. 리스트가 비어 있으면 안내 문구를 출력합니다.
'delete_from_end' 메서드 : 리스트 끝의 노드, 즉 tail 노드를 삭제합니다. 노드가 두 개 이상이면 tail을 이전 노드로 옮기고 그 next를 None으로 설정하며, 노드가 하나뿐이라면 head와 tail을 모두 None으로 만들어 리스트를 비웁니다.
'__init__' 메서드 : 객체 생성 시 head와 tail 노드를 None으로 초기화합니다.
객체 생성 및 반복 삭제 : 'double_list' 클래스의 객체를 만들고, while 반복문을 통해 리스트가 완전히 빌 때까지 끝에서부터 노드를 하나씩 삭제합니다.
결과 확인 : 매 삭제마다 'print_it' 메서드를 호출하여 남은 노드들을 콘솔에 출력합니다.

마무리

이처럼 tail 포인터를 함께 관리하는 이중 연결 리스트에서는 끝에서 노드를 삭제할 때 리스트를 처음부터 순회할 필요가 없습니다. 따라서 삭제 작업이 O(1)의 시간 복잡도로 수행되며, 이것이 단일 연결 리스트에 비해 이중 연결 리스트가 가지는 대표적인 장점 중 하나입니다.

파이썬으로 이중 연결 리스트 끝에서 노드 삭제하기 – 예제 코드와 상세 설명

예제 코드

실행 결과

코드 설명

마무리