Rust Program: Remove duplicates from singly linked list

Last update on December 21 2024 10:21:42 (UTC/GMT +8 hours)

Write a Rust program to remove duplicates from an unsorted singly linked list.

Sample Solution:

Rust Code:

use std::collections::HashSet;

// Define the singly linked list node
pub struct Node {
    val: T,
    next: Option>>,
}

// Define the linked list
pub struct LinkedList {
    head: Option>>,
}

impl LinkedList {
    // Function to remove duplicates from the linked list
    pub fn remove_dupes(&mut self) {
        // Create a HashSet to store unique elements
        let mut set = HashSet::new();
        // Initialize a mutable reference to the head of the linked list
        let mut current = &mut self.head;

        // Iterate through the linked list
        while let Some(mut node) = current.take() {
            // If the current node's value is found in the HashSet, remove it
            if set.contains(&node.val) {
                *current = node.next.take();
            } else {
                // Insert the current node's value into the HashSet
                set.insert(node.val.clone());
                // Re-insert the current node back into the linked list
                *current = Some(node);
                // Move the reference to the next node
                current = &mut current.as_mut().unwrap().next;
            }
        }
    }
}

fn main() {
    // Example usage
    let mut list = LinkedList {
        head: Some(Box::new(Node {
            val: 1,
            next: Some(Box::new(Node {
                val: 2,
                next: Some(Box::new(Node {
                    val: 1,
                    next: None,
                })),
            })),
        })),
    };
    // Remove duplicates from the list
    list.remove_dupes();

    // Print the modified list
    let mut current = &list.head;
    while let Some(node) = current {
        println!("{}", node.val);
        current = &node.next;
    }
}

Output:

1
2

Explanation:

Here is a brief explanation of the above Rust code:

Node and LinkedList Structs:

The Node<T> struct represents a node in a singly linked list, containing a value of type T and an optional pointer to the next node.
The LinkedList<T> struct represents the linked list itself, containing an optional pointer to the head node.

remove_dupes Method:

This method belongs to the "LinkedList" struct and is used to remove duplicate elements from the linked list.
It utilizes a HashSet to keep track of unique elements encountered so far.
It iterates through the linked list using mutable references and removes duplicate nodes by updating pointers accordingly.

Main Function:

In the main function, an example linked list is created with some duplicate elements.
The "remove_dupes()" method is called to remove duplicates from the list.
Finally, the modified list is printed to verify that duplicates have been removed.

Explanation of Usage:

The "remove_dupes()" method efficiently removes duplicates from the linked list while preserving the order of elements.
It achieves this by using a HashSet to track unique elements and updating the linked list in-place.
This approach has a time complexity of O(n), where n is the number of elements in the linked list.

Rust Code Editor:

Previous: Rust Program: Merge sorted singly linked lists.