list.go

package data_struct

import "fmt"

//数据结构 线性表 单链表 实现

//链表节点
type MyNode struct {
    X    interface{}
    next *MyNode
}

//链表
type MyList struct {
    Head   *MyNode
    length int
}

func MakeList() *MyList {
    list := MyList{
        Head: &MyNode{X: 0},
    }
    return &list
}

//判空
func (t *MyList) IsEmpty() bool {
    return t.Head.next == nil
}

//链表长度
func (t *MyList) Length() int {
    return t.length
}

//清空； 将链表每一个节点都置空、（如果直接将第一个节点置空如何？由GC回收？）
func (t *MyList) Clear() {
    current := t.Head.next
    for current != nil {
        temp := current.next
        current = nil
        current = temp
    }
    t.Head.next = nil
}

//插入部
func (t *MyList) InsertHead(node *MyNode) bool {
    current := t.Head        //记录之前的第一个节点
    node.next = current.next //将之前的节点，归到新节点的指针区
    current.next = node      //将新节点更新到最开始
    t.length++
    return true
}

//插入尾部
func (t *MyList) InsertTail(node *MyNode) bool {
    //找到最后一个节点
    current := t.Head
    for current.next != nil {
        current = current.next
    }
    current.next = node
    t.length++
    return true
}

//插入。 插入i位置 ，则 i-1的节点next指现elem, elem的next指向之前i-1节点的next
func (t *MyList) Insert(i int, elem MyNode) bool {
    if i  t.length {
        return false
    }
    current := t.Head
    for k := 0; k = t.length {
        return
    }
    current := t.Head
    var before *MyNode

    for k := 0; k = t.length {
        return
    }
    current := t.Head

    for k := 0; k  %v n", i, current.X)
        current = current.next
    }
}

list_test.go

package data_struct

import (
    "testing"
    "fmt"
)

func TestMakeList(t *testing.T) {
    list := MakeList()
    if list.Head == nil {
        t.Errorf("创建的新链表第一个节点为空，但不应该为空")
    }
    if list.Head.next != nil {
        t.Errorf("创建的新链表第一个节点为空的指针区应该为空")
    }
    if !list.IsEmpty() {
        t.Errorf("创建的新链表内容应为空")
    }
}
func TestMyList_Insert(t *testing.T) {
    list := MakeList()
    list.InsertHead(&MyNode{
        X: 2,
    })
    if list.IsEmpty() {
        t.Errorf("已在头部插入节点，链表不应该为空")
    }
    list.InsertHead(&MyNode{X: 1})
    list.InsertTail(&MyNode{X: 3})
    list.InsertTail(&MyNode{X: 4})
    if list.Length() != 4 {
        t.Errorf("链表长度应为3，但Length()返回%v", list.Length())
    }
    list.PrintList()
}

func TestMyList_GetElem(t *testing.T) {
    list := MakeList()
    list.InsertHead(&MyNode{X: 2})
    list.InsertHead(&MyNode{X: 1})
    if v, _ := list.GetElem(0); v.X != 1 {
        t.Errorf("0号位的值应为1，但GetElem的结果为%v", v)
    }
    list.Insert(1, MyNode{X: 3})
    if v, _ := list.GetElem(1); v.X != 3 {
        t.Errorf("1号位的值应为3，但GetElem的结果为%v", v)
    }
    if v := list.GetIndex(3); v != 1 {
        t.Errorf("值为3的节点，在链表中的位序，应该是1，但 GetIndex 的结果为%v", v)
    }
    list.PrintList()

    if v2, _ := list.PrevNode(MyNode{X: 3}); v2.X != 1 {
        t.Errorf("1号位置的前驱值是%q,而得到的值是%v", 1, v2)
    }
    if _, ok := list.PrevNode(MyNode{X: 1}); ok {
        t.Errorf("第一个元素，没有前驱")
    }
    if _, ok := list.NextNode(MyNode{X: 2}); ok {
        t.Errorf("最后一个元素，没有后继")
    }
    if v2, _ := list.NextNode(MyNode{X: 3}); v2.X != 2 {
        t.Errorf("1号位置的前驱值是%q,而得到的值是%v", 2, v2)
    }

}

func TestMyList_Clear(t *testing.T) {
    list := MakeList()
    list.InsertHead(&MyNode{X: 2})
    list.InsertHead(&MyNode{X: 1})
    list.InsertTail(&MyNode{X: 3})
    if list.IsEmpty() {
        t.Errorf("链表不应为空")
    }
    list.Clear()
    if !list.IsEmpty() {
        t.Errorf("链表已清空，应该为空")
    }
}

func ExampleMakeList() {
    list := MakeList()  //1 2 3 
    list.InsertHead(&MyNode{X: 2})
    list.InsertHead(&MyNode{X: 1})
    list.InsertTail(&MyNode{X: 3})
    list.Insert(1, MyNode{X: 1.5})  //
    var out = func() {
        list.Traverse(func(node interface{}) {
            fmt.Print(node)
        })
        fmt.Println()
    }
    out()
    list.Delete(1)
    out()
    pv, _ := list.PrevNode(MyNode{X: 3})
    fmt.Printf("%d", pv.X)
    //output:
    // 11.523
    // 123
    // 2
}