数据结构-数组

发表于 | 更新于 | 分类于

案例

ArrayList 基于数组实现,涉及到动态扩容,数组拷贝。

插入数据

  • 尾部插入 时间复杂度 O（1），数组扩容

  • 中部/头部插入，查找是O(1),插入存在数组拷贝

ArrayList.set方法会先判断数组真实数据size长度,而非数组构造方法长度。

btw:数组分配的内存空间是连续地址段，由于CPU二级缓存的存在,ArrayList的性能，多数情况下超过linkedList(双向链表实现,非数组)

如果不需要首位的频繁插入,基本不考虑使用LinkedList