연결 리스트(Linked List)는 데이터 요소들이 순차적으로 연결된 자료구조로, 각 노드는 데이터와 다음 노드를 가리키는 참조값으로 구성됩니다. 이번 글에서는 파이썬으로 연결 리스트를 직접 구현하고, 값 추가 메서드와 리스트 요소 출력 메서드를 함께 만들어 보겠습니다.
예제 코드
class Node:
def __init__(self, data):
self.data = data
self.next = None
class my_linked_list:
def __init__(self):
self.head = None
self.last_node = None
def add_value(self, my_data):
if self.last_node is None:
self.head = Node(my_data)
self.last_node = self.head
else:
self.last_node.next = Node(my_data)
self.last_node = self.last_node.next
def print_it(self):
curr = self.head
while curr is not None:
print(curr.data)
curr = curr.next
my_instance = my_linked_list()
n = int(input('How many elements should be added ? '))
for i in range(n):
data = int(input('Enter a data value : '))
my_instance.add_value(data)
print('The linked list is : ')
my_instance.print_it()실행 결과
How many elements should be added ? 4 Enter a data value : 6 Enter a data value : 7 Enter a data value : 8 Enter a data value : 9 The linked list is : 6 7 8 9
코드 설명
- 먼저 개별 데이터를 저장할 'Node' 클래스를 정의합니다. 각 노드는 data(데이터)와 next(다음 노드 참조) 속성을 가집니다.
- 연결 리스트 자체를 나타내는 'my_linked_list' 클래스를 생성합니다.
- 'init' 생성자 함수에서 첫 번째 노드인 head와 마지막 노드인 last_node를 모두 None으로 초기화합니다.
- 'add_value' 메서드는 연결 리스트에 새로운 데이터를 추가하는 역할을 합니다. 리스트가 비어 있으면 새 노드가 head가 되고, 그렇지 않으면 마지막 노드 뒤에 새 노드를 연결합니다.
- 'print_it' 메서드는 head부터 시작해 next 참조를 따라가며 모든 노드의 데이터를 콘솔에 출력합니다.
- 'my_linked_list' 클래스의 객체(my_instance)를 생성한 뒤, 사용자에게 추가할 요소의 개수를 입력받습니다.
- 입력받은 개수만큼 반복하면서 add_value 메서드를 호출해 데이터를 순서대로 추가합니다.
- 마지막으로 print_it 메서드를 호출하여 연결 리스트에 저장된 모든 값을 화면에 표시합니다.
이처럼 파이썬에서는 클래스 두 개(Node와 연결 리스트 클래스)만으로도 연결 리스트를 손쉽게 구현할 수 있습니다. 연결 리스트는 삽입과 삭제가 빈번한 상황에서 배열보다 유연하게 동작하는 자료구조이므로, 기본 구현 원리를 익혀두면 다양한 알고리즘 문제 해결에 큰 도움이 됩니다.