Simple Linked List

Ringkasan Tantangan

Write a simple linked list implementation that uses Elements and a List.

Introduction

You work for a music streaming company.

You’ve been tasked with creating a playlist feature for your music player application.

Instructions

Write a prototype of the music player application.

For the prototype, each song will simply be represented by a number. Given a range of numbers (the song IDs), create a singly linked list.

Given a singly linked list, you should be able to reverse the list to play the songs in the opposite order.

The linked list is a fundamental data structure in computer science, often used in the implementation of other data structures.

The simplest kind of linked list is a **singly** linked list.
That means that each element (or "node") contains data, along with something that points to the next node in the list.

If you want to dig deeper into linked lists, check out [this article][intro-linked-list] that explains it using nice drawings.

[intro-linked-list]: https://medium.com/basecs/whats-a-linked-list-anyway-part-1-d8b7e6508b9d

Dig Deeper

Keep track of length

use std::iter::FromIterator;

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

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

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

    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    pub fn len(&self) -> usize {
        self.len
    }

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

        self.head = Some(new_node);
        self.len += 1;
    }

    pub fn pop(&mut self) -> Option<T> {
        if self.len == 0 {
            return None;
        }
        self.len -= 1;
        self.head.take().map(|node| {
            self.head = node.next;
            node.data
        })
    }

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

    pub fn rev(self) -> SimpleLinkedList<T> {
        let mut list = Self::new();
        if self.len == 0 {
            return list;
        }
        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 = Self::new();
        for val in _iter {
            list.push(val);
        }
        list
    }
}

impl<T> Into<Vec<T>> for SimpleLinkedList<T> {
    fn into(self) -> Vec<T> {
        let mut the_vec: Vec<T> = vec![];
        if self.len == 0 {
            return the_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.

A len field is defined for SimpleLinkedList. The len field is updated as items are pushed and popped.

The is_empty() method is implemented by returning if len is 0.

The len() method is implemented by returning the value of the len field.

Do not keep track of length

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
    }
}

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.

Source: Exercism rust/simple-linked-list