（4）Go实现单链表

链表（Linked list）是一种 “动态数据结构”，链表由节点构成node链接构成，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针。
相比数组，数组的内存地址是连续的，而链表不用连续的内存地址
链表是动态数据结构，用链表组成的栈和队列数据结构，不用做扩容和缩容操作

node 节点一般存储两个元素，本节点内容content和下一个节点指针next，结构如下
type Node struct{
      Content  interface{}
      Next     *Node
}

链表由节点组成，由3个元素组成，length链表长度，head头节点，tail尾节点，结构如下
type LinkedList struct{
        Length    int
        Head    *Node
        Tail    *Node    
}

// 单链表数据结构的实现
// 节点
type node struct {
    Item interface{}
    Next *node
}

// 链表
type linkedList struct {
    Length    int
    DummyHead *node //虚拟头节点，可以统一头节点和其他节点的操作，达到简化逻辑的效果
}

func NewNode() *node {
    return &node{
        Item: nil,
        Next: nil,
    }
}

func NewLinkedList() *linkedList {
    return &linkedList{
        Length:    0,
        DummyHead: &node{},  
    }
}

func (l *linkedList) Add(index int, n *node) {
    if index < 0 || index > l.Length {
        log.Fatal("failed to add, index 超出范围.")
    }
    prev := l.DummyHead
    for i := 0; i < index; i++ {
        prev = prev.Next
    }

    n.Next = prev.Next
    prev.Next = n
    l.Length++
}

func (l *linkedList) AddFirst(n *node) {
    l.Add(0, n)
}

func (l *linkedList) AddLast(n *node) {
    l.Add(l.Length-1, n)
}

// 输入index，返回index位节点
func (l *linkedList) Get(index int) (cur *node, err error) {
    if index < 0 || index > l.Length {
        err = errors.New("failed to traverse, index out of range.")
        return nil, err
    }

    if l.Length == 0 {
        log.Fatal("failed to traverse,linkedList is empty.")
    }

    cur = l.DummyHead //虚拟头节点

    for i := 0; i <= index; i++ {
        cur = cur.Next //index位节点
    }
    return cur, nil
}

// 修改index节点
func (l *linkedList) Modify(index int, n *node) {
    if index < 0 || index > l.Length {
        log.Fatal("failed to modify, index out of range.")
    }

    if l.Length == 0 {
        log.Fatal("failed to traverse,linkedList is empty.")
    }

    cur, _ := l.Get(index)

    cur.Item = n.Item
    cur.Next = n.Next
}

// 修改index节点内容
func (l *linkedList) ModifyContent(index int, item interface{}) {
    if index < 0 || index > l.Length {
        log.Fatal("failed to modifyContent, index out of range.")
    }

    if l.Length == 0 {
        log.Fatal("failed to traverse,linkedList is empty.")
    }

    cur, _ := l.Get(index)
    cur.Item = item

}

func (l *linkedList) Delete(index int) error {
    if index < 0 || index > l.Length {
        return errors.New("failed to delete, index out of range.")
    }

    prev := l.DummyHead
    for i := 0; i < index; i++ {
        prev = prev.Next
    }

    delNode := prev.Next
    prev.Next = delNode.Next
    delNode = nil
    l.Length--
    return nil
}

// 查找链表中是否有元素e
func (l *linkedList) Contains(n *node) bool {
    if l.Length == 0 {
        return false
    }

    cur := l.DummyHead //虚拟头节点

    for i := 0; i <= l.Length-1; i++ {
        cur = cur.Next //index位节点
        if cur == n {
            return true
        }
    }
    return false
}

// 获取链表中所有内容
func (l *linkedList) Traverse() []interface{} {
    resp := []interface{}{}
    buf := l.DummyHead.Next
    for buf != nil {
        resp = append(resp, buf.Item, "->")
        buf = buf.Next
    }
    resp = append(resp, nil)
    return resp
}

// 测试链表
func main() {
    l := linked_list1.NewLinkedList()
    q := linked_list1.NewNode()

    for i := 0; i < 5; i++ {
        buf := linked_list1.NewNode()
        buf.Item = i
        l.AddFirst(buf)
        resp := l.Traverse()
        fmt.Println(resp)
    }
    fmt.Println(l.Contains(q))

    for i := 0; i < 5; i++ {
        l.ModifyContent(i, 8+i)
        resp := l.Traverse()
        fmt.Println(resp)
    }

    for i := 0; i < 5; i++ {
        l.Delete(4 - i)
        resp := l.Traverse()
        fmt.Println(resp)
    }

    l.Modify(1, q)
    resp := l.Traverse()
    fmt.Println(resp)
}

// 测试结果
[0 -> <nil>]
[1 -> 0 -> <nil>]
[2 -> 1 -> 0 -> <nil>]
[3 -> 2 -> 1 -> 0 -> <nil>]
[4 -> 3 -> 2 -> 1 -> 0 -> <nil>]
false
[8 -> 3 -> 2 -> 1 -> 0 -> <nil>]
[8 -> 9 -> 2 -> 1 -> 0 -> <nil>]
[8 -> 9 -> 10 -> 1 -> 0 -> <nil>]
[8 -> 9 -> 10 -> 11 -> 0 -> <nil>]
[8 -> 9 -> 10 -> 11 -> 12 -> <nil>]
[8 -> 9 -> 10 -> 11 -> <nil>]
[8 -> 9 -> 10 -> <nil>]
[8 -> 9 -> <nil>]
[8 -> <nil>]
[<nil>]
2019/04/16 23:59:31 failed to modify, index out of range.

有bug欢迎指出，转载请注明出处。