go链表(头指针和尾指针)

84 阅读 0 评论 56 点赞

我是靠谱客的博主玩命电源，这篇文章主要介绍go链表(头指针和尾指针)，现在分享给大家，希望可以做个参考。

要求: 创建一个空链表, 可以从头部插入任意数据, 也可以从尾部插入, 再遍历出来

分析: 首先肯定是需要一个链表型的结构体

再用一个结构体分别指向链表的头和尾两个节点

向链表添加元素时, 动态修改两个指针的指向

主要弄清楚二者的关系就好理解了, 关系如下图:

上面是结构体链表

复制代码

1
2
3
4
5
/*创建链表结构体, 用于表示实际链表上的节点*/
type LinkNode struct {
    data interface{}				// 数据为任意类型
    next *LinkNode
}

下面只是一个结构体变量, 有两个指针, 始终指向链表的头节点和尾节点

随着链表节点增加, 分别更改这两个指针就行了

复制代码

1
2
3
4
5
/*创建结构体, 用于代表链表的头节点和尾节点*/
type OneNode struct {
    head *LinkNode			//指向链表头节点
    tail *LinkNode			// 指向链表尾节点
}

最后循环链表的时候, 只需要根据OneNode的头指针获取到LinkNode链表的头节点就可以

复制代码

1
2
3
4
5
6
7
8
/*循环链表*/
func (p *OneNode) Each() {
    node := p.head			
    for node != nil {
        fmt.Println(node.data)
        node = node.next
    }
}

完整代码:

复制代码

package main
import "fmt"

/*创建链表结构体, 用于表示实际链表上的节点*/
type LinkNode struct {
    data interface{}				// 数据为任意类型
    next *LinkNode
}

/*创建结构体, 用于代表链表的头节点和尾节点*/
type OneNode struct {
    head *LinkNode				// 表示链表中的头节点
    tail *LinkNode				// 表示链表中的尾节点
}

/*头部插入*/
func (p *OneNode)AddHead(d interface{}) {	
    /*创建节点*/
    var node = &LinkNode{
        data : d,
    }

/*OneNode, 若为空, 则创建OneNode, 指向头尾节点*/
    if p.head == nil && p.tail == nil {
        p.tail = node
        p.head = node
        return
    }
    node.next = p.head		//连结
    p.head = node
}

/*尾部插入*/
func (p *OneNode)AddTail(d interface{}) {	
    /*创建节点*/
    var node = &LinkNode{
        data : d,
    }

/*判断OneNode是否为空*/
    if p.head == nil && p.tail == nil {
        p.tail = node
        p.head = node
	    return
    }
    p.tail.next = node		//连结
    p.tail = node
}

/*循环链表*/
func (p *OneNode) Each() {
    node := p.head			// 遍历从头部开始(实际遍历的是Node)
    for node != nil {
        fmt.Println(node.data)
        node = node.next
    }
}

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
package main
import "fmt"

/*创建链表结构体, 用于表示实际链表上的节点*/
type LinkNode struct {
    data interface{}				// 数据为任意类型
    next *LinkNode
}

/*创建结构体, 用于代表链表的头节点和尾节点*/
type OneNode struct {
    head *LinkNode				// 表示链表中的头节点
    tail *LinkNode				// 表示链表中的尾节点
} 

/*头部插入*/
func (p *OneNode)AddHead(d interface{}) {	
    /*创建节点*/
    var node = &LinkNode{
        data : d,
    }

    /*OneNode, 若为空, 则创建OneNode, 指向头尾节点*/
    if p.head == nil && p.tail == nil {
        p.tail = node
        p.head = node
        return
    }
    node.next = p.head		//连结
    p.head = node
}

/*尾部插入*/
func (p *OneNode)AddTail(d interface{}) {	
    /*创建节点*/
    var node = &LinkNode{
        data : d,
    }

    /*判断OneNode是否为空*/
    if p.head == nil && p.tail == nil {
        p.tail = node
        p.head = node
	    return
    }
    p.tail.next = node		//连结
    p.tail = node
}

/*循环链表*/
func (p *OneNode) Each() {
    node := p.head			// 遍历从头部开始(实际遍历的是Node)
    for node != nil {
        fmt.Println(node.data)
        node = node.next
    }
}

复制代码

1
2
3
4
5
6
7
8
9
10
package main
import "strconv"

func main() {
    var link OneNode
    for i:=0; i<10;i++ {
        link.AddTail("A" + strconv.Itoa(i))
    }
    link.Each()
}