CODEWITHSUNDEEP
data-structuresrustsingly-linked-listlifetime
uwu
uwu

Reputation: 1738

Can I traverse a singly linked list without owner move or unsafe?

A singly linked list can simply create from tail. But can't from head, I tried many time, code here: https://gist.github.com/tioover/8d7585105c06e01678a8.

In fact, I want search then delete a node in linked list. but I can't traversal linked list with mutable borrow pointer: https://gist.github.com/tioover/526715ed05342ef5b4f1. I tried many time too.

Upvotes: 0

Views: 423

Answers (1)

Shepmaster
Shepmaster

Reputation: 431489

Here's some code from an answer to a similar question. It shows a way of having a list that you can add to the beginning and the end, and the middle for good measure.

#[derive(Debug)]
struct Node<T> {
    v: T,
    next: Option<Box<Node<T>>>,
}

impl<T> Node<T> {
    fn new(v: T) -> Node<T> { Node { v: v, next: None } }

    fn push_front(self, head: T) -> Node<T> {
        Node {
            v: head,
            next: Some(Box::new(self)),
        }
    }

    fn push_back(&mut self, tail: T) {
        match self.next {
            Some(ref mut next) => next.push_back(tail), 
            None => self.next = Some(Box::new(Node::new(tail))),
        }
    }

    fn push_after(&mut self, v: T) {
        let old_next = self.next.take();

        let new_next = Node {
            v: v,
            next: old_next,
        };

        self.next = Some(Box::new(new_next));
    }
}

fn main() {
    let mut n = Node::new(2u8);
    n.push_back(3u8);
    let mut n = n.push_front(0u8);
    n.push_after(1u8);

    println!("{:?}", n);
}

The important thing is that when we add to the head, we consume the old head by taking it as self. That allows us to move it into a Box which will be the follower of the new head. Removing an item is a straight-forward extension of this example, but you'll need to look forward a bit and handle more edge cases (like what to do if there isn't a second successor).

Upvotes: 2

Related Questions