CODEWITHSUNDEEP
linked-listrust
GoldenChrysanthem
GoldenChrysanthem

Reputation: 197

Is it possible to pop a certain element off the standard library's LinkedList?

Is it possible to pop a certain element off the standard library's LinkedList? Could it be possible to reorder a linked list so the selected element appears at the end and then you pop it off?

Upvotes: 2

Views: 68

Answers (1)

Shepmaster
Shepmaster

Reputation: 431469

Sure. It requires O(n) time though, so it's not a good idea:

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]
}

Use split_off to create two lists. This takes O(n) time to walk through the list to the requested node. This also panics if the index is invalid.

You can then either take the tail of the first list (pop_back) or the head of the second list (pop_front). You can then splice the lists back together with append. These all work on O(1) time.

Upvotes: 3

Related Questions