두 개의 연결 리스트(Linked 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 is not None:
print(curr.data)
curr = curr.next
def add_linked_list(my_list_1, my_list_2):
sum_list = LinkedList_structure()
curr_1 = my_list_1.head
curr_2 = my_list_2.head
while (curr_1 and curr_2):
sum_val = curr_1.data + curr_2.data
sum_list.add_vals(sum_val)
curr_1 = curr_1.next
curr_2 = curr_2.next
if curr_1 is None:
while curr_2:
sum_list.add_vals(curr_2.data)
curr_2 = curr_2.next
else:
while curr_1:
sum_list.add_vals(curr_1.data)
curr_1 = curr_1.next
return sum_list
my_list_1 = LinkedList_structure()
my_list_2 = LinkedList_structure()
my_list = input('Enter the elements of the first linked list : ').split()
for elem in my_list:
my_list_1.add_vals(int(elem))
my_list = input('Enter the elements of the second linked list : ').split()
for elem in my_list:
my_list_2.add_vals(int(elem))
sum_list = add_linked_list(my_list_1, my_list_2)
print('The sum of elements in the linked list is ')
sum_list.print_it()출력
Enter the elements of the first linked list : 56 34 78 99 54 11 Enter the elements of the second linked list : 23 56 99 0 122 344 The sum of elements in the linked list is 79 90 177 99 176 355
설명
먼저 노드를 표현하는 'Node' 클래스가 생성됩니다. 각 노드는 데이터 값과 다음 노드를 가리키는 포인터를 가집니다.
필요한 속성을 포함하는 'LinkedList_structure' 클래스가 생성됩니다.
클래스에는 '__init__' 함수가 있으며, 첫 번째 요소인 'head'와 마지막 노드인 'last_node'를 'None'으로 초기화합니다.
'add_vals' 메서드가 정의되어 연결 리스트 끝에 새로운 값을 추가합니다. 마지막 노드를 별도로 추적하기 때문에 삽입 작업은 O(1)의 시간 복잡도를 가집니다.
'print_it' 메서드가 정의되어 연결 리스트의 모든 값을 순회하며 화면에 출력합니다.
'add_linked_list' 함수가 정의되어 두 연결 리스트의 대응 위치 요소들을 더합니다. 두 리스트를 동시에 순회하며 각 위치의 데이터를 더해 새로운 리스트를 만듭니다.
한쪽 리스트가 먼저 끝나면, 남은 리스트의 나머지 요소들이 그대로 결과 리스트에 추가됩니다. 따라서 길이가 다른 두 리스트도 문제없이 처리할 수 있습니다.
'LinkedList_structure'의 두 인스턴스가 생성되고, 사용자 입력을 받아 각 리스트에 정수 요소들이 추가됩니다.
마지막으로 'add_linked_list' 함수가 호출되어 합산된 새로운 연결 리스트가 반환되며, 그 결과가 콘솔에 출력됩니다.
이 알고리즘의 전체 시간 복잡도는 두 리스트 중 더 긴 것의 길이에 비례하는 O(n)이며, 추가 공간 역시 결과 리스트 크기만큼 필요합니다.