Rust Program to Implement LinkedList

0

Implement LinkedList

Rust Programming Language


Implement LinkedList


Problem


Rust program that implements a singly linked list.

Input


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

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

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

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

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

    fn is_empty(&self) -> bool {
        self.head.is_none()
    }

    fn size(&self) -> usize {
        self.size
    }

    fn print(&self) {
        let mut curr = &self.head;
        while let Some(node) = curr {
            print!("{} -> ", node.data);
            curr = &node.next;
        }
        println!("None");
    }
}

fn main() {
    let mut list = LinkedList::new();

    list.push(1);
    list.push(2);
    list.push(3);

    println!("List size: {}", list.size());
    list.print();

    list.pop();
    list.pop();

    println!("List size: {}", list.size());
    list.print();
}{codeBox}

Output


List size: 3
3 -> 2 -> 1 -> None
List size: 1
1 -> None{codeBox}


Explanation


In this program, we define a generic LinkedList struct that contains a head Node pointer and a size. We then define several methods on the LinkedList struct:

  • new(): creates a new, empty linked list.
  • push(): adds a new node with the given data to the head of the linked list.
  • pop(): removes and returns the node at the head of the linked list, or returns None if the list is empty.
  • is_empty(): returns true if the linked list is empty, false otherwise.
  • size(): returns the number of nodes in the linked list.
  • print(): prints the contents of the linked list to the console.

We also define a generic Node struct that contains some data and a pointer to the next node in the list.

In the main() function, we create a new linked list, push three integers onto the list, print the list's size and contents to the console, and then pop two nodes from the list and print the updated size and contents to the console.

Note that in the pop() method, we use the take() method to move the head node out of the linked list temporarily, and then replace it with the next node in the list using the map() method. This allows us to take ownership of the head node without needing to clone it, and also handles the case where the linked list is empty.

This is because we first push three integers, 1, 2, and 3, onto the linked list, and then print the size of the list and its contents to the console. We then pop two nodes from the list, and again print the updated size and contents to the console. Since the linked list is a last-in, first-out data structure, the nodes are popped from the list in reverse order from which they were pushed: 3 first, followed by 2.



Tags:

Post a Comment