七叶笔记 » golang编程 » 数据结构基础(golang版本)——单向无序链表

数据结构基础(golang版本)——单向无序链表

一。链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表的可以灵活利用内存空间,相对于数组减少了内存的浪费,同时链表的插入速度较数组快,时间复杂度是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
}  

相关文章