이중 연결 리스트(doubly linked list)에서 중복 요소를 제거해야 하는 경우, 먼저 'Node' 클래스를 정의해야 합니다. 이 클래스에는 세 가지 속성이 포함됩니다. 노드에 저장된 데이터(data), 다음 노드에 대한 참조(next), 그리고 이전 노드에 대한 참조(previous)입니다.
또한 연결 리스트 전체를 관리하기 위한 별도의 클래스가 필요하며, 여기에는 데이터 추가, 출력, 중복 제거 등의 메서드를 정의할 수 있습니다.
아래는 전체 구현 예제입니다.
예제 코드
class Node:
def __init__(self, my_data):
self.previous = 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 remove_duplicates(self):
if(self.head == None):
return
else:
curr = self.head
while(curr != None):
index_val = curr.next
while(index_val != None):
if(curr.data == index_val.data):
temp = index_val
index_val.previous.next = index_val.next
if(index_val.next != None):
index_val.next.previous = index_val.previous
temp = None
index_val = index_val.next
curr = curr.next
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(24)
my_instance.print_it()
print("The elements in the list after removing duplicates are : ")
my_instance.remove_duplicates()
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 24 The elements in the list after removing duplicates are : The nodes in the doubly linked list are : 10 24 54 77
코드 설명
- 'Node' 클래스: 각 노드의 데이터와 이전·다음 노드에 대한 참조를 저장하는 기본 단위입니다.
- 'double_list' 클래스: head와 tail 포인터를 가지며 연결 리스트 전체를 관리합니다.
- '__init__' 메서드: 객체 생성 시 head와 tail을 None으로 초기화하여 빈 리스트 상태로 만듭니다.
- 'add_data' 메서드: 새 노드를 리스트의 끝(tail)에 추가합니다.
- 'remove_duplicates' 메서드: 두 개의 포인터(curr, index_val)를 사용해 모든 노드 쌍을 비교하고, 값이 동일한 노드를 리스트에서 제거합니다.
- 'print_it' 메서드: head부터 시작해 각 노드의 데이터를 순서대로 출력합니다.
실행 흐름을 살펴보면, 먼저 10, 24, 54, 77, 24 다섯 개의 요소가 추가된 후 초기 상태가 출력됩니다. 이후 'remove_duplicates' 메서드가 호출되어 리스트를 순회하며 중복된 값(두 번째 24)을 찾아 삭제하고, 마지막으로 'print_it' 메서드를 통해 중복이 제거된 최종 결과가 콘솔에 표시됩니다.
참고로 이 알고리즘은 두 개의 중첩 반복문을 사용하므로 시간 복잡도가 O(n²)입니다. 따라서 리스트의 크기가 매우 큰 경우에는 해시 집합(set)을 활용해 O(n) 성능으로 개선하는 방법을 고려하는 것이 좋습니다.