linked-list - 是否可以从标准库的 LinkedList 中弹出某个元素？

Question

是否可以从标准库的 LinkedList 中弹出某个元素？ ？是否可以对链表重新排序，使所选元素出现在末尾，然后将其弹出？

Answer 1

当然。不过它需要 O(n) 的时间，所以这不是一个好的主意:

use std::collections::LinkedList;

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

    let mut tail = list.split_off(5);

    let x = list.pop_back();
    let y = tail.pop_front();

    list.append(&mut tail);

    println!("({:?}, {:?})", x, y); // (Some(5), Some(6))
    println!("{:?}", list);         // [1, 2, 3, 4, 7, 8, 9]
}

使用split_off创建两个列表。这需要 O(n) 时间遍历列表到请求的节点。如果索引无效，这也会出现 panic 。

然后您可以获取第一个列表的尾部 ( pop_back ) 或第二个列表的头部 ( pop_front )。然后您可以将列表与 append 拼接在一起.这些都是 O(1) 时间的工作。