Published on

动态数组实现分析

Authors

在编写程序时，是很难一次就编写好完整的代码，学会将需求拆分成一个个独立的小需求，各个击破，再组合起来，整个程序就完成了。

例子：动态数组

比方说实现一个动态数组，[]int，其实用[]string更好，在编写数据结构时，一定要具象化为生活场景，这样会容易理解很多。

数组是连续的，这是最重要的特性。

在这个数组[1,2,3,4]的2和3中间，插入一个7不好理解，很抽象。换成["橙汁"，"葡萄汁","椰汁","牛奶"]，在葡萄汁和椰汁中间放入一杯柠檬汁，就容易理解多了，数组的每个容器就像一个杯子，杯子里可以放入各种饮料液体。

动态数组至少有以下功能：

  • 插入 在空杯子里加饮料
  • 删除 拿走一杯饮料
  • 扩容 想倒一杯饮料，但是杯子不够了，要加空杯子
  • 索引（从第0杯开始） 想喝牛奶，记得在第3杯，直接去看第3杯取
  • 更新 把杯子里的牛奶换成咖啡

插入

先思考如何实现插入？ 每次插入前检有没有空杯，没有就需要拿新的空杯。（扩容） 刚开始拿到分配的空数组，里面肯定没有任何元素。直接向0号杯装入饮料即可。

如果不是空数组，先用一个小规模的例子，数组里有3个元素 ["牛奶", "茶", "水"]。为什么选择3呢，因为3规模不大容易理解，是奇数，不是0个，1个等特殊情况。

index索引012
size序号123
数组牛奶茶水

可以发现，size刚好是数组间的缝隙，插入的时候，选择缝隙插入。 0 牛奶 1 茶 2 水 3

这里可以分为：

  • 在头部插入
  • 从中间插入
  • 从尾部插入

每次插入前都要考虑需不需要扩容，就不重复说了 每次插入数组的size都要加1

从尾部插入

这个是最简单的，数组的长度size，表示最后一个元素的缝隙，直接插入即可。

从头部插入

[牛奶 , 茶 , 水 ]，那牛奶要空出来，往后挪。如果牛奶直接往后挪会覆盖掉茶，那么应该从最后水开始挪，直到牛奶被挪到茶的位置结束。

[ , 牛奶, 茶, 水]变成这样，再向index为0的位置，放入新的元素。

[柠檬汁, 牛奶, 茶, 水]

从中间插入

[牛奶 , 茶 , 水 ], 比如要从在茶前面插入一杯新的饮品，那就需要将茶和水往后挪，是不是跟从头部插入很像？

头部插入是特殊的中间插入，可以归纳为同一类。

只不过头部插入的缝隙是0,中间插入的缝隙是除0和尾之外的其他任意位置。

[ 牛奶, , 茶, 水]变成这样，再向index为1的位置，放入新的元素。

[ 牛奶, 柠檬汁, 茶, 水]

删除

[牛奶 , 茶 , 水 ] 先观察下，删除水，其他元素是不用挪动位置的，删除其余位置的元素，都要挪动位置，那么可以分归纳为两类。

每次删除，size要减1

尾部删除

size记录了数组的长度，元素的个数，那么只需要将size-1，就等于删除了尾部元素，因为访问的时候，index的合法区间是0到size-1（为什么是size-1可以看上面的表格），每次访问前，先做判断是否超出范围。

其余位置删除

[牛奶 , 茶 , 水 ] 删除头部，或者中间元素时，都需要将后面的元素往前挪，那么从需要删除的那个元素开始。

比如删除牛奶，那么将茶挪到牛奶的位置，将牛奶倒掉，把茶倒入牛奶的杯子，完成。再把水倒入茶的杯子。

扩容

想倒新饮料时，杯子不够了，怎么办？加入新的空杯子，用一个名词（变量）cap来记录。

size表示有多少杯饮料，cap表示有多少个杯子，装没装饮料的都要算。

如果次倒饮料都要去拿杯子，很累很麻烦，通常做法是只要发现杯子不够了，直接拿跟之前一样的杯子（扩容两倍），免得反复跑浪费力气。

每次扩容完，要更新cap的值

索引

记得第2杯（这里说的是index）装的是水，那么直接拿第2杯来用，速度很快（这里有点哈希表的意思了）。

为了防止记忆出错，出现非法访问的情况，每次访问前要判断下，index在不在合法的区间0~size-1。

更新

数组更新特别简单，因为可以直接通过index访问，直接替换调原来的就可以了。把第0杯的牛奶，换成咖啡，完成。

边界情况

首先要有cap（杯子才能装东西），它的大小影响size，index。最小为0，啥也不能装，最大就看分配多少了，理论上不能超过系统规定进程可分配栈的上限。

size 最小为0，最大不能超过cap，因为不可能没有杯子还能装东西。

index=size-1 最小为0不得为负，最大为size-1，索引从0开始，size是统计个数，从1开始。

代码实现

package dynamic_arr

import (
	"fmt"
)

type DynamicArr struct {
	size int
	data []any
}

const INIT_CAP = 1

func NewDynamicArr() *DynamicArr {
	return &DynamicArr{
		size: 0,
		data: make([]any, INIT_CAP),
	}
}

func (l *DynamicArr) TailInsert(value any) error {
	if l.size == l.Cap() {
		l.Resize()
	}
	l.data[l.size] = value
	l.size++

	return nil
}

func (l *DynamicArr) HeadInsert(value any) error {
	if l.size == l.Cap() {
		l.Resize()
	}

	if l.size == 0 {
		err := l.TailInsert(value)
		return err
	}

	for i := l.size; i > 0; i-- {
		l.data[i] = l.data[i-1]
	}
	l.data[0] = value
	l.size++

	return nil
}

func (l *DynamicArr) Insert(index int, value any) error {

	if l.isPositionIndex(index) != true {
		return fmt.Errorf("illegal index")
	}

	if index == 0 {
		if err := l.HeadInsert(value); err != nil {
			return err
		}
	} else if index == l.size {
		if err := l.TailInsert(value); err != nil {
			return err
		}
	}

	if l.size == l.Cap() {
		l.Resize()
	}

	for i := l.size; i > index; i-- {
		l.data[i] = l.data[i-1]
	}
	l.data[index] = value
	l.size++

	return nil
}

func (l *DynamicArr) Remove(index int) error {

	if l.size == 0 {
		return fmt.Errorf("has none elements in array")
	}

	if l.isElementIndex(index) != true {
		return fmt.Errorf("illeagl index %v", index)
	}

	for i := index; i < l.size-1; i++ {
		l.data[i] = l.data[i+1]
	}

	l.size--

	return nil
}

func (l *DynamicArr) HeadRemove() error {
	err := l.Remove(0)
	if err != nil {
		return fmt.Errorf("HeadRemove: %v", err)
	}

	return nil
}

func (l *DynamicArr) TailRemove() error {
	err := l.Remove(l.size - 1)
	if err != nil {
		return err
	}
	return nil
}

func (l *DynamicArr) Update(index int, value any) error {
	if l.isElementIndex(index) != true {
		return fmt.Errorf("illeagl index %v", index)
	}

	l.data[index] = value
	return nil
}

func (l *DynamicArr) Get(index int) (any, error) {
	if l.isElementIndex(index) != true {
		return nil, fmt.Errorf("illeagl index %v", index)
	}

	return l.data[index], nil
}

func (l *DynamicArr) Data() []interface{} {
	return l.data[:l.size]
}

func (l *DynamicArr) Size() int {
	return l.size
}

func (l *DynamicArr) Cap() int {
	return len(l.data)
}

func (l *DynamicArr) Resize() {
	tmp := make([]any, l.Cap()*2)
	copy(tmp, l.data)
	l.data = tmp
	tmp = nil
}

func (l *DynamicArr) isElementIndex(index int) bool {
	return index >= 0 && index < l.size
}

func (l *DynamicArr) isPositionIndex(index int) bool {
	return index >= 0 && index <= l.size
}
Discuss on Twitter • View on GitHub