数据结构之数组

数组是一种线性数据结构。

特点：

-  一组连续的内存空间，来存储一组具有相同类型的数据。

时间复杂度：

- 查找： O(1)
- 插入： O(n)
- 删除： O(n)

代码实现：

定义基本的数组结构：

type Array struct {
  data []int 
  length uint 
}

func NewArray(capacity uint) *Array {
  if capacity == 0 {
      return nil 
  }
  return &Array{
      data: make([]int, capacity, capacity),
      length: 0,
  }
}

数组的长度：

func (this *Array) Len() uint {
    return this.length
}

是否越界：

func (this *Array) isIndexOutOfRange(index uint) bool {
    if index >= uint(cap(this.data)){
        return true
    }
    return false
}

数据插入：

func (this *Array) Insert(index uint, v int) error {
    // 判断是否满了
    if this.Len() == uint(cap(this.data)) {
        return errors.New("full array")
    }
    // 判断插入位置是否插入到尾部
    if index != this.length && this.isIndexOutOfRange(index) {
        return errors.New("out of index range")
    }
    
    for i:= this.length; i > index; i-- {
        // index后的数据后移空出位置
        this.data[i] = this.data[i-1]
    }
    
    this.data[index] = v 
    this.length++
    return nil 
}

func (this *Array) InsertToTail(v int) error {
    // 尾部插入
    return this.Insert(this.Len(), v)
} 

删除操作：

func (this *Array) Delete(index uint) (int, error) {
    if this.isIndexOutOfRange(index) {
        return 0, errors.New("out of index range")
    }
    v := this.data[index]
    for i:= index; i <this.Len() -1; i++ {
        this.data[i] = this.data[i+1]
    }
    this.length--
    return v, nil 
}

数据打印：

 func (this *Array) Print() {
//   只要实现了Print方法，fmt.Print时就会调用此方法
    var format string
    format += fmt.Sprintf("%+v", this.data[0])
    for i:= uint(1); i< this.Len(); i++ {
        format += fmt.Sprintf("=>%+v", this.data[i])
        fmt.Println(format)
    }
}

这样基本上就实现了golang版本的Array的插入删除和下标取值的基本操作，
在Array实现的过程中，最重要的是警惕下标越界。