链表是一种数据结构，和数组不同，链表并不需要一块连续的内存空间，它通过「指针」将一组零散的内存块串联

概念

通过指针将一组零散的内存块串联在一起 ， 把内存块称为链表的“结点”。 记录下个结点地址的指针叫作后继指针 next ， 一个结点叫作头结点，把最后一个结点叫作尾结点

单链表操作

定义链表和头指针

// 定义节点
type Node struct {
    Value int
    Next *Node
}

// 初始化头结点
var head = new(Node)

添加节点

// 添加节点
func addNode(t *Node, v int) int {
    if head == nil {
        t = &Node{v, nil}
        head = t
        return 0
    }

    if v == t.Value {
        fmt.Println("节点已存在:", v)
        return -1
    }

    // 如果当前节点下一个节点为空
    if t.Next == nil {
        t.Next = &Node{v, nil}
        return -2
    }

    // 如果当前节点下一个节点不为空
    return addNode(t.Next, v)
}

查找节点

// 查找节点
func searchNode(t *Node, v int) bool {
    if head == nil {
        t = &Node{v, nil}
        head = t
        return false
    }
    if v == t.Value {
        return true
    }
    if t.Next == nil {
        return false
    }
    return searchNode(t.Next, v)
}

遍历链表

// 遍历链表
func traverse(t *Node) {
    if t == nil {
        fmt.Println("-> 空链表!")
        return
    }
    for t != nil {
        fmt.Printf("%d -> ", t.Value)
        t = t.Next
    }
    fmt.Println()
}

获取链表长度

// 获取链表长度
func size(t *Node) int {
    if t == nil {
        fmt.Println("-> 空链表!")
        return 0
    }
    i := 0
    for t != nil {
        i++
        t = t.Next
    }
    return i
}