링크드 리스트의 구조와 단일, 이중, 원형 리스트를 Python으로 구현하는 방법을 소개합니다.
✅ 링크드 리스트란?
링크드 리스트(Linked List)는 데이터를 노드(Node) 단위로 저장하고, 각 노드가 다음 노드의 주소를 가리키는 구조의 자료구조입니다. 배열과 달리 크기가 동적으로 조절되며, 삽입과 삭제가 용이한 특징이 있습니다. 링크드 리스트는 구조에 따라 **단일(Singly), 이중(Doubly), 원형(Circular)**으로 나뉩니다.
1️⃣ 단일 링크드 리스트(Singly Linked List)
단일 링크드 리스트는 각 노드가 데이터를 저장하고 다음 노드를 가리키는 포인터를 포함합니다. 마지막 노드는 None을 가리키며 리스트의 끝을 나타냅니다.
# 단일 링크드 리스트 구현
class Node:
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
def display(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# 사용 예제
sll = SinglyLinkedList()
sll.append(10)
sll.append(20)
sll.append(30)
sll.display()
# 출력: 10 -> 20 -> 30 -> None
2️⃣ 이중 링크드 리스트(Doubly Linked List)
이중 링크드 리스트는 각 노드가 **이전 노드와 다음 노드**를 가리키는 포인터를 포함합니다. 양방향 탐색이 가능하며, 삽입과 삭제가 더 유연합니다.
# 이중 링크드 리스트 구현
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
new_node.prev = current
def display(self):
current = self.head
while current:
print(current.data, end=" <-> ")
current = current.next
print("None")
# 사용 예제
dll = DoublyLinkedList()
dll.append(10)
dll.append(20)
dll.append(30)
dll.display()
# 출력: 10 <-> 20 <-> 30 <-> None
3️⃣ 원형 링크드 리스트(Circular Linked List)
원형 링크드 리스트는 마지막 노드가 첫 번째 노드를 가리키며 연결이 순환되는 구조입니다. 끝없이 반복되는 데이터 구조에 적합합니다.
# 원형 링크드 리스트 구현
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
self.head.next = self.head
return
current = self.head
while current.next != self.head:
current = current.next
current.next = new_node
new_node.next = self.head
def display(self):
current = self.head
if not current:
return
while True:
print(current.data, end=" -> ")
current = current.next
if current == self.head:
break
print("HEAD")
# 사용 예제
cll = CircularLinkedList()
cll.append(10)
cll.append(20)
cll.append(30)
cll.display()
# 출력: 10 -> 20 -> 30 -> HEAD
결론
링크드 리스트는 다양한 유형의 데이터 연결과 관리에 강력한 유연성을 제공합니다. 단일 링크드 리스트는 간단한 데이터 연결에 적합하며, 이중 링크드 리스트는 양방향 탐색과 복잡한 삽입/삭제가 필요한 경우 유용합니다. 원형 링크드 리스트는 순환 구조가 필요한 특정 시나리오에서 효과적입니다.
개인적으로 링크드 리스트를 학습하면서 가장 느낀 점은, 자료구조의 선택이 단순히 성능을 넘어서 문제 해결 방식 자체에 영향을 미친다는 것입니다. 특히, 링크드 리스트는 메모리 관리와 동적 데이터 처리의 중요성을 깊이 이해하는 데 도움을 줍니다.
앞으로 자료구조를 활용한 다양한 문제를 접할 때, 링크드 리스트의 장점과 한계를 파악하며 최적의 선택을 하는 것이 중요합니다. 이를 통해 더욱 효율적이고 창의적인 프로그래밍이 가능할 것입니다.