详解Go语言中单链表的使用

链表

一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。使用链表结构可以避免在使用数组时需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

单链表结构

利用 struct 可以包容多种数据类型，结构体内也可以包含多个成员，这些成员可以是基本类型、自定义类型、数组类型，也可以是指针类型。这里可以使用指针类型成员来存放下一个结点的地址。如以下定义，成员 data 用来存放结点中的数据(整数类型)，next 是指针类型的成员，它指向 ListNode struct 类型数据，也就是下一个结点的数据类型。

type ListNode struct {
   data int
   next *ListNode
}

创建节点

节点声明和赋值有以下几种格式：

package main

import "fmt"

type ListNode struct {
   data int
   next *ListNode
}

func main() {

var head *ListNode
   head = new(ListNode)
   head.data = 1

var node1 = new(ListNode)
   node1.data = 2

var node2 = &ListNode{3, nil}

var node3 = &ListNode{data: 4}

fmt.Println(*head)
   fmt.Println(*node1)
   fmt.Println(*node2)
   fmt.Println(*node3)

}

/* 输出：
{1 <nil>}
{2 <nil>}
{3 <nil>}
{4 <nil>}
*/

遍历链表

一个for循环即可，结构描述的链表没有空链表的，不论data是何种类型，一旦声明即使不马上赋值也会有类型默认值，比如new(ListNode)即赋值了ListNode{0, nil}。

func showNode(p *ListNode) {
   fmt.Print(*p)
   for p.next != nil {
       p = p.next
       fmt.Print("->", *p)
   }
   fmt.Println()
}

头插法

新结点放在链表的最前面

package main

import "fmt"

type ListNode struct {
   data int
   next *ListNode
}

func showNode(p *ListNode) {
   fmt.Print(*p)
   for p.next != nil {
       p = p.next
       fmt.Print("->", *p)
   }
   fmt.Println()
}

func main() {
   var head = &ListNode{0, nil}

for i := 1; i < 5; i++ {
       var node = ListNode{data: i}
       node.next = head
       head = &node
   }

showNode(head)

}

/* 输出：
{4 0xc000084250}->{3 0xc000084240}->{2 0xc000084230}->{1 0xc000084220}->{0 <nil>}
*/

尾插法

新结点追加到链表的最后面

package main

import "fmt"

type ListNode struct {
   data int
   next *ListNode
}

func showNode(p *ListNode) {
   fmt.Print(*p)
   for p.next != nil {
       p = p.next
       fmt.Print("->", *p)
   }
   fmt.Println()
}

func main() {

var head, tail *ListNode
   head = &ListNode{0, nil}
   tail = head
   for i := 1; i < 5; i++ {
       var node = ListNode{data: i}
       (*tail).next = &node
       tail = &node
   }

showNode(head)

}

/* 输出：
{0 0xc000084220}->{1 0xc000084230}->{2 0xc000084240}->{3 0xc000084250}->{4 <nil>}
*/

遍历方法

方法的定义：参数表放在函数名前

package main

import "fmt"

type ListNode struct {
   data int
   next *ListNode
}

func (p *ListNode) travel() {
   fmt.Print(p.data)
   for p.next != nil {
       p = p.next
       fmt.Print("->", p.data)
   }
   fmt.Println("<nil>")
}

func main() {

var head = &ListNode{0, nil}
   head.travel()

for i := 1; i < 10; i++ {
       var node = ListNode{data: i}
       node.next = head
       head = &node
   }

head.travel()

var root *ListNode
   root = new(ListNode)
   root.travel()

}

/* 输出：
0<nil>
9->8->7->6->5->4->3->2->1->0<nil>
0<nil>
*/

链表长度

注意：函数与方法的区别

package main

import "fmt"

type ListNode struct {
   data int
   next *ListNode
}

func (head *ListNode) size() int {
   size := 1
   for head = head.next; head != nil; size++ {
       head = head.next
   }
   return size
}

func Len(head *ListNode) int {
   size := 1
   for head = head.next; head != nil; size++ {
       head = head.next
   }
   return size
}

func main() {

var head = &ListNode{0, nil}
   fmt.Println(Len(head))
   fmt.Println(head.size())

for i := 1; i < 10; i++ {
       var node = ListNode{data: i}
       node.next = head
       head = &node
   }

fmt.Println(Len(head))
   fmt.Println(head.size())

}

/* 输出：
1
1
10
10
*/

链表转数组

package main

import (
   "fmt"
)

type ListNode struct {
   data int
   next *ListNode
}

func (head *ListNode) size() int {
   size := 1
   for head = head.next; head != nil; size++ {
       head = head.next
   }
   return size
}

func (head *ListNode) tolist() []int {
   var res []int
   res = make([]int, 0, head.size())
   for head.next != nil {
       res = append(res, head.data)
       head = head.next
   }
   res = append(res, head.data)
   return res
}

func (head *ListNode) tolist2() []int {
   var res []int
   res = make([]int, 0, head.size())
   res = append(res, head.data)
   head = head.next
   for head != nil {
       res = append(res, head.data)
       head = head.next
   }
   return res
}

func main() {

var head = &ListNode{0, nil}

for i := 1; i < 10; i++ {
       var node = ListNode{data: i}
       node.next = head
       head = &node
   }

fmt.Println(head.tolist())

var root, tail *ListNode
   root = &ListNode{0, nil}
   tail = root
   for i := 1; i < 10; i++ {
       var node = ListNode{data: i}
       (*tail).next = &node
       tail = &node
   }

fmt.Println(root.tolist2())

}

/* 输出：
[9 8 7 6 5 4 3 2 1 0]
[0 1 2 3 4 5 6 7 8 9]
*/

数组转链表

package main

import "fmt"

type ListNode struct {
   data int
   next *ListNode
}

func (p *ListNode) travel() {
   fmt.Print(p.data)
   for p.next != nil {
       p = p.next
       fmt.Print("->", p.data)
   }
   fmt.Println("<nil>")
}

func toNode(list []int) *ListNode {
   var head, tail *ListNode
   head = &ListNode{list[0], nil}
   tail = head
   for i := 1; i < len(list); i++ {
       var node = ListNode{data: list[i]}
       (*tail).next = &node
       tail = &node
   }
   return head
}

func main() {

var lst = []int{1, 3, 2, 3, 5, 6, 6, 8, 9}
   toNode(lst).travel()

}

/* 输出：
1->3->2->3->5->6->6->8->9<nil>
*/

来源：https://blog.csdn.net/boysoft2002/article/details/126442832