연결 리스트(Linked List)에서 특정 개수의 요소만 뒤집어야 하는 경우가 있습니다. 이럴 때 reverse_list라는 메서드를 정의하면, 리스트를 순회하면서 지정한 개수의 요소만 효율적으로 반전시킬 수 있습니다.
아래 예제를 통해 실제 구현 과정을 살펴보겠습니다.
예제 코드
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList_structure:
def __init__(self):
self.head = None
self.last_node = None
def add_vals(self, data):
if self.last_node is None:
self.head = Node(data)
self.last_node = self.head
else:
self.last_node.next = Node(data)
self.last_node = self.last_node.next
def print_it(self):
curr = self.head
while curr:
print(curr.data)
curr = curr.next
def reverse_list(my_list, n):
if n == 0:
return
before_val = None
curr = my_list.head
if curr is None:
return
after_val = curr.next
for i in range(n):
curr.next = before_val
before_val = curr
curr = after_val
if after_val is None:
break
after_val = after_val.next
my_list.head.next = curr
my_list.head = before_val
my_instance = LinkedList_structure()
my_list = input('연결 리스트에 넣을 요소들을 입력하세요... ').split()
for elem in my_list:
my_instance.add_vals(int(elem))
n = int(input('뒤집고 싶은 요소의 개수를 입력하세요... '))
reverse_list(my_instance, n)
print('새로운 리스트 : ')
my_instance.print_it()실행 결과
연결 리스트에 넣을 요소들을 입력하세요... 45 67 89 12 345 뒤집고 싶은 요소의 개수를 입력하세요... 3 새로운 리스트 : 89 67 45 12 345
코드 설명
Node 클래스 생성: 연결 리스트의 각 노드를 나타내는
Node클래스를 정의합니다. 각 노드는 데이터(data)와 다음 노드를 가리키는 포인터(next)를 가집니다.LinkedList_structure 클래스 생성: 연결 리스트 자체를 관리하는 클래스로, 필요한 속성들을 포함합니다.
init 함수: 리스트의 첫 번째 요소인
head와 마지막 노드인last_node를None으로 초기화합니다.add_vals 메서드: 리스트 끝에 새로운 값을 추가하는 기능을 담당합니다. 리스트가 비어 있으면 새 노드를 head로 설정하고, 그렇지 않으면 마지막 노드 뒤에 연결합니다.
print_it 메서드: 연결 리스트의 모든 값을 콘솔에 출력하는 역할을 합니다.
reverse_list 메서드: 핵심 로직으로, 앞에서부터 N개의 노드를 순차적으로 가리키는 방향을 바꿔서 해당 구간만 뒤집습니다. 세 개의 포인터(
before_val,curr,after_val)를 활용해 노드의 연결 순서를 변경한 후, head를 새로운 시작점으로 갱신합니다.인스턴스 생성 및 데이터 입력:
LinkedList_structure의 인스턴스를 만들고, 사용자로부터 입력받은 값들을 연결 리스트에 추가합니다.뒤집을 개수 입력: 사용자에게 뒤집고자 하는 요소의 개수를 입력받습니다.
결과 출력:
reverse_list메서드를 호출해 리스트를 뒤집은 뒤, 최종 결과를 콘솔에 출력합니다.
동작 원리 요약
이 알고리즘은 시간 복잡도 O(n)으로 동작합니다. 처음 N개 노드의 next 포인터를 역방향으로 재설정하고, N번째 노드를 새로운 head로 만든 다음, 원래 N번째 노드(뒤집힌 후에는 마지막)가 N+1번째 노드를 가리키도록 연결하여 나머지 리스트를 그대로 유지합니다. 위 실행 결과에서 3개의 요소(45, 67, 89)가 뒤집혀 89, 67, 45 순서로 변경되고, 나머지 요소(12, 345)는 원래 순서를 유지하는 것을 확인할 수 있습니다.