이중 연결 리스트(Doubly Linked List)에서 특정 요소를 검색하려면 먼저 'Node' 클래스를 생성해야 합니다. 이 클래스에는 세 가지 속성이 필요합니다. 노드에 저장된 데이터(data), 다음 노드에 대한 참조(next), 그리고 이전 노드에 대한 참조(previous)입니다.
다음으로 초기화 함수를 포함하는 별도의 클래스를 만들어야 하며, 이 클래스 내부에서는 리스트의 시작점인 head가 'None'으로 초기화됩니다.
이후 사용자가 직접 여러 메서드를 정의하여 연결 리스트에 노드를 추가하고, 전체 노드를 화면에 출력하며, 리스트에서 특정 노드를 검색하는 기능을 구현할 수 있습니다.
이중 연결 리스트의 각 노드는 포인터를 가집니다. 현재 노드는 다음 노드와 이전 노드 양쪽을 모두 가리키는 포인터를 가지며, 리스트의 마지막 노드는 next 포인터에 'NULL' 값을 가집니다. 이러한 구조 덕분에 이중 연결 리스트는 양방향으로 자유롭게 순회(traversal)할 수 있다는 큰 장점이 있습니다.
참고로 이 검색 방식은 리스트를 처음부터 끝까지 하나씩 확인하는 선형 탐색(linear search) 방식이므로, 시간 복잡도는 O(n)입니다.
아래는 이를 실제로 구현한 예제입니다.
예제
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("리스트가 비어 있습니다")
return
print("이중 연결 리스트의 노드들은 다음과 같습니다 :")
while curr != None:
print(curr.data)
curr = curr.next
def search_node(self, val_to_search):
i = 1
flag_val = False
curr = self.head
if(self.head == None):
print("리스트가 비어 있습니다")
return
while(curr != None):
if(curr.data == val_to_search):
flag_val = True
break
curr = curr.next
i = i + 1
if(flag_val):
print("해당 노드는 리스트 내 다음 위치에 있습니다 : ")
print(i)
else:
print("해당 노드는 리스트에 존재하지 않습니다")
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(24)
my_instance.add_data(0)
my_instance.print_it()
print("요소 77을 검색하는 중입니다... ")
my_instance.search_node(77)
print("요소 7을 검색하는 중입니다... ")
my_instance.search_node(7)
출력 결과
이중 연결 리스트에 요소를 추가하는 중입니다 이중 연결 리스트의 노드들은 다음과 같습니다 : 10 24 54 77 24 0 요소 77을 검색하는 중입니다... 해당 노드는 리스트 내 다음 위치에 있습니다 : 4 요소 7을 검색하는 중입니다... 해당 노드는 리스트에 존재하지 않습니다
설명
- 'Node' 클래스가 생성됩니다.
- 필요한 속성(head, tail)을 가진 또 다른 클래스가 생성됩니다.
- 'add_data'라는 이름의 메서드가 정의되어, 이중 연결 리스트 끝에 새로운 데이터를 추가하는 데 사용됩니다.
- 'search_node'라는 이름의 메서드가 정의되어, 이중 연결 리스트에서 검색할 값을 매개변수로 받습니다.
- 이 메서드는 요소를 검색한 후, 찾은 경우 해당 위치(인덱스)를 알려줍니다.
- 'print_it'이라는 이름의 메서드가 정의되어, 연결 리스트의 전체 데이터를 콘솔에 출력하는 데 사용됩니다.
- 'double_list' 클래스의 객체가 생성되고, 데이터를 추가하기 위해 관련 메서드들이 호출됩니다.
- 'search_node' 메서드가 호출되어 특정 요소의 존재 여부를 확인합니다.
- 이 메서드는 연결 리스트의 노드들을 처음부터 순차적으로 순회하며, 요소를 찾으면 해당 인덱스를 반환합니다.
- 검색 결과는 콘솔에 출력되어 사용자에게 표시됩니다.