一。链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表的可以灵活利用内存空间，相对于数组减少了内存的浪费，同时链表的插入速度较数组快，时间复杂度是O(1)。但缺点也比较明显，那就是不能随机查找元素，只能从头开始遍历，因此查找的时间复杂度是O(n)。那么现在就用golang来实现一个单向无序链表。
单向无序链表是相对较简单的链表，其特点是：
1.有一个Head头，用于存储表头信息。
2.每个节点的Next指向下一个节点，尾节点的Next为nil。
二。废话不多说，上菜：
1.首先声明链表的结构体
type Node struct {
Value int
Next *Node
}
type SinglyList struct {
Head *Node
*Node
} 2.初始化链表方法
//createList swap a list
func createList(value int) *SinglyList {
list := &SinglyList{}
head := &Node{Value: value}
list.Head = head
list.Node = head
return list
} 3.插入节点，这里有两种方式，一种是在尾部插入，另一种是头部插入。尾部插入比较简单，只需要找到当前的尾部节点，然后将该节点的next指向到新的节点即可。而在头部插入则需要将新节点的next指向到链表的头部节点，同时将链表的头赋值于新节点。
//insertLast insert at tail
func (l *SinglyList) insertLast(value int) {
n := &Node{Value: value}
head := l.Head
for head.Next != nil {
head = head.Next
}
head.Next = n
}
//insertFront insert at head
func (l *SinglyList) insertFront(value int) {
n := &Node{Value: value}
n.Next = l.Head
l.Head = n
} 4.删除节点。同样的需要通过从头开始遍历查找需要删除的节点，然后将当前节点的前一个节点的Next指向当前节点的Next即可。
//deleteNode delete node by value
func (l *SinglyList) deleteNode(value int) bool {
offset := l.Head
preNode := l.Head
for offset != nil {
if offset.Value == value {
preNode.Next = offset.Next
return true
}
preNode = offset
offset = offset.Next
}
return false
} 5.正序遍历，这个比较简单，直接从头到尾遍历即可。
//retrieve retrieve element just print
func (l *SinglyList) retrieve() []int {
head := l.Head
result := make([]int, 0)
for head != nil {
result = append(result, head.Value)
head = head.Next
}
return result
} 6.反向遍历，这里只是遍历，不改变链表的顺序。这里利用了递归进行反向输出。
//reverseRetrieve retrieve all elements
func (l *SinglyList) reverseRetrieve() []int {
result := make([]int, 0)
getNode(&result, l.Head)
return result
}
func getNode(result *[]int, node *Node) {
if node != nil {
getNode(result, node.Next)
*result = append(*result, node.Value)
}
} 7.反转链表，分四步走。
7.1 初始化一个新的尾节点；
7.2 声明一个ofset偏移量指向到头节点的next；
7.3 正序遍历每个节点并且以此插入到新的尾节点之前；
7.4 最后将链表的头赋值给尾节点。
//reverseList reverse all elements
func (l *SinglyList) reverseList() {
tail := &Node{Value: l.Head.Value}
offset := l.Head.Next
next := &Node{}
for offset != nil {
next = offset.Next
offset.Next = tail
tail = offset
offset = next
}
l.Head = tail
} 8.最后来一个打印链表，实现了接口stringer。
//String implement stringer
func (l *SinglyList) String() string {
head := l.Head
out := strings.Builder{}
for head != nil {
out.WriteString(fmt.Sprintf("%d ", head.Value))
head = head.Next
}
return out.String()
} 9.简单的用main测试
func main() {
//单向链表的特点是尾部为nil 每个节点的Next指向下一个节点
singlyList := createList(1)
for i := 2; i < 10; i++ {
singlyList.insertLast(i)
}
fmt.Println(singlyList)
fmt.Println("after retrieve")
fmt.Println(singlyList.retrieve())
fmt.Println("after reverseRetrieve")
fmt.Println(singlyList.reverseRetrieve())
fmt.Println("insertFront")
singlyList.insertFront(0)
singlyList.insertFront(-1)
singlyList.insertFront(-2)
fmt.Println(singlyList)
singlyList.reverseList()
fmt.Println("after reverseList", singlyList)
fmt.Printf("find node where value=8:%v\n", singlyList.findNode(8))
singlyList.deleteNode(7)
fmt.Println("after delete where value=7:", singlyList)
} 10.收工，最后贴上完整代码，可直接运行。
package main
import (
"fmt"
"strings"
)
func main() {
//单向链表的特点是尾部为nil 每个节点的Next指向下一个节点
singlyList := createList(1)
for i := 2; i < 10; i++ {
singlyList.insertLast(i)
}
fmt.Println(singlyList)
fmt.Println("after retrieve")
fmt.Println(singlyList.retrieve())
fmt.Println("after reverseRetrieve")
fmt.Println(singlyList.reverseRetrieve())
fmt.Println("insertFront")
singlyList.insertFront(0)
singlyList.insertFront(-1)
singlyList.insertFront(-2)
fmt.Println(singlyList)
singlyList.reverseList()
fmt.Println("after reverseList", singlyList)
fmt.Printf("find node where value=8:%v\n", singlyList.findNode(8))
singlyList.deleteNode(7)
fmt.Println("after delete where value=7:", singlyList)
}
type Node struct {
Value int
Next *Node
}
type SinglyList struct {
Head *Node
*Node
}
//String implement stringer
func (l *SinglyList) String() string {
head := l.Head
out := strings.Builder{}
for head != nil {
out.WriteString(fmt.Sprintf("%d ", head.Value))
head = head.Next
}
return out.String()
}
//createList swap a list
func createList(value int) *SinglyList {
list := &SinglyList{}
head := &Node{Value: value}
list.Head = head
list.Node = head
return list
}
//insertLast inset at tail
func (l *SinglyList) insertLast(value int) {
n := &Node{Value: value}
head := l.Head
for head.Next != nil {
head = head.Next
}
head.Next = n
}
//insertFront inset at head
func (l *SinglyList) insertFront(value int) {
n := &Node{Value: value}
n.Next = l.Head
l.Head = n
}
//retrieve retrieve element just print
func (l *SinglyList) retrieve() []int {
head := l.Head
result := make([]int, 0)
for head != nil {
result = append(result, head.Value)
head = head.Next
}
return result
}
//reverseRetrieve retrieve all elements
func (l *SinglyList) reverseRetrieve() []int {
result := make([]int, 0)
getNode(&result, l.Head)
return result
}
func getNode(result *[]int, node *Node) {
if node != nil {
getNode(result, node.Next)
*result = append(*result, node.Value)
}
}
//reverseList reverse all elements
func (l *SinglyList) reverseList() {
tail := &Node{Value: l.Head.Value}
offset := l.Head.Next
next := &Node{}
for offset != nil {
next = offset.Next
offset.Next = tail
tail = offset
offset = next
}
l.Head = tail
}
//findNode search node by value
func (l *SinglyList) findNode(value int) *Node {
offset := l.Head
for offset != nil {
if offset.Value == value {
return offset
}
offset = offset.Next
}
return nil
}
//deleteNode delete node by value
func (l *SinglyList) deleteNode(value int) bool {
offset := l.Head
preNode := l.Head
for offset != nil {
if offset.Value == value {
preNode.Next = offset.Next
offset = nil
preNode = nil
return true
}
preNode = offset
offset = offset.Next
}
return false
} 