이중 연결 리스트(doubly linked list)의 중간에 있는 노드를 삭제해야 할 때는 먼저 'Node' 클래스를 정의해야 합니다. 이 클래스에는 세 가지 속성이 담깁니다. 바로 노드에 저장된 데이터(data), 다음 노드를 가리키는 참조(next), 그리고 이전 노드를 가리키는 참조(prev)입니다.
그다음에는 또 다른 클래스를 만들어야 합니다. 이 클래스에는 초기화 함수(__init__)가 정의되며, 그 안에서 리스트의 head가 'None'으로 초기화됩니다.
이어서 노드를 리스트에 추가하는 메서드, 전체 노드를 화면에 출력하는 메서드, 그리고 리스트 중간의 노드를 삭제하는 메서드 등 필요한 기능들을 차례로 정의합니다.
이중 연결 리스트에서 각 노드는 포인터(참조)를 가집니다. 현재 노드는 다음 노드와 이전 노드를 동시에 가리킬 수 있으며, 리스트의 마지막 노드가 가리키는 next 값은 'None'입니다. 덕분에 리스트를 양방향으로 자유롭게 순회할 수 있다는 것이 이중 연결 리스트의 가장 큰 특징입니다.
아래는 이를 구현한 예시입니다.
예제
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
self.size = 0
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("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_middle(self):
if(self.head == None):
return
else:
curr = self.head
mid = (self.size//2) if(self.size % 2 == 0) else((self.size+1)//2)
for i in range(1, mid):
curr = curr.next
if(curr == self.head):
self.head = curr.next
if(self.head != None):
self.head.prev = None
elif(curr == self.tail):
self.tail = self.tail.prev
self.tail.next = None
else:
curr.prev.next = curr.next
curr.next.prev = curr.prev
curr = None
self.size -= 1
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_middle()
print("The list after deleting the element from the middle 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 middle is : The nodes in the doubly linked list are : 10 24 77 92 The list after deleting the element from the middle is : The nodes in the doubly linked list are : 10 77 92 The list after deleting the element from the middle is : The nodes in the doubly linked list are : 10 92 The list after deleting the element from the middle is : The nodes in the doubly linked list are : 92 The list after deleting the element from the middle is : The list is empty
설명
- 'Node' 클래스가 생성됩니다. 각 노드는 데이터와 함께 이전 노드(prev) 및 다음 노드(next)에 대한 참조를 가집니다.
- head, tail, size 속성을 가진 'double_list' 클래스가 생성됩니다.
- '__init__' 메서드는 head와 tail을 'None'으로, size를 0으로 초기화합니다.
- 'add_data' 메서드는 이중 연결 리스트의 끝에 새 데이터를 추가하며, 노드 사이의 prev/next 참조를 알맞게 연결합니다.
- 'print_it' 메서드는 리스트의 모든 노드를 순서대로 출력하고, 리스트가 비어 있으면 그 사실을 알려줍니다.
- 'delete_from_middle' 메서드는 현재 리스트의 크기를 기준으로 중간 위치를 계산한 뒤 해당 노드까지 이동하고, 삭제 대상이 head인지 tail인지 아니면 중간 노드인지에 따라 참조를 적절히 재연결하여 노드를 제거합니다.
- 'double_list' 클래스의 객체를 생성하고 데이터를 추가한 뒤, 리스트가 완전히 빌 때까지 중간 노드를 반복해서 삭제합니다.
- 매번 삭제 작업이 끝날 때마다 'print_it' 메서드를 호출하여 남은 노드들을 콘솔에 출력합니다.
참고로 중간 노드 삭제 연산은 삭제할 위치까지 이동해야 하므로 최악의 경우 O(n)의 시간 복잡도를 가집니다. 다만 삭제 자체는 앞뒤 노드의 참조만 변경하면 되기 때문에 실제 제거 과정은 O(1)로 매우 빠릅니다.