Python에서 연결된 목록 구현 이해
자료 구조는 프로그래밍 세계에서 빼놓을 수 없는 중요한 요소입니다. 데이터를 효율적으로 활용할 수 있도록 구성하는 데 핵심적인 역할을 합니다.
이번 글에서는 단일 연결 리스트와 이중 연결 리스트를 자세히 살펴보겠습니다.
연결 리스트는 선형적인 자료 구조의 한 형태입니다. 배열처럼 연속된 메모리 공간에 데이터를 저장하지 않고, 각 데이터 요소를 '노드'라는 단위로 관리하며, 포인터를 사용하여 노드들을 연결합니다. 연결 리스트의 시작 노드를 '헤드'라고 부릅니다.
연결 리스트의 가장 큰 특징 중 하나는 크기가 동적이라는 것입니다. 메모리 공간이 허용하는 한, 원하는 만큼 노드를 추가하거나 제거할 수 있습니다.
연결 리스트에는 크게 두 가지 유형이 있습니다. 이제부터 각각에 대해 자세히 알아보도록 하겠습니다.
#1. 단일 연결 리스트
단일 연결 리스트는 각 노드가 다음 노드만을 가리키는 포인터를 하나 가지고 있습니다. 즉, 각 노드는 데이터와 다음 노드의 주소를 저장하는 포인터로 구성됩니다.
리스트의 마지막 노드는 다음 노드를 가리키는 포인터에 null 값을 저장하여 연결 리스트의 끝을 표시합니다.
아래 그림을 통해 단일 연결 리스트의 구조를 확인해 볼 수 있습니다.
이제 단일 연결 리스트에 대한 기본적인 이해가 생겼을 것입니다. 다음으로 Python에서 단일 연결 리스트를 구현하는 과정을 단계별로 알아보겠습니다.
단일 연결 리스트 구현
1. 가장 먼저 해야 할 일은 연결 리스트를 구성하는 기본 단위인 노드를 만드는 것입니다.
어떻게 만들 수 있을까요?
Python에서는 클래스를 활용하여 노드를 간단하게 구현할 수 있습니다. 노드 클래스는 데이터와 다음 노드를 가리키는 포인터로 구성됩니다.
노드 클래스의 코드를 살펴보겠습니다.
class Node: def __init__(self, data): # 노드의 데이터 self.data = data # 다음 노드를 가리키는 포인터 self.next = None
위의 코드를 사용하면 다양한 형태의 데이터를 가진 노드를 생성할 수 있습니다. 간단한 예시를 통해 확인해 볼 수 있습니다.
노드를 만들었으니 이제 여러 노드를 연결하여 연결 리스트를 구성해야 합니다. 이를 위해 연결 리스트를 위한 별도의 클래스를 만들어 보겠습니다.
2. 헤드를 None으로 초기화한 LinkedList 클래스를 생성합니다. 아래 코드를 참고하세요.
class LinkedList: def __init__(self): # 헤드를 None으로 초기화 self.head = None
3. Node 클래스와 LinkedList 클래스가 준비되었습니다. 이제 연결 리스트에 새로운 노드를 추가하는 방법을 알아볼 차례입니다. LinkedList 클래스에 삽입 메서드를 추가하면 됩니다. 연결 리스트에 노드를 삽입하는 메서드를 만들어 봅시다.
새로운 노드를 연결 리스트에 삽입하려면 다음과 같은 단계를 따라야 합니다.
- 헤드가 비어 있는지 확인합니다.
- 헤드가 비어 있다면 새 노드를 헤드로 설정합니다.
- 헤드가 비어 있지 않다면 연결 리스트의 마지막 노드를 찾습니다.
- 새 노드를 마지막 노드의 다음 포인터에 할당합니다.
연결 리스트에 새 노드를 삽입하는 코드를 살펴봅시다.
class LinkedList: # ... def insert(self, new_node): # 헤드가 비어있는지 확인 if self.head: # 마지막 노드 찾기 last_node = self.head while last_node.next != None: last_node = last_node.next # 마지막 노드의 다음 포인터에 새 노드 할당 last_node.next = new_node else: # 헤드가 비어 있는 경우 # 새 노드를 헤드로 할당 self.head = new_node
축하합니다! 연결 리스트에 새로운 노드를 삽입하는 방법을 완성했습니다. 이제 연결 리스트에 저장된 데이터에 어떻게 접근할 수 있을까요?
연결 리스트의 데이터에 접근하려면 삽입 메서드에서 마지막 노드를 찾을 때와 마찬가지로 다음 포인터를 따라 연결된 노드를 순회해야 합니다. LinkedList 클래스 안에 연결 리스트의 모든 노드 데이터를 출력하는 메서드를 만들어 보겠습니다.
4. 아래 단계를 따라서 연결 리스트의 모든 노드 데이터를 출력합니다.
- 헤드로 변수를 초기화합니다.
- 연결 리스트의 끝에 도달할 때까지 반복하는 루프를 작성합니다.
- 노드 데이터를 출력합니다.
- 다음 노드로 이동합니다.
코드를 살펴봅시다.
class LinkedList:
# ...
def display(self):
# 순회를 위한 변수
temp_node = self.head
# 연결 리스트 끝까지 반복
while temp_node != None:
# 노드 데이터 출력
print(temp_node.data, end='->')
# 다음 노드로 이동
temp_node = temp_node.next
print('Null')
휴! 필요한 메서드들을 모두 추가하여 연결 리스트 구현을 완료했습니다. 이제 몇 가지 데이터를 넣어 연결 리스트를 테스트해 보겠습니다.
Node(1) 코드로 노드를 생성할 수 있습니다. 예제 사용법과 함께 연결 리스트 구현의 전체 코드를 살펴보겠습니다.
class Node:
def __init__(self, data):
# 노드의 데이터
self.data = data
# 다음 노드를 가리키는 포인터
self.next = None
class LinkedList:
def __init__(self):
# 헤드를 None으로 초기화
self.head = None
def insert(self, new_node):
# 헤드가 비어있는지 확인
if self.head:
# 마지막 노드 찾기
last_node = self.head
while last_node.next != None:
last_node = last_node.next
# 마지막 노드의 다음 포인터에 새 노드 할당
last_node.next = new_node
else:
# 헤드가 비어 있는 경우
# 새 노드를 헤드로 할당
self.head = new_node
def display(self):
# 순회를 위한 변수
temp_node = self.head
# 연결 리스트 끝까지 반복
while temp_node != None:
# 노드 데이터 출력
print(temp_node.data, end='->')
# 다음 노드로 이동
temp_node = temp_node.next
print('Null')
if __name__ == '__main__':
# 연결 리스트 인스턴스 생성
linked_list = LinkedList()
# 연결 리스트에 데이터 삽입
linked_list.insert(Node(1))
linked_list.insert(Node(2))
linked_list.insert(Node(3))
linked_list.insert(Node(4))
linked_list.insert(Node(5))
linked_list.insert(Node(6))
linked_list.insert(Node(7))
# 연결 리스트 출력
linked_list.display()
위의 프로그램을 실행하면 다음 결과를 얻을 수 있습니다.
1->2->3->4->5->6->7->Null
이것으로 단일 연결 리스트에 대한 기본적인 내용을 모두 살펴보았습니다. 이제 단일 연결 리스트를 구현하는 방법을 알게 되었으니, 이를 바탕으로 이중 연결 리스트를 더욱 쉽게 이해할 수 있을 것입니다. 그럼 다음 섹션에서 이중 연결 리스트에 대해 알아보겠습니다.
#2. 이중 연결 리스트
이중 연결 리스트는 각 노드가 이전 노드와 다음 노드를 가리키는 두 개의 포인터를 가지고 있는 구조입니다. 따라서 각 노드는 데이터와 이전, 다음 노드의 주소를 저장하는 포인터로 구성됩니다.
첫 번째 노드의 이전 포인터는 null이며, 마지막 노드의 다음 포인터 역시 null 값을 가져 연결 리스트의 양쪽 끝을 나타냅니다.
아래 그림을 통해 이중 연결 리스트의 구조를 확인할 수 있습니다.
이중 연결 리스트는 단일 연결 리스트와 마찬가지로 유사한 구현 단계를 거칩니다. 똑같은 내용을 다시 설명하는 것은 지루할 수 있으니, 코드 예시를 통해 단계별로 빠르게 이해해 보도록 하겠습니다. 바로 시작해 보겠습니다.
이중 연결 리스트 구현
1. 이전 노드를 가리키는 포인터, 데이터, 다음 노드를 가리키는 포인터를 포함하여 이중 연결 리스트의 노드를 만듭니다.
class Node: def __init__(self, data): # 이전 노드를 가리키는 포인터 self.prev = None # 노드의 데이터 self.data = data # 다음 노드를 가리키는 포인터 self.next = None
2. 이중 연결 리스트 클래스를 정의합니다.
class LinkedList: def __init__(self): # 헤드를 None으로 초기화 self.head = None
3. 이중 연결 리스트에 새로운 노드를 삽입하는 방법입니다.
class LinkedList: # ... def insert(self, new_node): # 헤드가 비어있는지 확인 if self.head: # 마지막 노드 찾기 last_node = self.head while last_node.next != None: last_node = last_node.next # 새 노드의 이전 포인터에 마지막 노드 할당 new_node.prev = last_node # 마지막 노드의 다음 포인터에 새 노드 할당 last_node.next = new_node else: # 헤드가 비어 있으면 새 노드를 헤드로 지정 self.head = new_node
4. 이중 연결 리스트의 데이터를 출력하는 방법입니다.
class LinkedList:
# ...
def display(self):
# 정방향으로 데이터 출력
print("Normal Order: ", end='')
temp_node = self.head
while temp_node != None:
print(temp_node.data, end=' ')
temp_node = temp_node.next
print()
# 역방향으로 데이터 출력
print("Reverse Order: ", end='')
# 마지막 노드 찾기
last_node = self.head
while last_node.next != None:
last_node = last_node.next
temp_node = last_node
while temp_node != None:
print(temp_node.data, end=' ')
temp_node = temp_node.prev
print()
이것으로 이중 연결 리스트의 코드 구현을 살펴보았습니다. 이중 연결 리스트 클래스를 사용하기 위한 추가 코드는 직접 작성해 보시기 바랍니다. 단일 연결 리스트를 사용했던 방식과 유사하게 이중 연결 리스트 클래스를 활용해 보세요. 즐거운 코딩 시간이 되시길 바랍니다. 🙂
결론
연결 리스트를 기반으로 다양한 문제들이 존재합니다. 하지만 이 튜토리얼에서 배운 연결 리스트의 기본 구현을 잘 이해하는 것이 중요합니다. 이 글을 통해 새로운 개념을 배우는 데 도움이 되었기를 바랍니다.
즐거운 코딩 하세요! 🙂