如何在稳定版Rust中移除LinkedList任意位置的元素

仅使用稳定版Rust完全可以移除LinkedList中任意位置的元素，不需要依赖尚未稳定的remove方法，通过标准库现有稳定API即可实现，两种常见移除场景的实现方式如下：

按值移除元素 #

稳定版标准库已经提供了现成的对应API，无需手写遍历逻辑：

• 移除第一个匹配指定值的元素：使用稳定的LinkedList::remove_first_match方法，传入判断匹配规则的闭包即可，方法会返回被移除的元素（不存在匹配项时返回None）。
  示例代码：

  use std::collections::LinkedList;
  
  fn main() {
      let mut list = LinkedList::from([1, 2, 3, 2, 4]);
      // 移除第一个值为2的元素
      let removed_val = list.remove_first_match(|&item| item == 2);
      assert_eq!(removed_val, Some(2));
      assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![1, 3, 2, 4]);
  }
  

• 移除所有匹配指定值的元素：使用稳定的LinkedList::retain方法，传入判断元素是否需要保留的闭包，所有不满足保留条件的元素会被直接移除。
  示例代码：

  use std::collections::LinkedList;
  
  fn main() {
      let mut list = LinkedList::from([1, 2, 3, 2, 4]);
      // 移除所有值为2的元素
      list.retain(|&item| item != 2);
      assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![1, 3, 4]);
  }
  

按索引移除元素 #

目前稳定版标准库没有直接提供按索引移除的原生API，但可以通过split_off、pop_front、append三个稳定方法组合实现，时间复杂度和官方未稳定的remove方法完全一致，没有额外性能损耗，实现逻辑如下：

1. 先校验索引合法性，索引大于等于链表长度时属于越界，直接返回None
2. 调用split_off(index)将链表从目标索引位置切为两段：前半段存储索引0到index-1的元素，后半段存储从index开始到末尾的元素
3. 对后半段链表调用pop_front()，取出的元素就是目标索引位置需要移除的值
4. 调用append将后半段剩余的元素追加回前半段链表，完成移除操作

示例代码：

use std::collections::LinkedList;

fn remove_index<T>(list: &mut LinkedList<T>, index: usize) -> Option<T> {
    if index >= list.len() {
        return None;
    }
    let mut right_part = list.split_off(index);
    let removed_val = right_part.pop_front();
    list.append(&mut right_part);
    removed_val
}

fn main() {
    let mut list = LinkedList::from([1, 2, 3, 4, 5]);
    let removed_val = remove_index(&mut list, 2);
    assert_eq!(removed_val, Some(3));
    assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![1, 2, 4, 5]);
}

注意：LinkedList本身的随机访问时间复杂度为O(n)，不管是官方未稳定的按索引移除方法，还是上面给出的实现，都需要从链表头部逐一遍历到目标位置。如果你的业务场景存在大量按索引操作元素的需求，LinkedList不是最优选择，优先考虑Vec等支持O(1)随机访问的集合类型。

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