파이썬으로 연결 리스트 끝에서 N번째 노드 출력하기

연결 리스트(Linked List)의 끝에서 특정 위치의 노드를 출력해야 하는 경우, list_length와 return_from_end 두 가지 메서드를 정의하여 해결할 수 있습니다.

list_length 메서드는 연결 리스트의 전체 길이를 계산하여 반환하며, return_from_end 메서드는 이 길이를 활용해 끝에서 n번째에 해당하는 요소를 반환합니다.

아래는 실제 동작 과정을 보여주는 예시입니다.

예제 코드

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 list_length(my_list):
    my_len = 0
    curr = my_list.head
    while curr:
        curr = curr.next
        my_len = my_len + 1
    return my_len

def return_from_end(my_list, n):
    l = list_length(my_list)
    curr = my_list.head
    for i in range(l - n):
        curr = curr.next
    return curr.data

my_instance = LinkedList_structure()

my_list = input('Enter the elements of the linked list..').split()
for elem in my_list:
    my_instance.add_vals(int(elem))

n = int(input('Enter the value for n.. '))
my_result = return_from_end(my_instance, n)

print('The nth element from the end is: {}'.format(my_result))

실행 결과

Enter the elements of the linked list..45 31 20 87 4
Enter the value for n.. 2
The nth element from the end is: 87

코드 설명

노드 하나를 표현하는 Node 클래스를 생성합니다. 각 노드는 데이터(data)와 다음 노드를 가리키는 참조(next)를 가집니다.
필요한 속성을 갖춘 LinkedList_structure 클래스를 생성합니다.
__init__ 함수에서 첫 번째 요소인 head와 마지막 노드인 last_node를 None으로 초기화합니다.
add_vals 메서드를 정의하여 연결 리스트의 끝에 새로운 값을 추가할 수 있도록 합니다.
list_length 메서드는 처음부터 끝까지 순회하며 연결 리스트의 길이를 계산한 뒤 반환합니다.
return_from_end 메서드는 전체 길이에서 n을 뺀 만큼 앞으로 이동하여, 끝에서 n번째 요소의 데이터를 반환합니다.
LinkedList_structure 클래스의 인스턴스를 생성합니다.
사용자에게 연결 리스트의 요소들을 입력받아 순서대로 추가합니다.
끝에서 몇 번째 값을 원하는지 나타내는 n값을 입력받습니다.
연결 리스트에 대해 return_from_end 메서드를 호출하고, 그 결과를 콘솔에 출력합니다.

참고: 시간 복잡도

위 방식은 리스트를 두 번 순회하기 때문에 시간 복잡도는 O(n)입니다. 두 개의 포인터를 활용하면 한 번의 순회만으로도 같은 결과를 얻을 수 있습니다. 즉, 첫 번째 포인터를 n칸 먼저 이동시킨 뒤 두 포인터를 함께 끝까지 이동하면, 첫 번째 포인터가 끝에 도달했을 때 두 번째 포인터가 바로 끝에서 n번째 노드를 가리키게 됩니다.