Rust 双向链表 LinkedList 和安全删除元素的方法_rust linkedlist

一、LinkedList 基本用法

在Rust中，LinkedList 是标准库中 std::collections 模块提供的一个双向链表实现。这个双向链表在每个节点中都保存了其前一个和后一个节点的引用，允许在链表的任一端进行有效的添加和移除操作。

以下是一个简单的示例，演示了如何使用 LinkedList：

use std::collections::LinkedList;

fn main() {
    // 创建一个新的空双向链表
    let mut list = LinkedList::new();

    // 在链表的尾部添加一个元素
    list.push_back("rust".to_string());

    // 在链表的头部添加一个元素
    list.push_front("learn".to_string());

    // 访问链表的头部和尾部元素
    println!("Front of the list: {:?}", list.front());
    println!("Back of the list: {:?}", list.back());

    // 遍历链表并打印元素
    for element in &list {
        println!("{}", element);
    }

    // 使用迭代器移除链表中的元素
    for element in list.iter_mut() {
        if element.contains("ust") {
            *element = "replaced!".to_string();
        }
    }

    // 展示修改后的链表
    println!("List after modification:");
    for element in &list {
        println!("{}", element);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

注意：

1. 使用 push_back 在链表的尾部添加元素，使用 push_front 在链表的头部添加元素。
2. 使用 front 和 back 方法来获取链表头部和尾部的引用。
3. 可以直接迭代链表来访问它的每个元素。
4. iter_mut 方法返回一个可变迭代器，可以用来修改链表中的元素。

请记住，双向链表的性能特征意味着在链表的中间插入或删除元素可能比在数组的对应位置进行相同的操作更加低效，因为链表必须遍历节点直到找到所需的位置。然而，在链表的两端插入和删除则是非常高效的。

由于Rust的所有权模型，当您将元素添加到 LinkedList 中时，链表将取得该元素的所有权，这意味着您不再能直接访问原始对象（除非您从链表中移除了该对象或者以某种方式共享了所有权，比如使用引用计数）。这在设计链表和处理所有权转移时是需要特别注意的。

二、双向链表LinkedList删除中间的元素效率比 Vec 低吗？

是的，从双向链表（LinkedList）中删除中间的元素通常比从向量（Vec）中删除元素的效率低。这是由两者不同的数据结构和内存布局所决定的。

对于 Vec（向量）：

• 向量在内存中是一块连续的空间，这意味着访问任意元素（尤其是中间的元素）都非常快，因为你可以直接通过偏移来找到它。
• 删除一个元素（尤其是在中间）涉及移动该元素之后的所有元素来填补空位，这虽然有一定的开销，但由于内存是连续的，这个过程仍然相对高效。对于大型向量，这种开销可能会变得显著。

对于 LinkedList（双向链表）：

• 链表中的每个元素都单独存储在内存中，并通过指针链接在一起。这意味着访问链表中的任意元素（尤其是中间的元素）都需要从头部或尾部开始遍历，直到找到目标元素，这是一个 O(n) 操作。
• 删除链表中的一个元素不需要移动其他元素，你只需要调整相邻元素的指针来绕过被删除的元素。虽然指针的调整本身是常数时间的，但找到要删除的元素需要遍历，这使得整个操作变得低效，尤其是对于长链表。

总的来说，如果你经常需要随机访问或删除中间的元素，Vec 可能是更好的选择。另一方面，如果你主要进行的是在头部或尾部的插入和删除操作，那么 LinkedList 可能会提供更好的性能。在选择数据结构时，了解你的具体用例和数据访问模式是非常重要的。

三、双向链表LinkedList在迭代循环中删除元素的效率如何？

双向链表在迭代循环中删除元素的效率主要取决于删除操作的位置。

在双向链表的头部或尾部删除元素通常是一个相对高效的操作，因为这两个位置都保留了直接的指针引用，可以直接调整指针来移除元素，无需遍历整个链表。这种情况下，删除操作的时间复杂度是O(1)。

然而，如果在迭代循环中需要删除链表中间的某个元素，效率就会降低。因为你需要从链表的头部或尾部开始遍历，直到找到要删除的元素。这个遍历过程的时间复杂度是O(n)，其中n是链表的长度。一旦找到要删除的元素，你可以通过调整相邻节点的指针来将其从链表中移除，这个过程的时间复杂度是O(1)。但是，由于需要遍历链表来找到要删除的元素，所以整体删除操作的时间复杂度是O(n)。

另外，值得注意的是，在迭代循环中删除元素时需要谨慎处理迭代器和链表的状态。一种常见的做法是使用“安全”的删除方法，比如在迭代过程中收集要删除的元素的索引或引用，然后在循环结束后再进行实际的删除操作。这样可以避免在迭代过程中修改链表结构导致的迭代器失效问题。

总的来说，双向链表在迭代循环中删除元素的效率取决于删除位置。在头部或尾部删除是高效的，而在中间位置删除则需要遍历链表，效率较低。因此，在选择使用双向链表时，需要根据具体的应用场景和数据访问模式来权衡其性能特点。

四、从双向链表LinkedList删除元素的例子

下面是一个Rust程序示例，它创建了一个包含1到100之间自然数的双向链表，并在一个迭代循环中删除了所有的素数。

use std::collections::LinkedList;

// 判断一个数是否为素数
fn is_prime(n: u32) -> bool {
    if n <= 1 {
        return false;
    }
    if n <= 3 {
        return true;
    }
    if n % 2 == 0 || n % 3 == 0 {
        return false;
    }
    let mut i = 5;
    while i * i <= n {
        if n % i == 0 || n % (i + 2) == 0 {
            return false;
        }
        i += 6;
    }
    true
}

fn main() {
    // 创建一个包含1到100的双向链表
    let mut list: LinkedList<u32> = (1..=100).collect();

    // 使用迭代器删除素数
    list.retain(|&x| !is_prime(x));

    // 打印剩余的元素
    println!("Remaining elements after removing primes:");
    for num in &list {
        println!("{}", num);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

在这个程序中，我们首先定义了一个is_prime函数，用于判断一个数是否为素数。然后，我们使用LinkedList::retain方法，它接受一个闭包（closure），并保留闭包返回true的元素。在我们的例子中，闭包检查每个元素是否不是素数（!is_prime(x)），因此所有素数都会被移除。

最后，我们遍历并打印出链表中剩余的元素，这些元素都是非素数。

注意：retain 方法是原地操作，它直接修改链表，而不是创建一个新的链表。这通常比创建一个新链表并复制非删除元素更高效。

五、可否在 for 循环中删除双向链表LinkedList中特定的元素？

在Rust中，直接在for循环中删除双向链表（LinkedList）的元素是困难的，因为当你删除一个元素时，它会使当前迭代器失效。因此，你不能简单地遍历链表并在循环体中删除元素。相反，你应该使用LinkedList提供的安全方法来删除元素，比如retain（正如之前所示），或者显式地处理迭代器失效的问题。

如果你确实需要在for循环的上下文中删除元素（尽管这不是推荐的做法），你可以通过收集要删除的元素的索引或引用，然后在循环结束后再进行删除。但是，对于LinkedList来说，这通常不是必要的，因为retain方法提供了一种更简洁且安全的方式来删除元素。

然而，如果你坚持要在类似for循环的构造中删除元素，你可以使用filter或fold等迭代器方法，这些方法不会因删除元素而使迭代器失效。但请注意，这些方法实际上会创建一个新的链表，而不是在原地修改链表。

下面是一个使用filter方法的示例，它创建一个新链表，只包含原始链表中的非素数元素：

use std::collections::LinkedList;

// 判断一个数是否为素数
fn is_prime(n: &u32) -> bool {
    if n <= &1 {
        return false;
    }
    if n <= &3 {
        return true;
    }
    if n % 2 == 0 || n % 3 == 0 {
        return false;
    }
    let mut i = 5;
    while i * i <= *n {
        if n % i == 0 || n % (i + 2) == 0 {
            return false;
        }
        i += 6;
    }
    true
}

fn main() {
    // 创建一个包含1到100的双向链表
    let mut list: LinkedList<u32> = (1..=100).collect();

    // 使用filter方法创建一个新的链表，其中不包含素数
    let filtered_list: LinkedList<u32> = list.iter().filter(|x| !is_prime(x)).cloned().collect();

    // 打印剩余的元素
    println!("Remaining elements after removing primes:");
    for num in &filtered_list {
        println!("{}", num);
    }

    // 如果你确实需要修改原始链表，你可以将filtered_list重新赋值给list
    // 但请注意，这将替换原始链表，而不是在原地修改它
    // list = filtered_list;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

请注意，上面的代码实际上并没有修改原始的list链表，而是创建了一个新的filtered_list链表。如果你需要修改原始链表，你可以将filtered_list重新赋值给list（取消注释最后一行代码），但请记住这不是原地修改。

对于双向链表来说，原地删除元素通常是通过直接操作链表节点和指针来实现的，而这在Rust的LinkedList抽象中是隐藏的。因此，使用retain方法是更符合Rust惯用法的做法。

六、其他在循环体内删除LinkedList元素的方法

当然，如果你想要在类似 for 循环的构造中直接修改双向链表（即原地删除元素），你可以使用 LinkedList 提供的内部迭代器，比如 iter_mut()，它允许你在遍历的同时修改链表。然而，直接删除当前迭代器指向的元素仍然是不安全的，因为这会使迭代器失效。

一种解决方法是使用 LinkedList 的 cursors() 方法，它提供了对链表中元素的安全访问，并且允许你在遍历的同时删除元素。下面是一个使用 cursors() 方法在双向链表中删除素数的示例：

use std::collections::LinkedList;

// 判断一个数是否为素数
fn is_prime(n: &u32) -> bool {
    if *n <= 1 {
        return false;
    }
    for i in 2..=(n.sqrt() as u32) {
        if *n % i == 0 {
            return false;
        }
    }
    true
}

fn main() {
    // 创建一个包含1到100的双向链表
    let mut list: LinkedList<u32> = LinkedList::from(1..=100);

    // 使用cursors()方法删除素数
    let mut cur = list.cursors_front();
    while let Some(cursor) = cur.as_mut() {
        if is_prime(&cursor.current()) {
            cursor.remove();
        } else {
            cur.move_next();
        }
    }

    // 打印剩余的元素
    println!("Remaining elements after removing primes:");
    for num in &list {
        println!("{}", num);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

在这个例子中，我们使用 cursors_front() 方法来获取一个指向链表前端的游标（cursor）。然后，我们在循环中使用 as_mut() 方法来获取一个可变的游标引用，并检查当前游标指向的元素是否为素数。如果是素数，我们使用 remove() 方法删除它；否则，我们使用 move_next() 方法将游标移动到下一个元素。

请注意，cursors() 方法是在 Rust 1.61.0 版本中引入的，因此你需要使用至少这个版本的 Rust 来编译上面的代码。

这种方法的好处是它允许你在遍历链表的同时安全地删除元素，而无需担心迭代器失效的问题。然而，它仍然不是最高效的方法，因为删除操作需要遍历整个链表。对于大型链表来说，这可能会成为性能瓶颈。在这种情况下，使用其他数据结构（如哈希表或向量）可能更为合适。