개인적으로 Rust를 공부하면서 자료구조와 관련된 내용을 rust standard library를 참조하여 정리한 글입니다. 틀린 부분에 대해 코멘트 남겨주시면 정말 감사드리겠습니다.
전체 소스코드와 테스트 결과는 아래의 링크에서 확인하실 수 있습니다.
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
연결 리스트는 최소 구성단위인 노드로 구성되어 있습니다. 노드는 데이터와 다음 노드에 대한 포인터를 가지고 있습니다.
struct Node<T> {
val: T,
next: Option<NonNull<Node<T>>>,
}
// public methods
impl<T> Node<T> {
pub fn new(t: T) -> Node<T> {
Node { val: t, next: None }
}
}LinkedList- setter methods (front/back)
다음으로, 연결 리스트 코드를 작성해보도록 하겠습니다. 연결 리스트는 노드들의 연결로 이루어져 있습니다. 따라서, 따라서, 노드가 추가될 때에는 인접한 노드와 새롭게 추가되는 노드를 연결시켜 주어야 합니다.
// setter methods
impl<T> LinkedList<T> {
/// Appends element to the back.
#[inline]
pub fn push_back(&mut self, val: T) {
self.push_back_node(Box::new(Node::new(val)))
}
/// Appends element to the front
#[inline]
pub fn push_front(&mut self, val: T) {
self.push_front_node(Box::new(Node::new(val)))
}
/// Appends the given node to the back of LinkedList
#[inline]
fn push_back_node(&mut self, node: Box<Node<T>>) {
unsafe {
let node = Some(NonNull::new_unchecked(Box::into_raw(node)));
match self.tail {
None => self.head = node,
Some(mut tail) => tail.as_mut().next = node,
}
self.tail = node;
self.length += 1;
}
}
/// Appends the given node to the front of LinkedList
#[inline]
fn push_front_node(&mut self, node: Box<Node<T>>) {
unsafe {
let mut node = Some(NonNull::new_unchecked(Box::into_raw(node)));
match self.head {
None => self.tail = node,
Some(head) => node.as_mut().unwrap().as_mut().next = Some(head),
}
self.head = node;
self.length += 1;
}
}
}LinkedList- getter methods(front/back)
다음으로 getter method를 구현하였습니다.
// getter methods (front/back)
impl<T> LinkedList<T> {
/// Provides a reference to the front element or `None` LinkedList is empty
#[inline]
pub fn front(&self) -> Option<&T> {
unsafe { self.head.as_ref().map(|node| &(node.as_ref().val)) }
}
/// Provides a mutable reference to the front element or `None` LinkedList is empty
#[inline]
pub fn front_mut(&mut self) -> Option<&T> {
unsafe { self.head.as_mut().map(|node| &(node.as_mut().val)) }
}
/// Provides a reference to the back element or `None` LinkedList is empty
#[inline]
pub fn back(&self) -> Option<&T> {
unsafe { self.tail.as_ref().map(|node| &(node.as_ref().val)) }
}
/// Provides a mutable reference to the back element or `None` LinkedList is empty
#[inline]
pub fn back_mut(&mut self) -> Option<&T> {
unsafe { self.tail.as_mut().map(|node| &(node.as_mut().val)) }
}
}LinkedList- setter (insert to the middle)
노드를 연결 리스트 앞/뒤에 추가할 때는 1개의 노드의 연결만 업데이트 하면 됩니다. 반면, 노드를 연결 리스트의 중간에 추가할 때에는 인접한 2개의 노드의 연결을 모두 업데이트 해주어야 합니다.
// setter methods (by index)
impl<T> LinkedList<T> {
/// Insert node to i-th index of LinkedList.
/// If given index if bigger than length of LinkedList,
/// Node will be attached to the tail of LinkedList
#[inline]
pub fn insert(&mut self, val: T, index: u32) {
self.insert_node(Box::new(Node::new(val)), index)
}
#[inline]
fn insert_node(&mut self, mut node: Box<Node<T>>, index: u32) {
if index > self.length {
return self.push_back_node(node);
}
if index == 0 {
return self.push_front_node(node);
}
unsafe {
let mut front = self.get_ith_node(self.head, index - 1).unwrap(); // None is unreachable
let back = front.as_ref().next;
// [front] -> [middle] -> [back]
node.next = back;
let middle = NonNull::new_unchecked(Box::into_raw(node));
front.as_mut().next = Some(middle);
}
self.length += 1;
}
}LinkedList- getter (by index)
연결 리스트를 탐색하기 위해서는 맨 앞 노드부터 뒤로 연결된 노드를 차례대로 순회하여야 합니다.
// getter methods (by index)
impl<T> LinkedList<T> {
/// Provides a reference to i-th element or `None` if i-th node does not exists
#[inline]
pub fn get(&mut self, index: u32) -> Option<&T> {
if index > self.length {
return None;
}
self.get_ith_node(self.head, index)
.map(|node| unsafe { &((*node.as_ptr()).val) })
}
/// Provide i-th node of LinkedList or `None` if i-th node does not exists
#[inline]
fn get_ith_node(
&mut self,
node: Option<NonNull<Node<T>>>,
index: u32,
) -> Option<NonNull<Node<T>>> {
// recursively follow linked nodes
match node {
None => None, // not enough
Some(next_ptr) => match index {
0 => Some(unsafe { next_ptr }), // reached end
_ => self.get_ith_node(unsafe { (*next_ptr.as_ptr()).next }, index - 1), // to next node
},
}
}
}LinkedList- Pop
마지막으로 pop 메서드를 구현하였습니다.
impl<T> LinkedList<T> {
/// Pop element from the back of LinkedList, or return `None` if empty
#[inline]
pub fn pop_back(&mut self) -> Option<T> {
self.pop_back_node().map(Node::into_element)
}
/// Pop node from the back of LinkedList, or return `None` if empty
/// This will unlink the last node from LinkedList
#[inline]
fn pop_back_node(&mut self) -> Option<Box<Node<T>>> {
self.tail.map(|node_ptr| {
unsafe {
if self.length > 1 {
self.tail = self.get_ith_node(self.head, self.length - 2);
} else {
self.tail = None;
}
match self.tail {
None => self.head = None,
Some(mut tail) => {
tail.as_mut().next = None;
}
}
}
self.length -= 1;
let node = unsafe { Box::from_raw(node_ptr.as_ptr()) };
node
})
}
}Further Topics
[1] NonNull vs *mut T
Rust standard library는 NonNull 데이터 타입을 지원합니다. Rust 공식 문서에서는 NonNull를 다음과 같이 설명하고 있습니다.
*mut T but non-zero and covariant.
[2] When to use LinkedList?
러스트 공식 문서에서는 다음과 같이 이야기 하고 있습니다.
The
LinkedListallows pushing and popping elements at either end in constant time. Almost always it is better to useVecorVecDequeinstead ofLinkedList. In general, array-based containers are faster, more memory efficient and make better use of CPU cache.
