Ch 11: LinkedList - 链表操作

1. 引言

LinkedList<T> 是 Rust 标准库提供的双向链表实现。相比 Vec 和 VecDeque，LinkedList 在任意位置插入和删除元素具有 O(1) 的时间复杂度，但随机访问的复杂度是 O(n)。本章将详细讲解 LinkedList 的核心方法。

2. LinkedList 基础

创建 LinkedList：

use std::collections::LinkedList;

fn main() {
    // 空链表
    let list: LinkedList<i32> = LinkedList::new();

    // 从迭代器创建
    let list = LinkedList::from_iter(0..5);
    println!("{:?}", list);  // [0, 1, 2, 3, 4]
}

3. push_back 和 push_front - 两端插入

push_back - 队尾插入：

use std::collections::LinkedList;

fn main() {
    let mut list = LinkedList::new();

    list.push_back(1);
    list.push_back(2);
    list.push_back(3);

    println!("{:?}", list);  // [1, 2, 3]
}

push_front - 队首插入：

use std::collections::LinkedList;

fn main() {
    let mut list = LinkedList::new();

    list.push_back(2);
    list.push_back(3);

    list.push_front(1);  // 插入到队首

    println!("{:?}", list);  // [1, 2, 3]
}

4. pop_front 和 pop_back - 两端移除

pop_front - 队首移除：

use std::collections::LinkedList;

fn main() {
    let mut list = LinkedList::from_iter(1..=3);

    let front = list.pop_front();
    println!("pop_front: {:?}", front);  // Some(1)
    println!("{:?}", list);              // [2, 3]
}

pop_back - 队尾移除：

use std::collections::LinkedList;

fn main() {
    let mut list = LinkedList::from_iter(1..=3);

    let back = list.pop_back();
    println!("pop_back: {:?}", back);  // Some(3)
    println!("{:?}", list);           // [1, 2]
}

5. front 和 back - 查看端点

use std::collections::LinkedList;

fn main() {
    let list = LinkedList::from_iter(1..=3);

    println!("front: {:?}", list.front());  // Some(&1)
    println!("back: {:?}", list.back());    // Some(&3)
}

6. splice - 区间替换

splice 用另一个迭代器替换链表中指定区间的元素：

方法签名：

pub fn splice<R, I>(&mut self, range: R, replace_with: I) -> Splice<'_, I::IntoIter>
where
    R: RangeBounds<usize>,
    I: IntoIterator<Item = T>,

示例：

use std::collections::LinkedList;

fn main() {
    let mut list: LinkedList<i32> = LinkedList::from_iter(1..=5);

    // 创建一个临时链表用于替换
    let replacement = LinkedList::from_iter(10..=12);

    // 替换索引 [1, 4) 的元素
    let removed: LinkedList<_> = list.splice(1..4, replacement).collect();

    println!("removed: {:?}", removed);  // [2, 3, 4]
    println!("list: {:?}", list);        // [1, 10, 11, 12, 5]
}

使用空迭代器删除元素：

use std::collections::LinkedList;

fn main() {
    let mut list: LinkedList<i32> = LinkedList::from_iter(1..=5);

    // 用空迭代器替换，相当于删除
    list.splice(1..4, LinkedList::new());

    println!("{:?}", list);  // [1, 5]
}

7. append 和 prepend - 合并链表

append - 队尾合并：

use std::collections::LinkedList;

fn main() {
    let mut list1: LinkedList<i32> = LinkedList::from_iter(1..=3);
    let mut list2: LinkedList<i32> = LinkedList::from_iter(4..=6);

    list1.append(&mut list2);

    println!("list1: {:?}", list1);  // [1, 2, 3, 4, 5, 6]
    println!("list2: {:?}", list2);  // []
}

prepend - 队首合并：

use std::collections::LinkedList;

fn main() {
    let mut list1: LinkedList<i32> = LinkedList::from_iter(4..=6);
    let mut list2: LinkedList<i32> = LinkedList::from_iter(1..=3);

    list1.prepend(&mut list2);

    println!("list1: {:?}", list1);  // [1, 2, 3, 4, 5, 6]
    println!("list2: {:?}", list2);  // []
}

8. push_after 和 push_before - 节点插入

这两个方法需要使用迭代器的 cursor：

cursor_after：

use std::collections::LinkedList;

fn main() {
    let mut list: LinkedList<i32> = LinkedList::from_iter(1..=3);

    // 获取迭代器
    let mut iter = list.iter();
    iter.next();  // 移动到第二个元素

    // 注意：LinkedList 的 iter 不支持 push_after
    // 这是一个简化示例
}

注意： LinkedList 在标准库中不提供直接操作任意节点的公共 API，需要通过 cursor 或 Cursor 类型。

9. LinkedList 的迭代器

iter - 不可变迭代：

use std::collections::LinkedList;

fn main() {
    let list = LinkedList::from_iter(1..=3);

    for item in &list {
        println!("{}", item);
    }
}

iter_mut - 可变迭代：

use std::collections::LinkedList;

fn main() {
    let mut list: LinkedList<i32> = LinkedList::from_iter(1..=3);

    for item in list.iter_mut() {
        *item *= 2;
    }

    println!("{:?}", list);  // [2, 4, 6]
}

into_iter - 所有权迭代：

use std::collections::LinkedList;

fn main() {
    let list = LinkedList::from_iter(1..=3);

    // 获取所有权
    let collected: Vec<_> = list.into_iter().collect();

    println!("{:?}", collected);  // [1, 2, 3]
}

10. 实战示例：LRU Cache 简化版

use std::collections::LinkedList;

struct LRUCache<K, V> {
    capacity: usize,
    items: LinkedList<(K, V)>,
}

impl<K, V> LRUCache<K, V>
where
    K: PartialEq,
{
    fn new(capacity: usize) -> Self {
        LRUCache {
            capacity,
            items: LinkedList::new(),
        }
    }

    fn get(&mut self, key: &K) -> Option<&V> {
        // 找到并移动到队首
        let mut pos = 0;
        let mut found = false;

        for item in &self.items {
            if &item.0 == key {
                found = true;
                break;
            }
            pos += 1;
        }

        if found {
            // 移除当前位置
            let mut new_list = LinkedList::new();
            let mut current = 0;

            for item in self.items.drain(..) {
                if current == pos {
                    new_list.push_front(item);
                } else {
                    if current < pos {
                        new_list.push_back(item);
                    } else {
                        new_list.push_back(item);
                    }
                }
                current += 1;
            }

            self.items = new_list;
            self.items.front().map(|(_, v)| v)
        } else {
            None
        }
    }

    fn put(&mut self, key: K, value: V) {
        // 检查是否已存在
        let mut found = false;
        let mut pos = 0;

        for item in &self.items {
            if item.0 == key {
                found = true;
                break;
            }
            pos += 1;
        }

        if found {
            // 移除旧值
            let mut new_list = LinkedList::new();
            let mut current = 0;

            for item in self.items.drain(..) {
                if current != pos {
                    new_list.push_back(item);
                }
                current += 1;
            }
            self.items = new_list;
        } else if self.items.len() >= self.capacity {
            // 移除最老的
            self.items.pop_back();
        }

        // 添加到队首
        self.items.push_front((key, value));
    }
}

fn main() {
    let mut cache = LRUCache::new(3);

    cache.put("a", 1);
    cache.put("b", 2);
    cache.put("c", 3);

    println!("{:?}", cache.get(&"a"));  // Some(&1)

    cache.put("d", 4);  // 移除 "b"

    println!("{:?}", cache.get(&"b"));  // None
}

11. LinkedList vs Vec vs VecDeque

操作	LinkedList	Vec	VecDeque
随机访问	O(n)	O(1)	O(1)
两端插入	O(1)	O(1) 均摊	O(1)
两端删除	O(1)	O(1)	O(1)
中间插入	O(1)*	O(n)	O(n)
中间删除	O(1)*	O(n)	O(n)
内存开销	较高	较低	较低

*需要先找到位置

12. 需要注意的点

1. LinkedList 的随机访问是 O(n)：不适合需要频繁随机访问的场景。

2. splice 的 O(1) 插入：只要有迭代器位置，插入和删除是 O(1)。

3. LinkedList 不实现 Index：不能使用 list[0] 语法。

4. LinkedList 是 !Sync：不能跨线程共享。

5. LinkedList 的迭代器不能 push_after/push_before：标准库没有提供在迭代时修改链表的公共 API。

13. 总结

LinkedList 是 Rust 中的双向链表实现：

方法	作用	复杂度
push_back	队尾插入	O(1)
push_front	队首插入	O(1)
pop_back	队尾移除	O(1)
pop_front	队首移除	O(1)
splice	区间替换	O(1)*
append	合并链表	O(1)
prepend	队首合并	O(1)
iter/iter_mut	迭代器	O(n)

LinkedList 适合需要频繁在任意位置插入/删除的场景，但随机访问性能较差。