双向链表

双向链表结构如下图

代码实现

package line
type DoubleLinkList struct {
    first  *doubleLinkElement
    length int
}
type doubleLinkElement struct {
    item interface{}
    prev *doubleLinkElement
    next *doubleLinkElement
}
func NewDoubleLinkList() *DoubleLinkList {
    return &DoubleLinkList{}
}
func (this *DoubleLinkList) 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 *DoubleLinkList) Insert(index int, item interface{}) bool {
    if index > this.length || index < 0 {
        return false
    }
    defer func() {
        this.length++
    }()
    current := &doubleLinkElement{
        item: item,
    }
    //头位置，需要更换头指针
    if index == 0 {
        if this.first != nil {
            current.next = this.first
            this.first.prev = current
        }
        this.first = current
        return true
    }
    ele := this.first
    for i := 0; i < index-1; i++ {
        ele = ele.next
    }
    //将索引位置的上一元素变为当前元素的上一元素
    current.prev = ele
    //将索引位置元素变为当前元素的下一元素
    current.next = ele.next
    if ele.next != nil && ele.next.next != nil {
        //索引位置下一元素的上个元素变为当前元素
        ele.next.next.prev = current
    }
    //索引位置上一元素的下个元素变为当前元素
    ele.next = current
    return true
}
func (this *DoubleLinkList) Lpush(item interface{}) {
    this.Insert(0, item)
}
func (this *DoubleLinkList) Rpush(item interface{}) {
    this.Insert(this.length, item)
}
func (this *DoubleLinkList) Set(index int, item interface{}) bool {
    if index > this.length || index < 0 {
        return false
    }
    current := &doubleLinkElement{
        item: item,
    }
    if index == 0 {
        if this.length == 0 {
            this.length++
        } else {
            current.next = this.first.next
            if this.first.next != nil {
                this.first.next.prev = current
            }
        }
        this.first = current
        return true
    }
    ele := this.first
    for i := 0; i < index-1; i++ {
        ele = ele.next
    }
    current.prev = ele
    if ele.next == nil {
        this.length++
        ele.next = current
        return true
    }
    ele.next = current
    current.next = ele.next.next
    ele.next.prev = current
    return true
}
func (this *DoubleLinkList) Length() int {
    return this.length
}
func (this *DoubleLinkList) Remove(index int) *doubleLinkElement {
    if this.length == 0 || index > this.length-1 || index < 0 {
        return nil
    }
    defer func() {
        this.length--
    }()
    ele := this.first
    if index == 0 {
        this.first = this.first.next
        if this.first != nil {
            this.first.prev = nil
        }
        return ele
    }
    for i := 0; i < index; i++ {
        ele = ele.next
    }
    ele.prev.next = ele.next
    if ele.next != nil {
        ele.next.prev = ele.prev
    }
    return ele
}
func (this *DoubleLinkList) Lpop() *doubleLinkElement {
    return this.Remove(0)
}
func (this *DoubleLinkList) Rpop() *doubleLinkElement {
    return this.Remove(this.length - 1)
}
func (this *DoubleLinkList) Range(f func(index int, item interface{})) {
    ele := this.first
    for i := 0; i < this.length; i++ {
        f(i, ele.item)
        ele = ele.next
    }
}

测试

package line
import (
    "testing"
    "time"
)
func TestDoubleLinkList_Insert(t *testing.T) {
    double := NewDoubleLinkList()
    result := double.Insert(1, time.Now().Unix())
    if result {
        t.Fatalf("want false, got %#v", result)
    }
    result = double.Insert(0, 1)
    if !result {
        t.Fatalf("want true, got %#v", result)
    }
    length := double.Length()
    if length != 1 {
        t.Fatalf("want 1, got %#v", length)
    }
    result = double.Insert(0, 2)
    if !result {
        t.Fatalf("want true, got %#v", result)
    }
    result = double.Insert(1, 3)
    if !result {
        t.Fatalf("want true, got %#v", result)
    }
    length = double.Length()
    if length != 3 {
        t.Fatalf("want 3, got %#v", length)
    }
    r0, _ := double.Get(0)
    if r0 != 2 {
        t.Fatalf("want 2, got %#v", r0)
    }
    r1, _ := double.Get(1)
    if r1 != 3 {
        t.Fatalf("want 3, got %#v", r1)
    }
    r2, _ := double.Get(2)
    if r2 != 1 {
        t.Fatalf("want 2, got %#v", r2)
    }
}
func TestDoubleLinkList_Pushpop(t *testing.T) {
    double := NewDoubleLinkList()
    double.Lpush(5)
    double.Lpush(4)
    double.Lpush(3)
    double.Lpush(2)
    double.Lpush(1)
    double.Rpush(6)
    double.Rpush(7)
    double.Rpush(8)
    double.Rpush(9)
    double.Rpush(10)
    for i := 1; i < 11; i++ {
        item := double.Lpop()
        if item.item.(int) != i {
            t.Fatalf("want %d; got %#v", i, item.item)
        }
    }
    if double.Length() != 0 {
        t.Fatalf("want 0, got %#v", double.Length())
    }
    double.Range(func(index int, item interface{}) {
        t.Fatalf("not run")
    })
    double.Rpush(6)
    double.Rpush(7)
    double.Rpush(8)
    double.Rpush(9)
    double.Rpush(10)
    if double.Length() != 5 {
        t.Fatalf("want 5, got %#v", double.Length())
    }
    for i := 10; i > 5; i-- {
        item := double.Rpop()
        if item.item.(int) != i {
            t.Fatalf("want %d; got %#v", i, item.item)
        }
    }
    if double.Length() != 0 {
        t.Fatalf("want 0, got %#v", double.Length())
    }
}
func TestDoubleLinkList_Set(t *testing.T) {
    double := NewDoubleLinkList()
    double.Set(0, 0)
    double.Set(1, 1)
    double.Set(2, 2)
    double.Set(3, 3)
    for i := 0; i < 4; i++ {
        item := double.Lpop()
        if item.item.(int) != i {
            t.Fatalf("want %d; got %#v", i, item.item)
        }
    }
}

时间复杂度