Rust - Implementing custom algorithms on LinkedList: merges, splits, and more

Rust introduces interesting challenges and opportunities when working with data structures like the LinkedList<T>. While there are many built-in methods for convenience, implementing custom algorithms can enhance its functionality, especially when dealing with operations such as merges, splits, and more. In this article, we'll explore how to implement these custom algorithms in Rust, providing practical examples and explanations.

Understanding LinkedList<T>

Rust's LinkedList is part of the standard library and provides a doubly-linked list, which is a versatile and frequently used data structure. It is well suited for applications where you need to frequently add or remove items from the middle of the list.

Creating a LinkedList

Let’s start by creating a LinkedList<T>:

use std::collections::LinkedList;

fn main() {
    let mut list: LinkedList = LinkedList::new();
    list.push_back(1);
    list.push_back(2);
    list.push_back(3);
    println!("LinkedList: {:?}", list);
}

This snippet initializes a LinkedList of integers and pushes some elements into it.

Implementing a Merge Algorithm

Merging two linked lists can be an efficient operation if conducted properly. Here’s an example of how to merge two linked lists:

fn merge_lists(list1: &mut LinkedList, list2: &mut LinkedList) {
    list1.append(list2);
}

fn main() {
    let mut list1: LinkedList = [1, 3, 5].iter().cloned().collect();
    let mut list2: LinkedList = [2, 4, 6].iter().cloned().collect();
    merge_lists(&mut list1, &mut list2);
    println!("Merged list: {:?}", list1);
}

This code merges list2 into list1, effectively concatenating the lists. Each list remains sorted (if they were to have been individually sorted prior).

Implementing a Split Algorithm

Sometimes, it might be necessary to split a linked list into two separate lists.

fn split_list(list: &mut LinkedList, at: usize) -> LinkedList {
    let mut other = LinkedList::new();
    for i in 0..list.len() {
        if i >= at {
            other.push_back(list.pop_front().unwrap());
        } else {
            list.push_back(list.pop_front().unwrap());
        }
    }
    other
}

fn main() {
    let mut list: LinkedList = [1, 2, 3, 4, 5, 6].iter().cloned().collect();
    let split_list = split_list(&mut list, 3);
    println!("First half: {:?}", list);
    println!("Second half: {:?}", split_list);
}

In this code, we divide a LinkedList at the third index, demonstrating a straightforward way to split one list into two.

Custom Algorithm for Removing Duplicates

A common task in managing lists is the removal of duplicates. The following function achieves this:

fn remove_duplicates(list: &mut LinkedList) {
    let mut seen = LinkedList::new();
    let mut new_list = LinkedList::new();

    while let Some(val) = list.pop_front() {
        if !seen.contains(&val) {
            seen.push_back(val);
            new_list.push_back(val);
        }
    }

    *list = new_list;
}

fn main() {
    let mut list: LinkedList = [1, 2, 2, 3, 4, 4, 5].iter().cloned().collect();
    remove_duplicates(&mut list);
    println!("List without duplicates: {:?}", list);
}

This function iterates through a linked list, preserving only unique elements by leveraging a temporary 'seen' list to track which elements have been encountered.

Conclusion

While Rust’s LinkedList might seem daunting initially, implementing custom algorithms like merges, splits, and duplicate removal helps in mastering this versatile data structure. The examples provided in this article serve as a foundational introduction for embedding more complex logic into your linked list operations in Rust. Experiment and build on these frameworks to mold them to your application's needs!