이중 연결 리스트(doubly linked list)는 각 노드가 이전 노드와 다음 노드를 동시에 가리키는 선형 자료구조입니다. 덕분에 리스트를 앞에서 뒤로, 뒤에서 앞으로 양방향으로 탐색할 수 있다는 큰 장점이 있습니다.
이중 연결 리스트의 요소를 생성하고 화면에 표시하려면 먼저 '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
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()
실행 결과
이중 연결 리스트에 요소를 추가합니다
이중 연결 리스트의 노드들은 다음과 같습니다:
10
24
54
77
92
코드 설명
- 'Node' 클래스를 생성합니다. 각 노드는 데이터(data)와 이전·다음 노드 참조(prev, next)를 가집니다.
- 필요한 속성을 담은 'double_list' 클래스를 추가로 생성합니다.
- 'add_data' 메서드를 정의하여 이중 연결 리스트 끝에 새로운 데이터를 추가합니다. 리스트가 비어 있으면 새 노드가 head이자 tail이 되고, 그렇지 않으면 기존 tail 뒤에 연결된 후 tail이 갱신됩니다.
- 'print_it' 메서드를 정의하여 head부터 시작해 next 참조를 따라가며 모든 노드의 데이터를 순서대로 출력합니다. 리스트가 비어 있는 경우 안내 메시지를 출력합니다.
- '__init__' 메서드에서는 이중 연결 리스트의 head와 tail 노드를 None으로 초기화합니다.
- 'double_list' 클래스의 객체를 생성한 뒤, 메서드를 호출하여 데이터를 추가하고 노드들을 화면에 표시합니다.
마무리
이처럼 이중 연결 리스트는 단일 연결 리스트와 달리 각 노드가 양방향 참조를 가지므로, 특정 노드에서 앞뒤로 자유롭게 이동할 수 있습니다. 삽입과 삭제가 빈번하게 일어나는 상황에서 특히 유용하게 활용할 수 있습니다.