Shulou(Shulou.com)05/31 Report--

This article mainly explains "how to use linked lists in Go language". Interested friends may wish to have a look at it. The method introduced in this paper is simple, fast and practical. Let's let the editor learn how to use linked lists in Go language.

1. What is a linked list

The linked list is a non-continuous and non-sequential storage structure on the physical storage unit, and the logical order of data elements is realized by the pointer link order in the linked list.

The linked list consists of a series of nodes (each element in the linked list is called a node), and the node can be generated dynamically at run time. Each node consists of two parts: one is the data field in which the data elements are stored, and the other is the pointer domain in which the address of the next node is stored.

Using the linked list structure can avoid the disadvantage of knowing the data size in advance when using the array, and the linked list structure can make full use of the computer memory space to achieve flexible memory dynamic management. However, the linked list loses the advantage of random reading of the array, and the linked list has a large space overhead due to the increase of the pointer domain of the node.

Linked lists allow you to insert and remove nodes anywhere on the table, but do not allow random access.

There are three types of linked lists: one-way linked lists, two-way linked lists, and circular linked lists.

two。 Basic operation of single item linked list

Each node in the one-way linked list consists of two parts, namely, the data domain and the pointer domain. The pointer of the previous node points to the next node, which is connected in turn to form a linked list.

A linked list connects a set of scattered memory blocks together by pointers, and the memory blocks here are called nodes of the linked list. In order to string these nodes together, the node of each linked list not only stores data, but also records the pointer of the next node (that is, the address of the next node). This pointer is called the subsequent pointer.

3. Define a single linked list using struct

The feature that Struct can contain multiple data types

The body of a structure can contain several members, which can be primitive types, custom types, array types, or pointer types.

The three forms defined by struct, where 2 and 3 are pointers to the return structure

/ / define var stu Studentvar stu * Student = new (Student) var stu * Student = & Student {} / / call stu.Name stu.Age stu.Score or (* stu) .Name (* stu) .Age (* stu) .Score

Define a single item linked list

Next is an attribute of the pointer type that points to the Student struct type data, that is, the data type of the next node

Type Student struct {Name string Age int Score float32 next * Student}

Assign a value to the linked list and traverse each node in the linked list

Package mainimport "fmt" type Student struct {Name string Age int Score float32 next * Student / / address where the next structure is stored Point directly to the next structure} func main () {/ / head structure var head Student head.Name = "Zhang San" head.Age = 28 head.Score = 88 / / the second structure node var stu1 Student stu1.Name = "Li Si" stu1.Age = 25 stu1.Score = 100head.next = & stu1 / / the third structure node var stu2 Student stu2.Name = "Wang Wu" stu2.Age = 18 stu2.Score = 60 stu1.next = & stu2 Req (& head)} func Req (tmp * Student) {/ / tmp pointer is the address of the next structure Adding * is the next structure for tmp! = nil {/ / traversing each structure in the output list Determine whether fmt.Println (* tmp) tmp = tmp.next / / tmp is empty or not. Change the address of the next structure}} / / the output is as follows: {Zhang San 28 88 0xc000114480} {Li Si 25 100 0xc0001144b0} {Wang Wu 18 60} 4. Add nodes at the tail

Method one

Package mainimport ("fmt"math/rand") type Student struct {Name string Age int Score float32 next * Student} func main () {/ / header structure var head Student head.Name = "head" head.Age = 28 head.Score = 88 / / second structure node var stu1 Student stu1.Name = "stu1" stu1.Age = 25 stu1.Score = 100head.next = & stu1 / / the head points to the first structure / / the third structure node var stu2 Student stu2.Name = "stu2" stu2.Age = 18 stu2.Score = 60 stu1.next = & stu2 / / the first structure points to the second node The fourth structure node var stu3 Student stu3.Name = "stu3" stu3.Age = 18 stu3.Score = 80 stu2.next = & stu3 / / the second structure points to the third structure / / the declaration variable var tail = & stu3 for I: = 4 I < 10 Var stu Student + {/ / define node var stu Student = Student {Name: fmt.Sprintf ("stu%d", I), Age: rand.Intn (100), Score: rand.Float32 () * 100 } / / production structure in series tail.next = & stu tail = & stu} Req (& head)} func Req (tmp * Student) {for tmp! = nil {fmt.Println (* tmp) tmp = tmp.next}} / / the output result is as follows: {head 28 88 0xc0001144b0} {stu1 25 100 0xc0001144e0} {stu2 18 60 0xc000114510} {stu3 18 80 0xc000114540} {stu4 81 94.05091 0xc000114570} {stu5 47 43.77142 0xc0001145a0} {stu6 81 68.682304 0xc0001145d0} {stu7 25 15.651925 0xc000114600} {stu8 56 30.091187 0xc000114630} {stu9 94 81.36399}

Method 2, use function to optimize

Package mainimport ("fmt"math/rand") type Student struct {Name string Age int Score float32 next * Student} func main () {/ / header structure var head Student head.Name = "head" head.Age = 28 head.Score = 88 TailInsert (& head) Req (& head)} / / Loop through func Req (tmp * Student) {for tmp! = nil {fmt.Println (* tmp) tmp = tmp.next}} / / add structure node func TailInsert (tail * Student) {for I: = 0 I < 10 Var stu Student + {/ / define node var stu Student = Student {Name: fmt.Sprintf ("stu%d", I), Age: rand.Intn (100), Score: rand.Float32 () * 100 } / / production structure concatenated tail.next = & stu / / points to the next structure tail = & stu / / gives the current structure to tail Let it continue to cycle}} / / output the following {head 28 88 0xc0001144b0} {stu0 81 94.05091 0xc0001144e0} {stu1 47 43.77142 0xc000114510} {stu2 81 68.682304 0xc000114540} {stu3 25 15.651925 0xc000114570} {stu4 56 30.091187 0xc0001145a0} {stu5 94 81.36399 0xc0001145d0} {stu6 62 38.06572 0xc000114600} {stu7 28 46.888985 0xc000114630} {stu8 11 29.310184 0xc000114660} {stu9 37 21.855305} 5. Insert the head into the node

Method one

Package mainimport ("fmt"math/rand") type Student struct {Name string Age int Score float32 next * Student} func main () {/ / header structure var head Student head.Name = "head" head.Age = 28 head.Score = 88 / / call the header insertion function HeadInsert ( & head) Req (& head)} func Req (tmp * Student) {for tmp! = nil {fmt.Println (* tmp) tmp = tmp.next}} func HeadInsert (p * Student) * Student {for I: = 0 I < 10 ITunes + {var stu = Student {Name: fmt.Sprintf ("stu%d", I), Age: rand.Intn (100), Score: rand.Float32 () * 100,} / / the current new node points to head Because head is the next node stu.next = p / / points to the next node p = & stu / / give the current structure to tail Let it continue to cycle} return p} / / the output is as follows: {stu9 85 30.152267 0xc000094840} {stu8 37 5.912065 0xc000094810} {stu7 29 7.9453626 0xc0000947e0} {stu6 87 60.72534 0xc0000947b0} {stu5 41 2.8303082 0xc000094780} {stu4 90 69.67192 0xc000094750} {stu3 87 20.658266 0xc000094720} {stu2 47 29.708258 0xc0000946f0} {stu1 28 86.249146 0xc0000946c0} {stu0 95 36.08714 0xc0000944b0} {head 2888}

Method two

Use the pointer of the pointer

Package mainimport ("fmt"math/rand") type Student struct {Name string Age int Score float32 next * Student} func main () {/ / header structure var head * Student = & Student {} head.Name = "head" head.Age = 28 head.Score = 88 / / call header insert letter Count HeadInsert (& head) Req (head)} func Req (tmp * Student) {for tmp! = nil {fmt.Println (* tmp) tmp = tmp.next}} func HeadInsert (p * * Student) {for I: = 0 I < 10 ITunes + {var stu = Student {Name: fmt.Sprintf ("stu%d", I), Age: rand.Intn (100), Score: rand.Float32 () * 100,} / / the current new node points to head Because head is the next node stu.next = * p / / points to the next node * p = & stu / / give the current structure to tail Let it continue to cycle}} / / output the following {stu9 37 21.855305 0xc000114660} {stu8 11 29.310184 0xc000114630} {stu7 28 46.888985 0xc000114600} {stu6 62 38.06572 0xc0001145d0} {stu5 94 81.36399 0xc0001145a0} {stu4 56 30.091187 0xc000114570} {stu3 25 15.651925 0xc000114540} {stu2 81 68.682304 0xc000114510} {stu1 47 43.77142 0xc0001144e0} {stu0 81 94.05091 0xc0001144b0} {head 2888}

Summary

If you want external data and function processing results to be synchronized, there are two ways:

① pass parameters, pass pointers

② return returns the value

6. Add a new node package mainimport ("fmt"math/rand") type Student struct {Name string Age int Score float32 next * Student} func main () {/ / header structure var head * Student = & Student {} / / define pointer type head.Name = "head" head.Age = 28 after specifying the node Head.Score = 88 / / define a new node var newNode * Student = & Student {} / / define the pointer type newNode.Name = "newNode" newNode.Age = 19 newNode.Score = 78 HeadInsert (& head) / / insert function Add (head) at the specified location NewNode) Req (head)} func Req (tmp * Student) {for tmp! = nil {fmt.Println (* tmp) tmp = tmp.next}} func HeadInsert (p * * Student) {/ / pointer to the pointer for I: = 0 I < 10 ITunes + {var stu = Student {Name: fmt.Sprintf ("stu%d", I), Age: rand.Intn (100), Score: rand.Float32 () * 100,} / / the current new node points to head Because head is the next node stu.next = * p / / points to the next node * p = & stu / / give the current structure to tail and let it continue to loop}} / / p as the current node Newnode is the inserted node func Add (p * Student) NewNode * Student) {for p! = nil {if p.Name = = "stu6" {/ / dock the next node newNode.next = p.next p.next = newNode} / / insert the node to the next node P = p.next / / p.next assigns p Continue traversing}} / / the output is as follows: {stu9 37 21.855305 0xc0000c0660} {stu8 11 29.310184 0xc0000c0630} {stu7 28 46.888985 0xc0000c0600} {stu6 62 38.06572 0xc0000c04b0} {newNode 19 78 0xc0000c05d0} {stu5 94 81.36399 0xc0000c05a0} {stu4 56 30.091187 0xc0000c0540} {stu2 81 68.682304 0xc0000c0510} {stu1 47 43.77142 0xc0000c04e0} {stu0 81 94.05091 0xc0000c0480} {head 28 88} 7. Delete node package mainimport ("fmt"math/rand") type Student struct {Name string Age int Score float32 next * Student} func main () {/ / header structure var head * Student = & Student {} / / define pointer type head.Name = "head" head.Age = 28 head.Score = 88 / / define a new node var newNode * Student = & Student {} / / define the pointer type newNode.Name = "newNode" newNode.Age = 19 newNode.Score = 78 HeadInsert (& head) / / insert function Add (head) at the specified location NewNode) / / Delete node del (head) Req (head)} func Req (tmp * Student) {for tmp! = nil {fmt.Println (* tmp) tmp = tmp.next}} func HeadInsert (p * * Student) {/ / pointer to the pointer for I: = 0 I < 10 ITunes + {var stu = Student {Name: fmt.Sprintf ("stu%d", I), Age: rand.Intn (100), Score: rand.Float32 () * 100,} / / the current new node points to head Because head is the next node stu.next = * p / / points to the next node * p = & stu / / give the current structure to tail and let it continue to loop}} / / p as the current node Newnode is the inserted node func Add (p * Student) NewNode * Student) {for p! = nil {if p.Name = = "stu6" {/ / dock the next node newNode.next = p.next p.next = newNode} / / insert the node to the next node P = p.next / / p.next assigns p Continue to cycle through}} / / delete node func del (p * Student) {var prev * Student = p / / p=head prev=head-- "prev=p for p! = nil {if p.Name = =" newNode "{prev.next = p.next break } prev = p / / translate The output result is as follows: {stu9 37 21.855305 0xc0000c0660} {stu8 11 29.310184 0xc0000c0630} {stu7 28 46.888985 0xc0000c0600} {stu6 62 38.06572 0xc0000c05d0} {stu5 94 81.36399 0xc0000c05a0} {stu4 56 30.091187 0xc0000c0570} {stu3 25 15.651925 0xc0000c0540} {stu2 81 68.682304 0xc0000c0510} {stu1 47 43. 77142 0xc0000c04e0} {stu0 81 94.05091 0xc0000c0480} {head 28 88} so far I believe you have a deeper understanding of "how to use linked lists in Go language". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

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.