如何在Rust的std::collections::LinkedList中向指定索引插入元素

Rust标准库的LinkedList没有内置按索引插入元素的方法，不过我们可以基于它的现有API实现这个功能，下面是两种实用的方案：

方案1：利用split_off和append实现 #

这种方式通过拆分链表再合并的方式完成插入，代码简洁且符合LinkedList的特性：

use std::collections::LinkedList;

fn insert_at<T>(list: &mut LinkedList<T>, index: usize, value: T) {
    // 如果索引超出链表长度，直接追加到末尾
    if index >= list.len() {
        list.push_back(value);
        return;
    }

    // 从索引位置拆分链表，前半部分保留在原链表，后半部分存入suffix
    let mut suffix = list.split_off(index);
    // 将元素插入到原链表末尾（即拆分前的索引位置）
    list.push_back(value);
    // 把后半部分链表合并回去
    list.append(&mut suffix);
}

fn main() {
    let mut list = LinkedList::new();
    list.push_back("a".to_string());
    list.push_back("c".to_string());
    list.push_back("d".to_string());

    // 在索引1的位置插入"b"
    insert_at(&mut list, 1, "b".to_string());

    // 遍历验证结果
    for elem in list {
        println!("{}", elem);
    }
}

原理说明 #

• split_off(index)会遍历到链表的第index个节点，将链表拆分为前半部分（原链表保留）和后半部分（返回值），时间复杂度为O(n)
• 插入元素后合并后半部分，相当于把元素放到了原本的index位置
• 自动处理索引超出范围的情况，直接追加到链表末尾

方案2：使用迭代器和insert_before #

如果你更倾向于通过迭代定位节点的方式实现，也可以用以下代码：

use std::collections::LinkedList;

fn insert_at<T>(list: &mut LinkedList<T>, index: usize, value: T) {
    let mut iter = list.iter_mut();
    // 遍历到目标索引的对应位置
    for _ in 0..index {
        // 如果中途遍历完链表，说明索引超出范围，直接追加到末尾
        if iter.next().is_none() {
            list.push_back(value);
            return;
        }
    }

    // 定位到目标节点后，在它前面插入新元素
    match iter.next() {
        Some(node) => list.insert_before(node, value),
        // 索引等于链表长度时，追加到末尾
        None => list.push_back(value),
    }
}

原理说明 #

• 通过iter_mut()获取可变迭代器，遍历到目标索引对应的节点
• 使用insert_before在目标节点前插入新元素，若遍历到链表末尾则直接追加

两种方案的时间复杂度都是O(n)，因为LinkedList是双向链表，无法直接随机访问，必须遍历到目标位置才能完成插入操作。

内容的提问来源于stack exchange，提问作者Fanisus