Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Singly-Linked List in Rust

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?

like image 432
Oliver Avatar asked Jan 14 '17 17:01

Oliver


People also ask

What is a linked list Rust?

The LinkedList allows pushing and popping elements at either end in constant time. A LinkedList with a known list of items can be initialized from an array: use std::collections::LinkedList; let list = LinkedList::from([1, 2, 3]);

Does Rust have linked list?

It is difficult to implement Linked List in Rust as what is allowed in most languages is simply not allowed in Rust, While it may seem to be a little difficult but the Rust compiler also at the same time makes sure that your code is memory safe.

What is a singly linked list?

A singly linked list is a type of linked list that is unidirectional, that is, it can be traversed in only one direction from head to the last node (tail). Each element in a linked list is called a node. A single node contains data and a pointer to the next node which helps in maintaining the structure of the list.

What is singly linked list algorithm?

In its most simplest form, a singly linked list is a linked list where each node is an object that stores a reference to an element and a reference, called next, to another node. Note that a node is defined in terms of itself, which is called self-referential structure.


1 Answers

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:

  • Ownership
  • References and Borrowing
  • What are move semantics?
like image 143
ljedrz Avatar answered Nov 15 '22 09:11

ljedrz