이중 연결 리스트(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
self.size = 0
def add_data(self, my_data):
new_node = Node(my_data)
if self.head is 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
self.size += 1
def print_it(self):
curr = self.head
if self.head is None:
print("리스트가 비어 있습니다")
return
print("이중 연결 리스트의 노드들 :")
while curr is not None:
print(curr.data)
curr = curr.next
def add_data_in_middle(self, my_data):
new_node = Node(my_data)
if self.head is None:
self.head = self.tail = new_node
self.head.previous = None
self.tail.next = None
else:
curr = self.head
# 크기가 짝수면 size//2, 홀수면 (size+1)//2를 중간 위치로 사용
mid = (self.size // 2) if (self.size % 2 == 0) else ((self.size + 1) // 2)
for _ in range(1, mid):
curr = curr.next
temp = curr.next
curr.next = new_node
new_node.previous = curr
new_node.next = temp
temp.previous = new_node
self.size += 1
my_instance = double_list()
print("이중 연결 리스트에 요소를 추가합니다")
my_instance.add_data(10)
my_instance.add_data(24)
my_instance.add_data(54)
print("리스트 중간에 요소를 추가합니다")
my_instance.add_data_in_middle(77)
my_instance.print_it()
my_instance.add_data_in_middle(92)
my_instance.print_it()
출력 결과
이중 연결 리스트에 요소를 추가합니다 리스트 중간에 요소를 추가합니다 이중 연결 리스트의 노드들 : 10 24 77 54 이중 연결 리스트의 노드들 : 10 24 92 77 54
코드 설명
- 'Node' 클래스: previous, data, next 세 가지 속성을 가지는 노드의 기본 단위입니다.
- 'double_list' 클래스: head(첫 번째 노드), tail(마지막 노드), size(노드 개수) 속성으로 리스트 전체를 관리합니다.
- '__init__' 메서드: 객체 생성 시 head와 tail을 None으로, size를 0으로 초기화합니다.
- 'add_data' 메서드: 리스트의 맨 뒤에 새 노드를 추가하고 size를 1 증가시킵니다.
- 'add_data_in_middle' 메서드: 리스트 크기가 짝수면 size//2, 홀수면 (size+1)//2로 중간 위치를 계산한 뒤, 해당 위치 바로 뒤에 새 노드를 삽입합니다.
- 'print_it' 메서드: head부터 시작해 각 노드의 데이터를 순서대로 출력하며, 리스트가 비어 있으면 안내 문구를 표시합니다.
- 객체를 생성한 뒤 'add_data'로 10, 24, 54를 차례로 추가하고, 'add_data_in_middle'을 호출해 중간에 77과 92를 삽입한 결과를 'print_it'으로 확인합니다.
삽입 동작 원리
중간 삽입의 핵심은 포인터(참조) 재연결입니다. 새 노드(new_node)를 삽입할 때는 다음 네 가지 연결만 올바르게 수정하면 됩니다.
- 현재 노드(curr)의 next가 새 노드를 가리키도록 변경
- 새 노드의 previous가 현재 노드를 가리키도록 설정
- 새 노드의 next가 기존 다음 노드(temp)를 가리키도록 설정
- 기존 다음 노드(temp)의 previous가 새 노드를 가리키도록 변경
이 방식의 시간 복잡도는 중간 위치를 찾기 위해 리스트를 순회해야 하므로 O(n)입니다. 다만 실제 삽입 작업(포인터 변경) 자체는 O(1)로 처리됩니다.