Singly-Linked List in Rust

Question

I've been trying to teach myself some Rust lately and wanted to practice a bit by implementing a simple linked list. I took some inspiration from the Rust library's linked list and tried to replicate the parts I already understood. Also I decided to make it singly-linked for now.

struct Node<T> {
    element: T,
    next: Option<Box<Node<T>>>,
}

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

    fn append(&mut self, element: Box<Node<T>>) {
        self.next = Some(element);
    }
}

pub struct LinkedList<T> {
    head: Option<Box<Node<T>>>,
    tail: Option<Box<Node<T>>>,
    len: u32,
}

impl<T> LinkedList<T> {
    pub fn new() -> Self {
        head: None,
        tail: None,
        len: 0,
    }

    pub fn push(&mut self, element: T) {
        let node: Box<Node<T>> = Box::new(Node::new(element));

        match self.tail {
            None => self.head = Some(node),
            Some(mut ref tail) => tail.append(node),
        }
        self.tail = Some(node);
        self.len += 1;
    }

    pub fn pop(&mut self) -> Option<T> {
        //not implemented
    }

    pub fn get(&self, index: u32) -> Option<T> {
        //not implemented
    }
}

This is what I've got so far; from what I understand, the problem with this code is that the Box can not have more than one reference to it in order to preserve memory safety.

So when I set the list head to node in

None => self.head = Some(node),

I can't then go ahead and set

self.tail = Some(node);

later, am I correct so far in my understanding? What would be the correct way to do this? Do I have to use Shared like in the library or is there a way in which the Box or some other type can be utilized?

obligatory reference (Learning Rust With Entirely Too Many Linked Lists) — ljedrz
– ljedrz, Commented Jan 14, 2017 at 18:03
Note that the traditional singly-linked (Cons List) does not memorize the tail. It's a way to allow appending in O(1), but is not necessary. — Matthieu M.
– Matthieu M., Commented Jan 14, 2017 at 18:15
@Oliver can you please accept Ijedrzs answer if it answers your question? Else please state what's missing. — hellow
– hellow, Commented Nov 30, 2018 at 9:57

Community · Accepted Answer · 2017-05-23 12:24:34Z

5

Your issue is that you are attempting to use a value (node) after having moved it; since Box<Node<T>> does not implement Copy, when you use it in the match expression:

match self.tail {
    None => self.head = Some(node),
    Some(ref mut tail) => tail.append(node),
}

node is moved either to self.head or to self.tail and can no longer be used later. Other than reading the obligatory Learning Rust With Entirely Too Many Linked Lists to see the different ways in which you can implement linked lists in Rust, I suggest that you first do some more research in the field of Rust's basic concepts, especially:

edited May 23, 2017 at 12:24

CommunityBot

11 silver badge

answered Jan 14, 2017 at 18:14

ljedrz

22.6k5 gold badges77 silver badges110 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

debuti · Accepted Answer · 2019-08-23 08:50:34Z

3

You can go with something simpler than that, only using your nodes

use std::fmt;

struct Payload {
  id: i32,
  value: i32,
}

impl fmt::Display for Payload {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "({}, {})", self.id, self.value)
    }
}

struct Node<T> {
    element: T,
    next: Option<Box<Node<T>>>,
}

impl<T> Node<T> where T: std::fmt::Display{
    fn new(element: T) -> Self {
        Node {
            element: element,
            next: None,
        }
    }

    fn append(&mut self, element: T) {
        match &mut self.next {
            None => {let n = Node {
                        element: element,
                        next: None,
                    };
                    self.next = Some(Box::new(n));
            },
            Some(ref mut x) => x.append(element),
        }
    }

    fn list(& self) {
        println!("{}", self.element);
        match &self.next {
            None => {},
            Some(x) => x.list(),
        }
    }
}

fn main(){
  let mut h = Node::new(Payload {id:1, value:1});
  h.append(Payload {id:2, value:2});
  h.append(Payload {id:3, value:3});
  h.append(Payload {id:4, value:4});
  h.append(Payload {id:5, value:5});
  h.list();
  h.append(Payload {id:6, value:6});
  h.list();
}

answered Aug 23, 2019 at 8:50

debuti

6952 gold badges12 silver badges21 bronze badges

2 Comments

prehistoricpenguin Over a year ago

So it's a recursive append, it's non-performant

Vignesh Over a year ago

@prehistoricpenguin will it be better if we just iterate the elements and do it, instead of recursion?

Collectives™ on Stack Overflow

Singly-Linked List in Rust

2 Answers 2

Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related