.-. .-
.-,.--..-,.--. \ \ / /
__ | .-. | .-. | __ \ \ / /
.:--.'. | | | | | | |.:--.'. \ \ / /
/ | \ || | | | | | / | \ | \ \ / /
`" __ | || | '-| | '-`" __ | | \ ` /
.'.''| || | | | .'.''| | \ /
/ / | || | | | / / | |_ / /
\ \._,\ '|_| |_| \ \._,\ '|`-' /
`--' `" `--' `" '..' Golang
Online Go tutorial
1.1 原理
数组（Array）是一种线性表数据结构，通过在内存中申请一组连续的存储空间，用于存储一系列具有相同类型的数据。
而除了数组，链表、栈、队列都是线性表结构。
根据下标实现随机访问
计算机会给每个内存单元分配一个地址，然后通过这个地址来访问内存中的数据，访问数组中的元素时候，会根据如下寻址公式来访问：
$$ a[i]\_address = base\_address + i * data\_type\_size $$
其中 $a[i]\_address$ 表示a[i]的地址，$base\_address$ 表示计算机分配的数组的地址，$data\_type\_size$表示数组中每个元素的大小，如果数据类型是整型int，那么 $data\_type\_size$ 就等于4字节。
1.2 相关操作与分析
插入
如果需要将一个数据插入到数组的第k个位置，就需要将数组中k~n位置这部分的元素往后挪。
- 如果在数组末尾插入元素，就不需要移动数据，最好时间复杂度为 $O(1)$
- 如果在数组头部插入元素，就需要搬移整个数组，最坏时间复杂度为 $O(n)$
- 假设我们在数组的每个位置插入元素的概率是一样的，则平均时间复杂度为 $(1+2+...n)/n = O(n)$
删除
与插入数据类似
- 最好情况时间复杂度为 $O(1)$
- 最坏情况时间复杂度为 $O(n)$
- 平均情况时间复杂度为 $O(n)$
1.3 思考
- 为什么大多数编程语言中的数据要从0开始编号，而不是从1开始？
- 数组与链表的区别？
- 在编程中直接使用数组还是使用编程语言提供的容器类（如Java中的ArrayList、C++STL中从Vector），容器类有哪些优劣呢？
- *了解JVM中的标记清除垃圾回收算法原理与数组的关系？
- *散列表的原理，散列表的查询时间复杂度？
1.4 LeetCode练习
1.5 简单实现
package main
import "fmt"
type Array interface {
Get(i int) interface{}
Set(i int, element interface{})
Len() int
Remove(i int)
Insert(i int, element interface{})
// 辅助测试，打印
Print()
}
type array struct {
data []interface{}
}
func (a *array) Print() {
fmt.Println(a.data)
}
func (a *array) Get(i int) interface{} {
return a.data[i]
}
func (a *array) Set(i int, element interface{}) {
a.data[i] = element
}
func (a *array) Len() int {
return len(a.data)
}
func (a *array) Remove(i int) {
for ; i < a.Len() - 1; i++ {
a.data[i] = a.data[i+1]
}
a.data = a.data[:a.Len()-1]
}
func (a *array) Insert(i int, element interface{}) {
a.data = append(a.data, 0)
for j:= a.Len()-1; j > i; j-- {
a.data[j] = a.data[j-1]
}
a.data[i] = element
}
func NewArray(n int) Array {
return &array{data: make([]interface{}, n)}
}
func main() {
// 创建数组
arr := NewArray(3)
arr.Set(0, "hello")
arr.Set(1, "world")
fmt.Println(arr.Get(0))
arr.Print()
arr.Insert(0, "mike")
arr.Print()
arr.Remove(3)
arr.Print()
}
有疑问加站长微信联系（非本文作者）
