关于后端:数据结构1

数据结构（1）

1. 链表

链表中数据呈线性排列。在单链表中增加，删除数据都为 O(1)，查找数据为 O(n)。

在实现链表可增加一个“虚”头节点，这能够使链表操作更简便。

链表的存储能够是不间断的。

1.1 数据结构

type listNode struct {Data interface{}
    Next *listNode
}

1.2 初始化头节点

func makeList() *listNode {
    return &listNode{Next: nil,}
}

1.3 建设链表

头插法

对应代码

temp := head.Next // 在断开指针会失落下一节点的地址，用 temp 保留下一节点的地址
node := new(listNode)
head.Next = node
node.Data = data
node.Next = temp

残缺代码

func HeadInsert(head *listNode, data int) {
    temp := head.Next
    node := new(listNode)
    head.Next = node
    node.Data = data
    node.Next = temp
}

尾插法

对应代码

node := new(listNode)
node.Data = data
last.Next = node
node.Next = nil

残缺代码

func TailInsert(head *listNode, data interface{}) {
    last := head
    for last.Next != nil { // 找到 last
        last = last.Next
    }

    node := new(listNode)
    last.Next = node
    node.Data = data
    node.Next = nil
}

1.4 查找

在单链表中查找数据只能从头节点开始顺次向后查找直到找到指标数据为止，工夫复杂度为 O(n).

例如：在 1，2 中查找 2，顺次比拟数据是否为 2，如果为 2 则找到；如果查找齐全部还没有找到，则链表中不存在该数据。

func SearchNode(head *listNode, data interface{}) (*listNode, bool) {
    node := head
    for node.Next != nil {
        node = node.Next
        if node.Data == data {return node, true}
    }
    return nil, false
}

1.5 删除

func DeleteNode(head *listNode, data interface{}) bool {
    node := head
    for node.Next != nil {
        node = node.Next
        if node.Next.Data == data {
            node.Next = node.Next.Next
            return true
        }
    }
    return false
}