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) 时间。