比如,在一个已经添加了0 1 2 3 4的ArrayList中进行add(5)操作,首先进行扩容检查ensureCapacity(size + 1),然后把5放在下标为5的位置,把size指针往后移动。正果时间复杂度为O(1)。
假如进行add(2,6),要在数组下标为2的位置插入6这个元素,首先会进行边界检查防止插入位置不合法,然后进行扩容检查,之后会把2,3,4,5往后复制,复制之后index为2的位置还是2,此时把6替换2,size指针任然要往后移动。整个过程时间空间复杂度都是O(n).
如上代码,在一个已有元素【0,1,2,3,4,5,6】的列表删除数组下标为2的元素,首先会检查下标范围是否合法,然后把index后面的数都向前移动复制一位。最后把原来数组末尾指针指向null;
remove(object)
这个方法首先会从elementData数组里边从头到尾遍历寻找该对象,然后会调用fastRemove方法进行删除,fastRemove方法和remove方法大同小异时间复杂度仍然是O(n)。
get是对数组的随即访问,肯定时间复杂度为O(1)
index是对对象的顺序查找,时间复杂度为O(n)
set是对数组的随机修改,直接操作数组,时间复杂度为O(1)