关于java:列表容器ArrayList学习基于Java8

<article class=“article fmt article-content”><h2>概述</h2><p>ArrayList是jdk提供的非线程平安的基于数组的列表容器，是最频繁应用的Java容器之一。本文次要介绍一下ArrayList的内部结构和运行机制。</p><h2>继承与实现</h2><pre><code class=“java”>public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable</code></pre><ol><li><code>ArrayList</code>继承了<code>AbstractList</code>抽象类，<code>AbstractList</code>提供了<code>get</code>,<code>set</code>,<code>add</code>,<code>remove</code>等形象的列表办法，提供给ArrayList或这LinkedList依据底层存储构造具体实现。</li><li><code>ArrayList</code>实现了<code>List</code>接口，这样就能够实例化一个<code>List</code>类型的变量，其具体实现为<code>ArrayList</code>。</li><li><code>RandomAccess</code>只是一个标记接口，没有任何办法，用于示意该类反对疾速随机拜访——能够应用工夫复杂度O(1)拜访任意元素。</li><li><code>Cloneable</code>接口，想应用<code>Object.clone()</code>办法就要实现这个接口。</li><li>Serializable接口，序列化接口。</li></ol><h2>成员变量和办法</h2><pre><code class=“java”>transient Object[] elementData;private int size;</code></pre><p><code>ArrayList</code>底层是一个Object数组，应用size示意一共保留了多少个元素（不等于elemetnData.length)。</p><h3>常见操作</h3><pre><code class=“java”> public E get(int index) { rangeCheck(index); return elementData(index); } public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[–size] = null; // clear to let GC do its work return oldValue; }</code></pre><p>因为底层是数组，增加、拜访和删除操作都比较简单。查看拜访索引或者容量，而后批改数组。</p><h3>扩容</h3><pre><code class=“java”> public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! modCount记录了汇合的批改次数 elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }</code></pre><p>对list进行扩容，<code>newCapacity = oldCapacity + (oldCapacity >> 1)</code>即新容量为原来的1.5倍。如果数组容量大于<code>ArrayList</code>最大容量，无奈再进行扩容。</p><h3>遍历</h3><p><code>Iterator</code>次要的作用是为容器提供一个遍历元素的形式并且屏蔽容器的底层实现。如果没有迭代器，遍历ArrayList就须要拜访其底层数组，遍历LinkedList就须要拜访它的节点，裸露外部细节。<code>Iterator</code>屏蔽了底层细节，其根本应用：</p><pre><code class=“java”> List list = new ArrayList(); for (Iterator i=list.iterator(); i.hasNext();) i.next();</code></pre><p>ArrayList实现了两个外部迭代器类<code>Itr</code>和<code>ListItr</code>，而后通过<code>iterator()</code>和<code>listIterator()</code>返回给用户应用。</p><pre><code class=“java”>private class Itr implements Iterator<E> { int cursor; // index of next element to return int lastRet = -1; // index of last element returned; -1 if no such</code></pre><p><code>cursor</code>指向下一个<code>next()</code>须要返回元素的索引，<code>lastRet</code>指向曾经拜访过的上一个元素的索引，<code>lastRet== -1</code>时代表上一个元素曾经被<code>remove()</code>删除了。<code>next()</code>执行之后迭代器<code>remove()</code>才晓得删除的是什么元素。</p><p>本文是迁徙旧文浅学——ArrayList机制</p></article>