자료 구조 - 단일 연결 리스트 Singly Linked List, 파이썬으로 구현한 단일 연결 리스트 예제

연결 리스트Linked List란?

각 노드(node)가 데이터와 포인터를 가지고 한 줄로 연결된 자료 구조.

참고: 위키백과 연결 리스트

 

그렇다면 노드란?

단일 연결 리스트 예 (출처: 위키백과)

위 그림에서 네모 두 칸이 노드다. 12가 데이터, 다른 노드를 가리키고 있는 화살표가 바로 포인터다.

 

파이썬 노드 코드 예

	class Node:
	def __init__(self, value):
	self._value = value
	self._next_node = None
	def set_value(self, value):
	self._value = value
	def get_value(self):
	return self._value
	def set_next_node(self, node):
	self._next_node = node
	def get_next_node(self):
	return self._next_node
	if __name__ == '__main__':
	node_num1 = Node(1)
	node_num2 = Node(2)
	node_num1.set_next_node(node_num2)
	print(node_num1.get_value())
	print(node_num1.get_next_node())
	print(node_num2.get_value())
	'''
	# Result example
	1
	<__main__.Node object at 0x7f7e88203d30>
	2
	'''

view raw python_data_structure_node.py hosted with ❤ by GitHub

 

노드를 한 줄로 연결하게 되면 연결 리스트가 된다.

연결 리스트 중 포인터가 하나인 경우가 단일 연결 리스트이다.

 

단일 연결 리스트 파이썬 구현 예

아래는 파이썬으로 구현한 단일 연결 리스트 예이다.

 

	from typing import Any
	from node import Node
	class SinglyLinkedList:
	def __init__(self, value=None):
	self._head_node = Node(value)
	def get_head_node(self) -> Node:
	return self._head_node
	def insert(self, value: Any):
	if self._head_node is None:
	node = Node(value)
	self._head_node = node
	else:
	current_node = self._head_node
	while current_node.get_next_node():
	current_node = current_node.get_next_node()
	node = Node(value)
	current_node.set_next_node(node)
	def stringify_list(self) -> str:
	stringify_list = ""
	current_node = self.get_head_node()
	while current_node:
	if current_node.get_value() is not None:
	stringify_list = stringify_list + str(current_node.get_value()) + " -> "
	current_node = current_node.get_next_node()
	return stringify_list
	if __name__ == '__main__':
	linked_list = SinglyLinkedList()
	linked_list.insert(1)
	linked_list.insert(2)
	print(linked_list.stringify_list())
	'''
	# Result example
	1 -> 2 ->
	'''

view raw python_data_structure_singly_linked_list.py hosted with ❤ by GitHub

 

 

 

앞에서 살펴본 스택이나 큐보다 훨씬 복잡하다.

노드란 객체를 만들어서 연결하기 때문에 더 복잡해 보인다.

코드를 이해하기 위해서는 천천히 살펴볼 필요가 있다.

 

그렇다면 왜 연결 리스트를 사용할까?

많은 프로그래밍 언어에서 배열이란 자료형을 사용할 경우, 배열 크기를 미리 정의하고 사용한다. 자바 코드를 예로 들면 아래와 같다.

class Main {
    public static void main(String[] args) {
        int[] arr = new int[3];
        arr[0] = 1;
        arr[1] = 2;
        arr[2] = 3;
        System.out.println(arr[0]);
        System.out.println(arr[1]);
        System.out.println(arr[2]);
        System.out.println(arr);
    }
}

위 코드에서 new int[3]으로 int 타입 배열로 크기는 3을 선언하고 사용하게 된다. 값 4개는 저장할 수 없다.

만약 크기가 4이고 값이 {1, 2, 3}인 배열에 1과 2 사이에 0을 넣게 된다면, {1, 0, 2, 3}으로 2와 3의 값을 다음 칸으로 옮겨야 하는 번거로움이 생긴다.

연결 리스트로 구현하면 크기를 제한 없이 늘릴 수 있다. 또 중간에 임의로 쉽게 데이터를 넣을 수 있게 된다.

 

파이썬의 리스트는 배열일까? 아니면 연결 리스트일까?

nums = []
nums.append(1)
nums.append(2)
nums.append(3)
print(nums[0])
print(id(nums[0]))
print(nums[1])
print(id(nums[1]))
print(nums[2])
print(id(nums[2]))

nums.insert(1, 10)
print(nums)

print(nums[0])
print(id(nums[0]))
print(nums[1])
print(id(nums[1]))
print(nums[2])
print(id(nums[2]))
print(nums[3])
print(id(nums[3]))

출력 결과

1
4447828320
2
4447828352
3
4447828384
[1, 10, 2, 3]
1
4447828320
10
4447828608
2
4447828352
3
4447828384

위 출력 결과를 보면 10만 주소값이 뛴 것을 볼 수 있고, 2와 3의 주소값은 그대로인 것을 알 수 있다. 파이썬 리스트 자체가 연결 리스트로 구현되어 있다고 추정할 수 있다.