ArrayList的实现原理-阿里云开发者社区

ArrayList的实现原理

2017-11-07 925

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介：

ArrayList的线性复杂度是1.想确定一个数据,直接通过索引进行访问.实际上这个过程和数组是非常相似的.ArrayList在整个使用过程中,如果想要高效操作,最好设置一个数组的大小.
在个数固定的情况下,ArrayList里面避免了重复开辟空间的问题,所以当你确定数据个数的时候,就使用ArrayList.
如果不确定的时候就使用LinkedList(链表实现). 时间复杂度是N ,而ArrayList最底层的原理就是一个数组的动态操作.
数组本身的最大问题在于数组的容量是固定的,而ArrayList通过自己的算法实现动态扩增.

ArrayList的add方法:

 1     public boolean add(E e) {
 2         ensureCapacityInternal(size + 1);  // Increments modCount!!
 3         elementData[size++] = e;
 4         return true;
 5     }
 6      private void ensureCapacityInternal(int minCapacity) {
 7         if (elementData == EMPTY_ELEMENTDATA) {
 8             minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
 9         }
10 
11         ensureExplicitCapacity(minCapacity);
12     }
13     private void ensureExplicitCapacity(int minCapacity) {
14         modCount++;
15 
16         // overflow-conscious code
17         if (minCapacity - elementData.length > 0)
18             grow(minCapacity);
19     }

ArrayList是一个相对来说比较简单的数据结构，最重要的一点就是它的自动扩容，可以认为就是我们常说的“动态数组”。
我们可以看到他的实现其实最核心的内容就是ensureCapacityInternal。这个函数其实就是自动扩容机制的核心。我们依次来看一下他的具体实现
也就是说，当增加数据的时候，如果ArrayList的大小已经不满足需求时，那么就将数组变为原长度的1.5倍，之后的操作就是把老的数组拷到新的数组里面。例如，默认的数组大小是10，也就是说当我们add10个元素之后，再进行一次add时，就会发生自动扩容，数组长度由10变为了15.

本文转自SummerChill博客园博客，原文链接：http://www.cnblogs.com/DreamDrive/p/7513664.html，如需转载请自行联系原作者

文章标签：

算法