算法学习之动态数组类

算法学习之动态数组

一、整型动态数组

数组操作逻辑代码实现

数组操作测试

二、使用泛型

让我们的数据结构可以放置“任何”数据类型
不可以是基本数据类型,只能是类对象
boolean,byte , char,short,int,long,float,double
每个基本数据类型都有对应的包装类
Boolean,Byte,Char,Short , Int , Long,Float,Double

需要改动的地方:
1、声明数组的方式,不再只是int

2、传入参数类型改变

3、值比较与引用比较

4、声明存放数据类型

修改后的泛型数组代码

泛型数组操作代码

三、动态数组

当数组的长度大于数组实际的个数的时候,多余的空间就会浪费,可以自动调用方法使数组长度变小。
一般采取2倍的操作,扩容2倍或者缩小2倍。

四、复杂度震荡

当长度刚好是数组长度时,增加一个和删除一个末尾的元素都需要扩容,时间复杂度都是O(n),在这个极端情况下产生的复杂度变化称为复杂度震荡。解决的方式就是懒处理,当元素在原来的1/4时缩小一半。