Go数据结构---可变长数组

三、可变长数组

因为数组大小是固定的，当数据元素特别多时，固定的数组无法储存这么多的值，所以可变长数组出现了，这也是一种数据结构。在 Golang语言中，可变长数组被内置在语言里面：切片 slice。

slice 是对底层数组的抽象和控制。它是一个结构体：

type slice struct {
    array unsafe.Pointer
    len   int
    cap   int
}

1. 指向底层数组的指针。( Golang 语言是没有操作原始内存的指针的，所以 unsafe 包提供相关的对内存指针的操作，一般情况下非专业人员勿用)
2. 切片的真正长度，也就是实际元素占用的大小。
3. 切片的容量，底层固定数组的长度。

每次可以初始化一个固定容量的切片，切片内部维护一个固定大小的数组。当 append 新元素时，固定大小的数组不够时会自动扩容，如：

package main
import "fmt"
func main() {
    // 创建一个容量为2的切片
    array := make([]int, 0, 2)
    fmt.Println("cap", cap(array), "len", len(array), "array:", array)
    // 虽然 append 但是没有赋予原来的变量 array
    _ = append(array, 1)
    fmt.Println("cap", cap(array), "len", len(array), "array:", array)
    _ = append(array, 1)
    fmt.Println("cap", cap(array), "len", len(array), "array:", array)
    _ = append(array, 1)
    fmt.Println("cap", cap(array), "len", len(array), "array:", array)
    fmt.Println("-------")
    // 赋予回原来的变量
    array = append(array, 1)
    fmt.Println("cap", cap(array), "len", len(array), "array:", array)
    array = append(array, 1)
    fmt.Println("cap", cap(array), "len", len(array), "array:", array)
    array = append(array, 1)
    fmt.Println("cap", cap(array), "len", len(array), "array:", array)
    array = append(array, 1, 1, 1, 1)
    fmt.Println("cap", cap(array), "len", len(array), "array:", array)
    array = append(array, 1, 1, 1, 1, 1, 1, 1, 1, 1)
    fmt.Println("cap", cap(array), "len", len(array), "array:", array)
}

1、实现可变长数组

实现一个简单得，存放整数的，可变长得数组版本。

这里会使用切片的部分功能来代替数组，虽然切片本身是可变长数组，但是我们不会用到它的 append 功能，只把它当数组用。

package main

import "sync"

// Array 定义可变常数组
type Array struct {
	array []int //固定大小得数组，用切片来进行
	len   int
	cap   int
	lock  sync.Mutex
}

// 1.初始化数组
func make(len, cap int) *Array {
	s := new(Array)
	if len > cap {
		panic("len large than cap")
	}
	//把切片当数组使用
	array := make([]int, cap, cap)
	//元数据

	s.array = array
	s.cap = cap
	s.len = 0
	return s

}

// Append 2.添加数组 方法(可以有指针类型，也有值类型)
func (a *Array) Append(element int) {
	//并发锁
	a.lock.Lock()
	defer a.lock.Unlock()

	//大小与容量相等，无为之进行多余增加
	if a.len == a.cap {
		//没有容量，那进行扩容吧
		newCap := 2 * a.len
		if a.cap == 0 {
			newCap = 1
		}
		newArray := make([]int, newCap, newCap)
		//newArray 将老数组的数据移动到新数组上
		for k, v := range a.array {
			newArray[k] = v
		}
		//替换数组
		a.array = newArray
		a.cap = newCap
	}
	//将元素放入新数组
	a.array[a.len] = element
	//并且长度+1
	a.len += 1
}

// 1.3获取指定下表的元素
// Get 获取某个下标的元素
func (a *Array) Get(index int) int {
	//讨论越界
	if a.len == 0 || index >= a.len {
		panic("index over len")
	}
	return a.array[index]
}
//1.4获取真实长度和容量
//Len 返回真实长度
func (a *Array)Len()int  {
	return a.len
}
//Cap 返回容量
func (a *Array)Cap() int{
	return a.cap
}

func main() {

}

解释如下：

1.对于添加元素：

首先添加一个元素到可变长数组里，会加锁，这样会保证并发安全。然后将值放在数组里：a.array[a.len] = element，然后 len + 1，表示真实大小又多了一个。

当真实大小 len = cap 时，表明位置都用完了，没有多余的空间放新值，那么会创建一个固定大小 2*len 的新数组来替换老数组：a.array = newArray，当然容量也会变大：a.cap = newCap。如果一开始设置的容量 cap = 0，那么新的容量会是从 1 开始。

添加元素中，耗时主要在老数组中的数据移动到新数组，时间复杂度为：O(n)。当然，如果容量够的情况下，时间复杂度会变为：O(1)。

补充添加多个元素：

// AppendMany 增加多个元素
func (a *Array) AppendMany(element ...int) {
    for _, v := range element {
        a.Append(v)
    }
}