lists

首先我们从最基本的线性表开始看起，线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。众所周知线性表分为数组和链表，先规定一些线性表都需要的方法

type List interface {
    Get(index int) (interface{}, bool)
    Remove(index int)
    Add(values ...interface{})
    Contains(values ...interface{}) bool
    Sort(comparator utils.Comparator)
    Swap(index1, index2 int)
    Insert(index int, values ...interface{})
    Set(index int, value interface{})
    containers.Container
}

Array

struct

type List struct {
    elements []interface{}
    size     int
}

数组的底层是一个切片，size 表示切片内占有数据的数量，但是我们知道切片的底层是有 size 这个字段的，这个 size 不是多次一举吗？

这个 size 这里是用来控制底层数组的长度的，因为使用中需要对数据进行添加或者移除，但是这时的 size 并不会随之改变，而且如果这个时候底层数组大小不够了怎么办，或者容量远远大于所存储的数据，浪费空间，所以我们需要对切片中存储的数量进行存储，来保证数组大小符合我们的要求。

众所周知频繁的进行空间分配是很消耗时间的操作，所以我们不可能每增加一个数据就分配空间，而是应该提前预留一部分空间进行分配，同样我们也需要在数据少于一定限度的时候缩减数组大小。 growthFactor 默认大小为 2.0，也就是每次将要插入的数据大于所有数据的时候就会将底层数组扩大为插入后的两倍。

func (list *List) growBy(n int) {
    currentCapacity := cap(list.elements)
    if list.size+n >= currentCapacity {
        newCapacity := int(growthFactor * float32(currentCapacity+n))
        list.resize(newCapacity)
    }
}
func (list *List) resize(cap int) {
    newElements := make([]interface{}, cap, cap)
    copy(newElements, list.elements)
    list.elements = newElements
}

同样我们也需要在数据少于一定限度的时候缩减数组大小。这个函数会在每次进行移除数据之后被调用， shrinkFactor 的默认大小是 0.25.

func (list *List) shrink() {
    if shrinkFactor == 0.0 {
        return
    }
    currentCapacity := cap(list.elements)
    if list.size <= int(float32(currentCapacity)*shrinkFactor) {
        list.resize(list.size)
    }
}

insert

为了保证数组必须是首尾相接，没有空余的，我们进行插入的时候，需要将这一位之后的所有数据都向后移动，删除也需要向前移动填补这个空缺，所以删除和插入需要花费的时间都比较长。

    l := len(values)
    list.growBy(l)
    list.size += l
    copy(list.elements[index+l:], list.elements[index:list.size-l])
    copy(list.elements[index:], values)

特别的，如果插入的 index 超过了数组的 size ，也可以插入成功，不过是直接将这个数据插入到数组的最后，而不是返回错误信息。同样 set 的结果也是如此。

SingleLink

struct

type List struct {
    first *element
    last  *element
    size  int
}
type element struct {
    value interface{}
    next  *element
}

按理说，链表并没有底层的数组，不需要扩容，也就不需要存储 size 而且需要进行遍历的时候如果每次都需要与 nil 进行比较，同样影响效率，所以还是使用 size 存储了数据的数量，每次对 index 进行操作的时候，先检查一遍是否存在，就不需要担心超出界限了。
而且在执行的最开始就否定了没有结果的情况，不会出现需要遍历整个链表发现链表长度不够的情况，大大减少了时间的浪费。
遍历的条件也可以改为for element := list.first; element != nil; element = element.next

func (list *List) withinRange(index int) bool {
    return index >= 0 && index < list.size
}

而 last 是为了方便在尾部插入的时候，不需要从头开始遍历整个链表，大大提高了效率

sort

链表的排序操作比较特殊，他不能像数组一样直接操纵底层数组，而是先使用 Value() 获取所有的数据，然后将这个切片进行排序，清空原有结构体，然后再新增进去。

func (list *List) Sort(comparator utils.Comparator) {
    if list.size < 2 {
        return
    }
    values := list.Values()
    utils.Sort(values, comparator)
    list.Clear()
    list.Add(values...)
}

contain

对于链表来说插入是很相对简单的事，只需要定位到需要插入的位置，然后改变指针的指向就可以了，而因为这里存储了最后的一个数据，所以向尾部进行添加也变得很简单了，比数组慢的就只有通过索引进行查找了，最坏的情况下链表需要遍历整个结构，才能够发现这个结构体，这里的实现是这样的，而相对于数组只需要常数时间就慢很多了

func (list *List) Get(index int) (interface{}, bool) {
    if !list.withinRange(index) {
        return nil, false
    }
    element := list.first
    for e := 0; e != index; e, element = e+1, element.next {
    }
    return element.value, true
}
func (list *List) Get(index int) (interface{}, bool) {
    if !list.withinRange(index) {
        return nil, false
    }
    return list.elements[index], true
}

其实我们已经存储了最后一个数据，如果可以从后向前进行查找最坏的情况也能够缩短一半的时间

DoubleLink

struct

type List struct {
    first *element
    last  *element
    size  int
}
type element struct {
    value interface{}
    prev  *element
    next  *element
}

相比于单链表唯一增加的就是每个单位上的 prev 它指向的就是前一个数据，这让我们的使用方法更灵活

get

新的 get() 方法通过检查 list.size-index 和 index 的相对大小，判断检查进行的方向

func (list *List) Get(index int) (interface{}, bool) {
    if !list.withinRange(index) {
        return nil, false
    }
    if list.size-index < index {
        element := list.last
        for e := list.size - 1; e != index; e, element = e-1, element.prev {
        }
        return element.value, true
    }
    element := list.first
    for e := 0; e != index; e, element = e+1, element.next {
    }
    return element.value, true
}