关于后端:数据结构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
}