Algorithmen und Datenstrukturen in Rust: Ein praktischer Leitfaden

Einleitung: Warum Rust für Algorithmen?

Rust ist eine moderne Systemprogrammiersprache, die die hohe Leistung von C/C++ mit Speichersicherheit kombiniert. Für das Erlernen von Algorithmen und Datenstrukturen ist Rust besonders gut geeignet, weil:

• Besitzkontrolle (ownership) zwingt dazu, die Speicherverwaltung explizit zu durchdenken
• Sicherheit – der Compiler verhindert viele Laufzeitfehler
• Geschwindigkeit – Rust wird in Maschinencode kompiliert, was für leistungsstarke Algorithmen wichtig ist

In diesem Artikel analysieren wir die Implementierung von vier grundlegenden Strukturen und Algorithmen in Rust mit praktischen Codebeispielen.

1. Verkettete Liste (Linked List)

Eine der klassischen Datenstrukturen. In Rust erfordert ihre Implementierung die Verwendung von Box zur Speicherzuweisung auf dem Heap und Option zur Darstellung des Fehlens eines Knotens.

Implementierung einer einfach verketteten Liste

// Definiert den Listenknoten#[derive(Debug)]struct Node<T> {    value: T,    next: Option<Box<Node<T>>>,}

// Die Liste selbst#[derive(Debug)]struct LinkedList<T> {    head: Option<Box<Node<T>>>,}

impl<T> LinkedList<T> {    // Erstellt eine leere Liste    fn new() -> Self {        LinkedList { head: None }    }

    // Fügt ein Element am Anfang hinzu    fn push_front(&mut self, value: T) {        let new_node = Box::new(Node {            value,            next: self.head.take(),        });        self.head = Some(new_node);    }

    // Entfernt ein Element vom Anfang    fn pop_front(&mut self) -> Option<T> {        self.head.take().map(|node| {            self.head = node.next;            node.value        })    }}

fn main() {    let mut list = LinkedList::new();    list.push_front(10);    list.push_front(20);    list.push_front(30);    println!("{:?}", list); // LinkedList { head: Some(Node { value: 30, next: ... }) }        let popped = list.pop_front();    println!("Entfernt: {:?}", popped); // Entfernt: Some(30)    println!("Liste jetzt: {:?}", list);}

Was hier passiert:

• Box<Node> – ein Zeiger auf einen Knoten auf dem Heap
• Option – entweder gibt es einen Knoten (Some) oder nicht (None)
• take() – entnimmt den Wert aus Option und hinterlässt None

2. Binärer Suchbaum (Binary Search Tree)

Ein Baum ist eine hierarchische Struktur. In einem binären Suchbaum hat jeder Knoten einen linken und einen rechten Nachfolger, wobei der linke kleiner als die Wurzel und der rechte größer ist.

Implementierung eines BST

use std::cmp::Ordering;

#[derive(Debug)]struct TreeNode<T> {    value: T,    left: Option<Box<TreeNode<T>>>,    right: Option<Box<TreeNode<T>>>,}

#[derive(Debug)]struct BinarySearchTree<T> {    root: Option<Box<TreeNode<T>>>,}

impl<T: Ord> BinarySearchTree<T> {    fn new() -> Self {        BinarySearchTree { root: None }    }

    // Einfügen eines Elements    fn insert(&mut self, value: T) {        let mut current = &mut self.root;        while let Some(node) = current {            match value.cmp(&node.value) {                Ordering::Less => current = &mut node.left,                Ordering::Greater => current = &mut node.right,                Ordering::Equal => return, // Duplikate ignorieren wir            }        }        *current = Some(Box::new(TreeNode {            value,            left: None,            right: None,        }));    }

    // Suche nach einem Element    fn contains(&self, value: &T) -> bool {        let mut current = &self.root;        while let