linked list in rust

In Rust, a typical implementation of linked list involves creating a custom data structure to represent each node of the list, and using pointers to point to the next node in the list.

Here's a simple implementation of a singly linked list:

main.rs
struct Node<T> {
    data: T,
    next: Option<Box<Node<T>>>,
}

impl<T> Node<T> {
    fn new(data: T, next: Option<Box<Node<T>>>) -> Node<T> {
        Node { data, next }
    }
}


struct LinkedList<T> {
    head: Option<Box<Node<T>>>,
}

impl<T> LinkedList<T> {
    fn new() -> LinkedList<T> {
        LinkedList { head: None }
    }

    fn push(&mut self, data: T) {
        let new_node = Node::new(data, self.head.take());
        self.head = Some(Box::new(new_node));
    }

    fn pop(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            self.head = node.next;
            node.data
        })
    }
}
633 chars
34 lines

Here, the Node struct is used to represent each element of the list, and contains the data value as well as an optional pointer to the next node. The LinkedList struct maintains a pointer to the head of the list, and provides methods to push and pop data values from the list.

Note that the use of Box is necessary to ensure that each node is allocated on the heap, rather than on the stack, as their size is not known at compile time. Additionally, the take() method is used to take ownership of the Option pointer contained in the current head of the list, leaving it with a value of None. This is necessary to prevent the head reference from taking ownership of the next pointer, which would cause a recursive ownership cycle.

There are other ways to implement linked lists in Rust, depending on the specific requirements and performance characteristics of the list.