[Rust로 배우는 자료구조 ] 01. 연결 리스트(Linked List)
개인적으로 Rust를 공부하면서 자료구조와 관련된 내용을 정리하여 올린 글입니다. 틀린 부분에 대해 코멘트 남겨주시면 정말 감사드리겠습니다.
전체 소스코드와 테스트 결과는 아래의 링크에서 확인하실 수 있습니다. https://github.com/DonghyungKo/til/blob/master/rust/data-structures/src/single_linked_list.rs
러스트로 배우는 자료구조의 첫 장에서는 연결 리스트를 다뤄도록 하겠습니다.
연결 리스트 (Linked List) vs 배열 (Array)
연결 리스트는 일반적으로 친숙한 배열(Array)와 다른 모습을 하고 있습니다.
배열은 데이터가 메모리 상에 연속적으로 저장되는 특징을 가지고 있습니다. 따라서, 인덱스를 통해 데이터에 접근하는 것이 매우 빠르고 편리합니다.
반면, 연결 리스트를 구성하는 데이터는 노드(Node)라고 불리는 최소 단위로 구성되는데, 이 노드는 메모리 상에 무작위 공간에 나눠져 위치합니다. 따라서, 노드는 자신과 인접한 노드에 대한 포인터를 가짐으로써, 논리적으로 연결을 유지하여 리스트의 성격을 가질 수 있게 됩니다.
연결 리스트의 장점
왜, 연결 리스트는 이처럼 불편한(?) 구조를 선택하게 된 것일까요. 그 이유는 연결 리스트가 중간에 위치한 데이터를 추가(insert)하거나 제거(delete)하는 과정을 매우 효율적으로 수행할 수 있기 때문입니다.
배열은 중간에 위치한 i 번째 데이터를 제거할 경우, i번째 index 뒤에 존재하는 모든 데이터를 한 칸씩 앞으로 움직여야 합니다. 이에 반해, 연결 리스트는 i번째 노드를 제거하고 (i-1)번째 노드와 (i+1)번째 노드를 연결하면 됩니다. 데이터를 추가하는 과정도 이와 유사하게 동작합니다.
연결 리스트의 단점
- 연결 리스트는 i번째 노드에 접근하기 위해서는 첫 번째 노드부터 데이터를 순차적으로 탐색해야 하기 때문에 데이터 탐색 과정이 비효율적입니다. 이에 반해 배열은 데이터 크기 만큼 포인터를 움직이면서 데이터를 탐색하기 때문에 매우 효율적입니다.
- 연결 리스트는 데이터와 함께 포인터를 저장하기 때문에 메모리를 더 많이 사용합니다.
Rust Implementation
Node
연결 리스트는 최소 구성단위인 노드로 구성되어 있습니다. 노드는 데이터와 다음 노드에 대한 포인터를 가지고 있습니다.
LinkedList- setter methods (front/back)
다음으로, 연결 리스트 코드를 작성해보도록 하겠습니다. 연결 리스트는 노드들의 연결로 이루어져 있습니다. 따라서, 따라서, 노드가 추가될 때에는 인접한 노드와 새롭게 추가되는 노드를 연결시켜 주어야 합니다.
LinkedList- getter methods(front/back)
LinkedList- setter (insert to the middle)
노드를 연결 리스트 앞/뒤에 추가할 때는 1개의 노드의 연결만 업데이트 하면 됩니다. 반면, 노드를 연결 리스트의 중간에 추가할 때에는 인접한 2개의 노드의 연결을 모두 업데이트 해주어야 합니다.
LinkedList- getter (by index)
연결 리스트를 탐색하기 위해서는 맨 앞 노드부터 뒤로 연결된 노드를 차례대로 순회하여야 합니다.
LinkedList- Pop
Further Topics
[1] NonNull<T> vs *mut T
Rust standard library는 NonNull<T> 데이터 타입을 지원합니다. Rust 공식 문서에서는 NonNull<T>를 다음과 같이 설명하고 있습니다.
*mut T but non-zero and covariant.
[2] When to use LinkedList?
러스트 공식 문서에서는 다음과 같이 이야기 하고 있습니다.
The `LinkedList` allows pushing and popping elements at either end in constant time. Almost always it is better to use `Vec` or `VecDeque` instead of `LinkedList`. In general, array-based containers are faster, more memory efficient and make better use of CPU cache.
