可变长数组

代码实现

package zgo_algorithm

import (
	"fmt"
	"sync"
)

// Array 可变长数组
type Array struct {
	array []int      // 固定大小的数组，用满容量和满大小的切片来代替
	len   int        // 真正长度
	cap   int        // 容量
	lock  sync.Mutex // 为了并发安全使用的锁
}

// MakeArray 新建一个可变长数组
// 时间复杂度为：O(1)，因为分配内存空间和设置几个值是常数时间。
func MakeArray(len, cap int) *Array {
	s := new(Array)
	if len > cap {
		panic("数组的长度不能大于容量")
	}

	// 把切片当数组用
	array := make([]int, cap, cap)

	// 元数据
	s.array = array
	s.cap = cap
	s.len = 0
	return s
}

// Append 增加一个元素
// 添加元素中，耗时主要在老数组中的数据移动到新数组，时间复杂度为：O(n)
func (a *Array) Append(element int) {
	// 并发锁
	a.lock.Lock()
	defer a.lock.Unlock()

	// 大小等于容量，表示没多余位置了
	if a.len == a.cap {
		// 没容量，数组要扩容，扩容到两倍
		newCap := 2 * a.len

		// 如果之前的容量为0，那么新容量为1
		if a.cap == 0 {
			newCap = 1
		}

		newArray := make([]int, newCap, newCap)

		// 把老数组的数据移动到新数组
		for k, v := range a.array {
			newArray[k] = v
		}

		// 替换数组
		a.array = newArray
		a.cap = newCap

	}

	// 把元素放在数组里
	a.array[a.len] = element
	// 真实长度+1
	a.len = a.len + 1

}

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

// Get 获取某个下标的元素
// 因为只获取下标的值，所以时间复杂度为 O(1)
func (a *Array) Get(index int) int {
	// 越界了
	if a.len == 0 || index >= a.len {
		panic("索引超过了长度")
	}
	return a.array[index]
}

// Len 返回真实长度
// 时间复杂度为 O(1)
func (a *Array) Len() int {
	return a.len
}

// Cap 返回容量
// 时间复杂度为 O(1)
func (a *Array) Cap() int {
	return a.cap
}

// 转换为字符串输出，主要用于打印
func (a *Array) ToString() (result string) {
	result = "["
	for i := 0; i < a.Len(); i++ {
		// 第一个元素
		if i == 0 {
			result = fmt.Sprintf("%s%d", result, a.Get(i))
			continue
		}

		result = fmt.Sprintf("%s %d", result, a.Get(i))
	}
	result = result + "]"
	return
}

测试

package zgo_algorithm

import (
	"fmt"
	"testing"
)

func TestArray(t *testing.T) {
	// 创建一个容量为3的动态数组
	a := MakeArray(0, 3)
	fmt.Println("cap", a.Cap(), "len", a.Len(), "array:", a.ToString())

	// 增加一个元素
	a.Append(10)
	fmt.Println("cap", a.Cap(), "len", a.Len(), "array:", a.ToString())

	// 增加一个元素
	a.Append(9)
	fmt.Println("cap", a.Cap(), "len", a.Len(), "array:", a.ToString())

	// 增加多个元素
	a.AppendMany(8, 7)
	fmt.Println("cap", a.Cap(), "len", a.Len(), "array:",a.ToString())

}

输出结果

=== RUN   TestArray
cap 3 len 0 array: []
cap 3 len 1 array: [10]
cap 3 len 2 array: [10 9]
cap 6 len 4 array: [10 9 8 7]
--- PASS: TestArray (0.00s)
PASS