Implementing a Linked List in Rust.

In this story we are going to look at a very common used data structure, that is, a linked list. After looking at its definition we will provide a possible realization in Rust. When it comes to data structures Rust is known to be a little tricky because of its strict ownership rules. Though, we will see linked lists as a relative simple structure, will not provide too many difficulties. At the end we will use our learned to solve a nice problem to practice coding.

Definition:

A linked list is a set of nodes where each node has a value and a reference/link to another node that is called ‘next’. The correspondence between a node and its next not is one-to-one, meaning, a node can be the next node of exactly one node. Moreover, the linked list has exactly one node that is not the next of another (the start) and a node that has no next node (the end).

Implementation:

Let us look at the implementation of a linked list that makes the above definition much clearer:

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

As you can see, the data structure is recursive by definition. For this reason we have to wrap the type of the field next into a Box that ensures only a pointer has to be saved in the stack and hence the size of the struct is…