[Rust] LinkedList 사용법: 예제와 시간복잡도 분석

LinkedList: Rust에서의 양방향 연결 리스트 구현

Rust의 표준 라이브러리에서 제공하는 LinkedList는 양방향 연결 리스트(doubly-linked list)를 구현한 자료구조입니다. 연결 리스트는 각 요소가 개별 노드로 구성되며, 노드 간 링크를 통해 연결됩니다. 이는 Vec이나 VecDeque와는 다른 방식으로 메모리 관리를 하며 특정 상황에서 더 적합한 선택이 될 수 있습니다. Rust 자료구조 중 하나로, LinkedList는 삽입과 삭제가 빈번한 작업에서 효율적입니다.

---

1. LinkedList의 주요 특징

1. 양방향 링크:
   • 각 노드는 이전 노드와 다음 노드에 대한 포인터를 포함하여 양방향으로 탐색이 가능합니다.
2. 양쪽 끝에서의 빠른 삽입/삭제:
   • push_front와 push_back으로 O(1)의 시간 복잡도로 양쪽 끝에서 삽입이 가능합니다.
   • pop_front와 pop_back으로 O(1) 시간 내에 양쪽 끝에서 요소를 제거할 수 있습니다.
3. 랜덤 접근 비효율:
   • 특정 인덱스의 요소를 가져오려면 O(n)의 시간이 소요됩니다.
4. 노드 기반 메모리 구조:
   • 각 노드는 독립적으로 메모리에 저장되므로 메모리가 연속적이지 않을 수 있습니다. 따라서 CPU 캐시 효율은 낮을 수 있습니다.
5. 동적 크기 조정:
   • 연결 리스트는 사전 용량 설정 없이 필요에 따라 크기를 동적으로 조정할 수 있습니다.

---

2. LinkedList의 생성 방법

기본 생성

use std::collections::LinkedList;

let list: LinkedList<i32> = LinkedList::new();

설명: 빈 LinkedList를 생성합니다.

배열로부터 생성

let list: LinkedList<_> = LinkedList::from([1, 2, 3, 4]);

설명: 배열을 기반으로 LinkedList를 초기화합니다.

---

3. 주요 메서드

요소 삽입 및 제거

• push_front(value): 리스트의 앞에 요소를 추가합니다.
• push_back(value): 리스트의 뒤에 요소를 추가합니다.
• pop_front(): 리스트의 앞 요소를 제거하고 반환합니다.
• pop_back(): 리스트의 마지막 요소를 제거하고 반환합니다.

예제

let mut list = LinkedList::new();
list.push_back(1);
list.push_front(2);
assert_eq!(list.pop_front(), Some(2));
assert_eq!(list.pop_back(), Some(1));

요소 접근

• front(): 첫 번째 요소에 대한 참조를 반환합니다.
• back(): 마지막 요소에 대한 참조를 반환합니다.
• iter(): 리스트의 요소를 순회하는 반복자를 반환합니다.

예제

let mut list = LinkedList::from([1, 2, 3]);
assert_eq!(list.front(), Some(&1));
assert_eq!(list.back(), Some(&3));

for value in list.iter() {
    println!("{}", value);
}

리스트 병합

• append(other): 다른 LinkedList의 모든 요소를 병합합니다.

예제

let mut list1 = LinkedList::from([1, 2]);
let mut list2 = LinkedList::from([3, 4]);
list1.append(&mut list2);
assert_eq!(list1, LinkedList::from([1, 2, 3, 4]));
assert!(list2.is_empty());

---

4. 실제 활용 예시

LRU 캐시 구현

LinkedList는 최근 사용된 요소를 효율적으로 관리하는 LRU(Least Recently Used) 캐시 구현에 적합합니다.

use std::collections::{HashMap, LinkedList};

struct LRUCache<K, V> {
    capacity: usize,
    map: HashMap<K, V>,
    order: LinkedList<K>,
}

impl<K: Eq + std::hash::Hash + Clone, V> LRUCache<K, V> {
    fn new(capacity: usize) -> Self {
        Self {
            capacity,
            map: HashMap::new(),
            order: LinkedList::new(),
        }
    }

    fn get(&mut self, key: &K) -> Option<&V> {
        if self.map.contains_key(key) {
            self.order.retain(|k| k != key);
            self.order.push_back(key.clone());
            self.map.get(key)
        } else {
            None
        }
    }

    fn put(&mut self, key: K, value: V) {
        if self.map.contains_key(&key) {
            self.order.retain(|k| k != &key);
        } else if self.order.len() == self.capacity {
            if let Some(oldest) = self.order.pop_front() {
                self.map.remove(&oldest);
            }
        }
        self.order.push_back(key.clone());
        self.map.insert(key, value);
    }
}

---

5. 시간 복잡도 표

연산	시간 복잡도
push_back	O(1)
push_front	O(1)
pop_back	O(1)
pop_front	O(1)
front/back 접근	O(1)
특정 인덱스 get 접근	O(n)
append	O(1)

---

F&Q

Q1: LinkedList는 언제 사용해야 하나요?

• 양쪽 끝에서 빈번히 삽입/삭제가 필요할 때 적합합니다.
• 요소의 순서 유지가 중요하고, 중간 요소의 삽입/삭제가 빈번할 때 유용합니다.

Q2: LinkedList의 단점은 무엇인가요?

• 메모리가 연속적이지 않아 CPU 캐시 효율이 낮습니다.
• 랜덤 접근 성능이 좋지 않습니다(O(n)).

Q3: VecDeque와 LinkedList의 차이점은 무엇인가요?

• VecDeque는 배열 기반이므로 메모리 효율과 캐시 적중률이 높습니다.
• LinkedList는 중간 삽입/삭제에 더 적합합니다.

Q4: Rust에서 LinkedList를 사용하는 이유는 무엇인가요?

• Rust 자료구조 중 LinkedList는 특정한 삽입/삭제 작업에서 성능상의 이점을 제공합니다.

---

결론

LinkedList는 양방향 연결 리스트 구조를 제공하여 특정 시나리오에서 유용한 자료구조입니다. 중간 삽입/삭제가 빈번하거나 순서가 중요한 작업에 적합하며, LRU 캐시와 같은 활용 사례에서 강력한 도구로 사용될 수 있습니다. Rust의 다른 자료구조와 비교하여 LinkedList는 고유한 특성을 지니고 있으므로, 적절한 상황에서 최적의 성능을 발휘합니다.