Shulou(Shulou.com)06/01 Report--

This article will explain in detail how to use rust to achieve a single linked list, the editor thinks it is very practical, so share it for you to do a reference, I hope you can get something after reading this article.

Preface

Today's goal is to implement a simple single linked list LinkedList with rust, while providing the ability to insert elements from the head (head insertion), flip the list, and print the list.

1. Definition of linked list nodes

To implement the linked list, first of all, the node of the linked list is implemented. According to the experience of other programming languages, the following node structure definition of the linked list is first written with rust:

Snippet 1:

Struct Node {data: t, next: Option, / / recursive type `Node` has infinite size}

In snippet 1, a Node structure is defined, and the data field uses the data of the generic type T for the linked list node. Next uses the Option enumeration, that is, if the node does not have the next node, next is nullable, there is no null value in other programming languages in rust (null, nil), but provides an Option solution, if the next node of the linked list node is empty, its next value is Option::None.

Unfortunately, code snippet 1 cannot be compiled, and a compilation error of recursive type ``Node`` has infinite size was reported. Reviewing the basics of Rust memory management, Rust needs to know how much space a type takes up at compile time, and the Node structure nests itself so that it cannot be confirmed at compile time. The smart pointer Box can be used in Rust when there is a type of unknown size at compile time and you want to use the type value in a context that requires the exact size. Change the type of the next field to Option, so that the nested type is Box, the nested Node will be assigned to the heap, and the next field stores only the data of the smart pointer Box (ptr, meta) on the stack, so that the size of the Node type can be determined at compile time. Modify snippet 1 as follows:

Snippet 2:

Struct Node {data: T, next: Option,}

After the modification is complete, you can compile and pass. According to next: Option, each linked list node Node will have ownership of its next node, Node.

two。 Definition of linked list

After defining the linked list, the next step is to define a structure LinkedList to represent the linked list, which will encapsulate some of the basic operations of the linked list. In the structure, you only need to square the field head of the chain header node with the type Option.

Snippet 3:

/ / single linked list node # [derive (Debug)] struct Node {data: t, next: Option,} / / single linked list # [derive (Debug)] struct LinkedList {head: Option,}

For ease of use, add the correlation function new to each of the Node and LinkedList structures.

Snippet 4:

Impl Node {fn new (data: t)-> Self {Self {data: data, next: None}} impl LinkedList {fn new ()-> Self {Self {head: None}

Node's new function is used to create an isolated (no next node) node with the given data data.

The new function of LinkedList is used to create an empty linked list.

3. Implementing the prepend method of inserting nodes from the head of a linked list

Now that we have completed the definition of the linked list and linked list nodes, let's implement the prepend method for the linked list, which will add nodes to the linked list by head insertion.

Snippet 5:

Impl LinkedList {fn new ()-> Self {Self {head: None}} / / insert a node in the header of the linked list (push front) fn prepend (& mut self, data: t)-> & mut Self {/ / build the node to be inserted from incoming data let mut new_node = Box::new (Node::new (data)) Match self.head {/ / when the current linked list is empty, the inserted node is directly used as the header node None = > self.head = Some (new_node), / / when the current linked list is not empty The inserted node is inserted as a new header node in front of the original header node Some (_) = > {/ / call the take method of Option to extract the header node from the Option (the internal implementation of take is a mem::replace avoidable memory copy) as the next node of the newly inserted node new_node.next = self.head.take () / / use the newly inserted node as the header node of the linked list self.head = Some (new_node);}} self}} fn main () {let mut ll = LinkedList::new (); ll.prepend (5) .prepend (4) .prepend (3) .prepend (2) .prepend (1); print! ("{ll:?}") / / LinkedList {head: Some (Node {data: 1, next: Some (Node {data: 2, next: Some (Node {data: 3, next: Some (Node {data: 4, next: Some (Node {data: 5, next: None})}} 4. Print and display Display trait customized linked list for linked list

Earlier, we implemented the prepend method of inserting nodes into the head of the linked list, and constructed a linked list in the main function to print out the information of the linked list in the form of Debug.

In order to make the print information look better, we decided to implement Display trait for LinkedList so that the format of linked list printing is similar to 1-> 2-> 3-> 4-> 5-> None.

Snippet 6:

Use std::fmt::Display;.impl Display for LinkedList {fn fmt (& self, f: & mut std::fmt::Formatter)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.