Simple Linked List

Welcome to Simple Linked List on Exercism's Rust Track. If you need help running the tests or submitting your code, check out HELP.md.

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

Do not implement the struct SimpleLinkedList as a wrapper around a Vec. Instead, allocate nodes on the heap.
This might be implemented as:

pub struct SimpleLinkedList<T> {
    head: Option<Box<Node<T>>>,
}

The head field points to the first element (Node) of this linked list.
This implementation also requires a struct Node with the following fields:

struct Node<T> {
    data: T,
    next: Option<Box<Node<T>>>,
}

data contains the stored data, and next points to the following node (if available) or None.

Why `Option<Box<Node<T>>>` and not just `Option<Node<T>>`?

Try it on your own. You will get the following error.

| struct Node<T>
| ^^^^^^^^^^^^^^ recursive type has infinite size
...
|     next: Option<Node<T>>,
|     --------------------- recursive without indirection

The problem is that at compile time the size of next must be known. Since next is recursive ("a node has a node has a node..."), the compiler does not know how much memory is to be allocated. In contrast, Box is a heap pointer with a defined size.

Source

Created by

@kedeggel

Contributed to by

@coriolinus
@cwhakes
@efx
@ErikSchierboom
@lutostag
@ocstl
@petertseng
@rofrol
@stringparser
@tejasbubane
@treble37
@xakon
@ZapAnton

Based on

Inspired by 'Data Structures and Algorithms with Object-Oriented Design Patterns in Ruby', singly linked-lists. - https://web.archive.org/web/20160731005714/http://brpreiss.com/books/opus8/html/page96.html

maduma/exercism-simple-linked-list