单链表

链表是一种链式存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的，单链表的结构如下图

代码实现

package line
type LinkList struct {
    first  *element
    last   *element
    length int
}
type element struct {
    item interface{}
    next *element
}
func NewLinkList() *LinkList {
    return &LinkList{}
}
func (this *LinkList) Get(index int) (interface{}, bool) {
    if this.length == 0 || index >= this.length || index < 0 {
        return nil, false
    }
    ele := this.first
    for i := 0; i < index; i++ {
        ele = ele.next
        if ele == nil {
            return nil, false
        }
    }
    return ele.item, true
}
func (this *LinkList) Set(index int, item interface{}) bool {
    if index > this.length || index < 0 {
        return false
    }
    current := &element{
        item: item,
    }
    if index == 0 {
        current.next = this.first.next
        this.first   = current
        if this.length == 0 {
            this.last = this.first
            this.length++
        }
        return true
    }
    ele := this.first
    for i:=0; i< index -1; i++ {
        ele = ele.next
    }
    indexEle := ele.next
    current.next = indexEle.next
    ele.next     = current
    if index == this.length {
        this.length++
        this.last = current
    }
    return true
}
func (this *LinkList) Insert(index int, item interface{}) bool {
    if index > this.length || index < 0 {
        return false
    }
    defer func() {
        this.length++
    }()
    current := &element{
        item: item,
    }
    //头位置，需要更换头指针
    if index == 0 {
        current.next = this.first
        this.first   = current
        if this.length == 0 {
            this.last = this.first
        }
        return true
    }
    //尾位置，需要更换尾指针
    if index == this.length {
        this.last.next = current
        this.last      = current
        return true
    }
    ele := this.first
    for i := 0; i < index - 1; i++ {
        ele = ele.next
    }
    //获取索引位置元素
    indexEle := ele.next
    //将索引位置元素放到插入元素后面
    current.next = indexEle
    //上一元素的下一个元素为当前元素
    ele.next = current
    return true
}
func (this *LinkList) Prepend(item interface{}) {
    this.Insert(0, item)
}
func (this *LinkList) Append(item interface{}) {
    this.Insert(this.length, item)
}
func (this *LinkList) Length() int {
    return this.length
}
func (this *LinkList) Remove(index int) bool {
    if this.length == 0 || index > this.length - 1 || index < 0 {
        return false
    }
    defer func() {
        this.length--
    }()
    if index == 0 {
        this.first = this.first.next
        return true
    }
    ele := this.first
    for i :=0; i < index - 1; i++ {
        ele = ele.next
    }
    indexEle := ele.next
    ele.next = indexEle.next
    indexEle = nil
    if this.length == index {
        this.last = ele
    }
    return true
}
func (this *LinkList) Range(f func(index int, item interface{})) {
    ele := this.first
    for i := 0; i < this.length; i++ {
        f(i, ele.item)
        ele = ele.next
    }
}

使用

   //初始化链表
   container := line.NewLinkList()
    //向索引位置1插入数据10，插入失败，因为头结点还没有数据
    result := container.Insert(1, 10)
    fmt.Printf("Insert: %t, container.Length:%d\n", result, container.Length())
    //向头结点插入数据0
    //此时数据为：0
    result = container.Insert(0, 0)
    fmt.Printf("Insert: %t, container.Length:%d\n", result, container.Length())
   //向索引为8插入数据80，插入失败
   //此时数据为：0
    result = container.Insert(8, 80)
    fmt.Printf("Insert: %t, container.Length:%d\n", result, container.Length())
    //此时数据为：10 0
    result = container.Insert(0, 10)
    fmt.Printf("Insert: %t, container.Length:%d\n", result, container.Length())
    container.Range(func(index int, item interface{}) {
        fmt.Printf("index:%d; item:%v\n", index, item)
    })
    //此时数据为：10 20 0
    result = container.Insert(1, 20)
    fmt.Printf("Insert: %t, container.Length:%d\n", result, container.Length())
    //此时数据为：10 20 0 30
    container.Append(30)
    fmt.Printf("Insert: %t, container.Length:%d\n", result, container.Length())
    //此时数据为：50 10 20 0 30
    container.Prepend(50)
    fmt.Printf("Insert: %t, container.Length:%d\n", result, container.Length())
    container.Range(func(index int, item interface{}) {
        fmt.Printf("index:%d; item:%v\n", index, item)
    })
    container.Append(60)
    container.Append(70)
    container.Append(80)
    container.Append(90)
    container.Append(100)
    container.Append(110)
    //单链表无长度限制
    fmt.Printf("container.Length:%d\n", container.Length())
    for i :=0; i < container.Length(); i++ {
        value, _ := container.Get(i)
        fmt.Printf("i:%d; item: %v\n", i, value)
    }
    //删除
    container.Remove(0)
    value, _ := container.Get(0)
    fmt.Printf("i:%d; item: %v\n", 0, value)
    container.Set(9, 999)
    value, _ = container.Get(9)
    fmt.Printf("i:%d; item: %v\n", 9, value)

以上例程运行结果

Insert: false, container.Length:0
Insert: true, container.Length:1
Insert: false, container.Length:1
Insert: true, container.Length:2
index:0; item:10
index:1; item:0
Insert: true, container.Length:3
Insert: true, container.Length:4
Insert: true, container.Length:5
index:0; item:50
index:1; item:10
index:2; item:20
index:3; item:0
index:4; item:30
container.Length:11
i:0; item: 50
i:1; item: 10
i:2; item: 20
i:3; item: 0
i:4; item: 30
i:5; item: 60
i:6; item: 70
i:7; item: 80
i:8; item: 90
i:9; item: 100
i:10; item: 110
i:0; item: 10
i:9; item: 999

时间复杂度