Do not keep track of length

Simple Linked List
Simple Linked List in Rust
use std::iter::FromIterator;

type Link<T> = Option<Box<Node<T>>>;

pub struct SimpleLinkedList<T> {
    head: Link<T>,
}
struct Node<T> {
    data: T,
    next: Link<T>,
}

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

impl<T> SimpleLinkedList<T> {
    pub fn new() -> Self {
        Self { head: None }
    }

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

    pub fn len(&self) -> usize {
        let mut current_node = &self.head;
        let mut size = 0;
        while let Some(x) = current_node {
            size += 1;
            current_node = &x.next;
        }
        size
    }

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

    pub fn pop(&mut self) -> Option<T> {
        if self.head.is_some() {
            let head_node = self.head.take().unwrap();
            self.head = head_node.next;
            Some(head_node.data)
        } else {
            None
        }
    }

    pub fn peek(&self) -> Option<&T> {
        self.head.as_ref().map(|head| &(head.data))
    }

    pub fn rev(self) -> SimpleLinkedList<T> {
        let mut list = SimpleLinkedList::new();
        let mut cur_node = self.head;
        while let Some(node) = cur_node {
            list.push(node.data);
            cur_node = node.next;
        }
        list
    }
}

impl<T> FromIterator<T> for SimpleLinkedList<T> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let mut list = SimpleLinkedList::new();
        for item in iter {
            list.push(item);
        }
        list
    }
}

impl<T> Into<Vec<T>> for SimpleLinkedList<T> {
    fn into(self) -> Vec<T> {
        let mut the_vec: Vec<T> = vec![];
        let mut cur_node = self.rev().head;
        while let Some(node) = cur_node {
            the_vec.push(node.data);
            cur_node = node.next;
        }
        the_vec
    }
}

This approach starts by defining a Link type which will be used for the head field of SimpleLinkedList and the next field of Node. Defining Link<T> as an Option<Box<Node<T>>> in one place helps to keep the code DRY.

The is_empty() method is implemented by returning the result of the is_none() method on the head.

The len() method is implemented by iterating all of the nodes while mutating a counter variable. When the iteration is done, the value of the counter variable is returned.

25th Aug 2024 · Found it useful?