Golang(五十一)[线性存储

1
2
3
4
5

mkdir -p linkList
cd linkList
go mod init linkList
touch linkList.go
vim linkList.go

1
2
3
4
5
6
7

// 定义环形链表的结点结构体
type LinkNode struct {
    // 定义环形链表的数据域
    Data interface{}
    // 定义环形链表指针域
    Next *LinkNode
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// 创建环形链表
func (node *LinkNode) NewLinkList(data ...interface{}) {
    // 容错处理
    if node == nil || len(data) == 0 {
        return
    }
    // 保存head结点
    head := node
    // 遍历data数据创建新结点
    for _, v := range data {
        // 创建新结点，并初始化
        newNode := new(LinkNode)
        newNode.Data = v
        newNode.Next = nil

        // 将当前结点的指针域指向新结点
        node.Next = newNode
        // 更新当前结点
        node = node.Next
    } // 遍历结束，node在尾结点
    // 将尾结点的指针域指向第一个数据结点(head.Next)
    node.Next = head.Next
    // 将head结点赋值给node,以便node回到head结点位置
    node = head
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

// 正向打印环形链表--递归实现
var start interface{}

func (node *LinkNode) Print1() {
    // 容错处理
    if node == nil {
        return
    }
    // 如果是头结点就给第一个数据结点标记赋值[头结点的数据域为nil]
    if node.Data == nil {
        // 做第一个数据结点的标记
        start = node.Next
    }
    // 数据结点的特点：有数据数据域
    if node.Data != nil {
        fmt.Print(node.Data, " ")
        //  递归的出口: 此时应该在尾结点[数据域不为空，]，其下一个结点(node.Next)即将回到第一个数据结点
        if node.Next == start {
            // 在递归调用出口处打印换行
            fmt.Println()
            return
        }
    }
    // 递归实现
    node.Next.Print1()
}

1
2
3
4
5

func main() {
    list := new(LinkNode)
    list.NewLinkList(1, 2, 3, 4, 5, 6, 7)
    list.Print1()
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// 正向打印环形链表--循环实现
func (node *LinkNode) Print2() {
    // 容错处理
    if node == nil {
        return
    }
    // 定义第一个数据结点的位置标记
    start := node.Next
    for node.Next != nil {
        node = node.Next // 更新node结点位置，在初始时，可以跳过head指针[head结点：没有数据域(nil),只有指针域(指向第一个数据结点)]
        // 数据结点的特点：有数据数据域
        if node.Data != nil {
            fmt.Print(node.Data, " ")
        }
        // 判断是否在尾结点(即node.Next是否指向第一个数据结点位置)
        if start == node.Next {
            // 已经在尾结点，直接返回
            return
        }
    }
    // 打印换行
    fmt.Println()
}

1
2
3
4
5

func main() {
    list := new(LinkNode)
    list.NewLinkList(1, 2, 3, 4, 5, 6, 7)
    list.Print2()
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

// 获取数据结点长度
func (node *LinkNode) Length() (length int) {
    // 容错处理
    if node == nil {
        return
    }
    // 标记第一个数据结点的位置：head结点的下一个结点[node.Next]
    start := node.Next
    for {
        node = node.Next // 初始可以跳过head结点
        length++
        // 如果当前在尾结点，即指针域指向第一个数据结点时
        if start == node.Next {
            break
        }
    }
    /* // 也可以使用如下方法获取：
    for {
        node = node.Next // 初始跳过head 结点
        if node.Data != nil {
            length++
        }
        // 如果当前在尾结点，即指针域指向第一个数据结点时
        if start == node.Next {
            break
        }
    } */
    return
}

1
2
3
4
5
6
7

func main() {
    list := new(LinkNode)
    list.NewLinkList(1, 2, 3, 4, 5, 6, 7)
    list.Print1()
    length := list.Length()
    fmt.Println("环形链表的数据结点长度为：", length)
}