LinkedList, VecDeque 등

컬렉션 중에서 특정한 상황에서 보다 편리하게 쓸 수 있는 자료구조로 LinkedList와 VecDeque가 있다. 둘 다 특정 연산에 유리한 특성을 가지고 있으나, 일반적인 용도로는 Vec이나 다른 고수준 컬렉션을 사용하는 것이 더 효율적일 때가 많다. 그렇기 때문에 이 두 자료구조를 선택할 때는 내부 동작 원리와 시간 복잡도, 메모리 사용 패턴 등을 충분히 고려해야 한다.

LinkedList는 이중 연결 리스트(doubly linked list) 형태로 구성되어 있다. 각 노드는 자신의 앞 노드와 뒤 노드의 포인터를 가지고 있어서, 특정 노드를 기준으로 앞뒤로 순회가 가능하다. 삽입과 삭제는 리스트의 임의 위치에서 기존 노드를 가리키는 참조자만 알고 있다면 O(1)에 수행 가능하다는 점이 특징이다. 그러나 연속된 메모리를 활용하는 Vec과 달리 노드가 흩어져 있고, 각 노드가 추가적인 포인터를 갖고 있으므로 힙 메모리 할당이 잦아질 수 있다. 또한 임의의 위치에 접근하기 위해서는 앞에서부터 차례대로 노드를 따라가야 하므로 O(n)이 걸린다. 따라서 순회와 랜덤 액세스가 잦은 경우에는 LinkedList가 오히려 성능적으로 불리할 수 있다. 그럼에도 불구하고 삽입/삭제가 빈번한 특정 지점이 확정되어 있거나, 매우 특수한 상황에서만 LinkedList가 적합하다.

LinkedList를 만들고 사용하는 방법은 다음과 같다.

use std::collections::LinkedList;

fn main() {
    let mut list = LinkedList::new();
    list.push_back(10);
    list.push_back(20);
    list.push_front(0);

    println!("{:?}", list);

    list.pop_front();
    list.push_back(30);

    println!("{:?}", list);

    // 노드 순회를 예시로 확인
    for val in list.iter() {
        println!("값: {}", val);
    }
}

위 코드에서 list는 [0, 10, 20]의 형태로 초기 구성된 뒤, pop_front()를 통해 0이 빠져나가고 30을 뒤에 추가하여 [10, 20, 30]으로 변경된다. LinkedList는 iter() 메서드로 순회할 수 있고, iter_mut(), into_iter() 등을 활용하여 가변 순회나 값 이동도 가능하다. 이러한 메서드는 표준 라이브러리의 다른 컬렉션과 유사한 디자인 패턴을 따른다.

LinkedList는 노드 단위로 메모리가 분산되어 있기 때문에 CPU 캐시 지역성이 낮아질 수 있다. 대규모 데이터를 한꺼번에 순회해야 하는 경우, Vec이 일반적으로 더 빠른 성능을 낸다. LinkedList는 어딘가에서 이미 노드를 가리키고 있는 포인터가 주어져 있을 때 그 자리에 손쉽게 삽입하거나 삭제할 필요가 있을 때만 진정한 장점을 발휘한다. 일반적으로 Rust 표준 라이브러리 문서에서도 “특수한 상황이 아니라면 LinkedList를 쓰지 않는 것이 좋다”는 언급이 있다.

VecDeque는 양쪽 끝에서 O(1)에 가까운 시간 안에 데이터를 추가하거나 제거할 수 있는 이중 데크(double-ended queue) 자료구조이다. 내부적으로는 고정 크기 배열을 두 개 이상 링 버퍼(ring buffer) 형태로 연결해 관리하며, 큐의 앞뒤가 가득 차면 내부적으로 새로운 공간을 재할당하거나 재배치한다. 단방향 큐(Queue)가 필요한데 양쪽 끝에서 삽입 혹은 삭제가 발생하는 상황이라면 VecDeque가 유리하다.

VecDeque의 가장 큰 장점은 push_front, pop_front, push_back, pop_back 연산을 모두 평균적으로 O(1)에 처리할 수 있다는 것이다. 표준 라이브러리의 Vec은 push/pop 연산을 끝쪽에 대해서만 O(1)을 보장하고 앞쪽에 대해서는 O(n)이 될 수 있으므로, 자료의 앞쪽 끝에서 삽입이나 제거가 많이 발생하는 경우에는 VecDeque가 적절하다.

VecDeque를 생성하고 사용하는 예시는 다음과 같다.

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::new();
    deque.push_back(1);
    deque.push_back(2);
    deque.push_back(3);
    deque.push_front(0);

    println!("{:?}", deque);

    deque.pop_back();
    deque.push_front(-1);

    println!("{:?}", deque);

    for val in &deque {
        println!("값: {}", val);
    }
}

이 코드는 [-1, 0, 1, 2]를 출력한 뒤 순회하여 각 값을 하나씩 출력한다. deque에 값이 더 많이 쌓여 있는 상황이라 해도 양쪽 끝에서의 삽입 삭제는 빠르다. 다만 VecDeque 역시 중간 위치에 임의로 삽입하거나 삭제를 수행하면 내부 요소들을 재배치해야 하므로 O(n)이 발생한다. 이 점에서 LinkedList와는 다른 전략을 쓰지만, 역시나 중간 연산에는 비용이 크다.

LinkedList와 VecDeque 모두 특정 케이스에서만 높은 효율성을 제공하므로, 일반적인 시나리오라면 다른 컬렉션(Vec, HashMap, BTreeMap 등)을 사용하는 편이 좋다. 그럼에도 불구하고 매우 큰 데이터를 리스트 형태로 유지하면서 특정 지점 노드에 대한 삽입·삭제가 매우 빈번하거나, 양쪽 끝에서 값의 추가·제거가 지속적으로 이루어지는 큐 시나리오처럼 명확한 요구 사항이 있다면 LinkedList나 VecDeque가 최적일 수 있다. Rust는 이 두 자료구조에 대하여 안전성을 최대한 보장함과 동시에, 개발자가 내부 구현이나 특성(시간 복잡도, 메모리 사용, CPU 캐시 적중률 등)을 충분히 고려하여 사용할 수 있도록 잘 정리된 API를 제공한다.

컬렉션을 선택할 때는 각 자료구조의 장단점을 반드시 분석해야 하며, Rust의 표준 라이브러리는 다양한 상황에 맞춰서 사용할 수 있도록 여러 가지 대안을 제시하고 있다. LinkedList와 VecDeque도 그중 하나이며, 지나치게 난해한 자료구조를 직접 구현하지 않고도 필요한 기능을 빠르게 적용할 수 있다는 점에서 중요한 도구가 된다. 사용 전에 실제로 요구되는 작업, 데이터의 크기, 접근 및 삽입 패턴을 면밀히 살피는 것이 성능 및 코드 유지보수에 큰 도움이 될 것이다.