数组
数组(Array)是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据
线性表(Linear List)
- 线性表就是数据排成像一条线一样的结构
- 每个线性表上的数据最多只有前和后两个方向
- 数组、链表、队列、栈等都是线性表结构
与它相对应的概念是非线性表，比如二叉树、堆、图等。非线性表指数据之间并不是简单的前后关系
连续的内存空间和相同类型的数据
正因为这两个限制，它才具有“随机访问”
数组是如何实现根据下标随机访问数组元素？
比如长度为10的int类型数组 int[] = new int[10]
计算机给数组a[10]，分配一块连续的内存空间 1000 ~ 1039
其中内存块的首地址是 base_address = 1000
我们知道，计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据
当计算机需要随机访问数组中的某个元素时，它会首先通过寻址公式。
来计算出该元素存储的内存地址
a[i]_address = base_address + i * data_type_size
其中 data_type_size 表示数组中的每个元素的大小
面试题：数组和链表的区别？
数组支持随机访问，根据下标随机访问的时间复杂度为 O(1),二分查找的时间复杂度是 O(logn)
链表适合插入、删除，时间复杂度 O(1)
低效的“插入”
如果在数组的末尾插入元素，不需要移动数据，时间复杂度为 O(1)
在数组的开头插入元素，所有的数据都需要依次往后移动一位，最坏时间复杂度是 O(n)
因为我们在每个位置插入元素的概率是一样的，所以平均情况时间复杂度为(1+2+...+n)/n = O(n)
这里考虑一下，如果数组是有序的，在某个位置插入一个新的元素，就必须移动数据
但是数组中存储的数据并没有任何规律，数组只是作为一个存储数据的集合，在这种情况下
将插入一个新的元素，为了避免大规模的数据搬移，
可以直接将第k位的数据移动到数组元素的最后，把新的元素直接放入第k个位置
利用这种处理技巧，在特定情况下，在第k个位置插入一个元素的时间复杂度就会降为O(1),快排中使用
低效的删除
跟插入数据类似，如果我们要删除第k个位置的数据，为了内存的连续性，也要搬移数据
- 如果删除数组末尾的数据，则最好情况时间复杂度为 O(1)
- 如果删除数组开头的数据，则最坏情况时间复杂度为 O(n)
- 平均情况时间复杂度为 O(n)
某些特殊场景下，不一定非得追求数组中数据的连续性。
如果我们将多次删除操作集中在一起执行，删除的效率会有所提高
例如，数组a[10]中存储了8个元素:a, b, c, d, e, f, g, h。现在要依次删除 a, b, c 三个元素
为了避免 d, e, f, g, h 这几个数据会被搬移三次，可以先记录下已经删除的数据
每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除
当数组没有更多空间存储数据时，我们再触发执行一次真正的删除操作，
这样就大大减少了删除操作导致的数据搬移
这就是 JVM 标记清除垃圾回收算法的核心思想
数据结构和算法的魅力在于，很多时候并不是要去死记硬背某个数据结构或者算法，
而是要学习它背后的思想和处理技巧，这些东西才是最有价值的
不管在软件开发还是架构设计中，总能找到某些算法和数据结构的影子
警惕数组的访问越界问题
首先分析这段C语言代码的运行结果
int main(int argc, char* argv[1]) {
int i = 0;
int arr[3] = {0};
for (; i <= 3; i++){
arr[i] = 0;
printf("hello world
");
}
return 0;
}
数组大小为3，a[0], a[1], a[2]，for 循环的结束条件错写为 i <= 3而非 i < 3，所以当 i=3 时，数组 a[3] 访问越界
Go语言本身就会越界检查，比如下面代码
就会抛出 invalid array index 3 (out of bounds for 3-element array)
a := [3]int{1, 2, 3}
a[3] = 10
容器能否完全代替数组？
针对数组类型，很多语言都提供了容器类，比如Java中的 ArrayList，C++ STL中的 vector
在项目开发中，什么时候适合用数组，什么时候适合用容器呢
- 如果数据大小事先已知，并对数组的操作非常简单，可以直接使用数组
二维数组的内存寻址公式
对于m *n 的数组，a[i][j] (i < m, j < n)的地址为：
a[i][j]_address = base_address + (i*n +j)*type_size
Go语言代码示例
package main
import (
"errors"
"fmt"
)
/**
* int类型数组的插入、删除、根据下标随机访问
*/
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
}
// 通过索引查找数组，索引范围[0, n-1]
func (this *Array) Find(index uint) (int, error) {
if this.isIndexOutOfRange(index) {
return 0, errors.New("out of index range")
}
return this.data[index], nil
}
// 插入数组到索引index上
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-- {
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)
}
// 删除索引index上的值
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() {
var format string
for i := uint(0); i < this.Len(); i++ {
format += fmt.Sprintf("|%+v", this.data[i])
}
fmt.Println(format)
}
测试示例
package main
import "testing"
func TestArray_Insert(t *testing.T) {
capacity := 10
arr := NewArray(uint(capacity))
for i := 0; i < capacity-2; i++ {
err := arr.Insert(uint(i), i+1)
if nil != err {
t.Fatal(err.Error())
}
}
arr.Print() // |1|2|3|4|5|6|7|8
arr.Insert(uint(6), 999)
arr.Print() // |1|2|3|4|5|6|999|7|8
arr.InsertToTail(666)
arr.Print() // |1|2|3|4|5|6|999|7|8|666
}
func TestArray_Delete(t *testing.T) {
capacity := 10
arr := NewArray(uint(capacity))
for i := 0; i < capacity; i++ {
err := arr.Insert(uint(i), i+1)
if nil != err {
t.Fatal(err.Error())
}
}
arr.Print()
for i := 9; i >= 0; i-- {
_, err := arr.Delete(uint(i))
if nil != err {
t.Fatal(err)
}
arr.Print()
}
}
func TestArray_Find(t *testing.T) {
capacity := 10
arr := NewArray(uint(capacity))
for i := 0; i < capacity; i++ {
err := arr.Insert(uint(i), i+1)
if nil != err {
t.Fatal(err.Error())
}
}
arr.Print()
t.Log(arr.Find(0)) // 1 <nil>
t.Log(arr.Find(9)) // 10 <nil>
t.Log(arr.Find(11)) // 0 out of index range
}
运行结果
=== RUN TestArray_Insert
|1|2|3|4|5|6|7|8
|1|2|3|4|5|6|999|7|8
|1|2|3|4|5|6|999|7|8|666
--- PASS: TestArray_Insert (0.00s)
=== RUN TestArray_Delete
|1|2|3|4|5|6|7|8|9|10
|1|2|3|4|5|6|7|8|9
|1|2|3|4|5|6|7|8
|1|2|3|4|5|6|7
|1|2|3|4|5|6
|1|2|3|4|5
|1|2|3|4
|1|2|3
|1|2
|1
--- PASS: TestArray_Delete (0.00s)
=== RUN TestArray_Find
|1|2|3|4|5|6|7|8|9|10
--- PASS: TestArray_Find (0.00s)
array_test.go:54: 1 <nil>
array_test.go:55: 10 <nil>
array_test.go:56: 0 out of index range
PASS