ArrayList与LinkedList的实现和区别

写在前面的话

ArrayList与LinkedList的实现和区别

都是 List 的实现，一个数组实现一个链表实现，直奔源码，先看类：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, Serializable
{...}

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, Serializable
{

先从实现初看端倪

RandomAccess

首先一眼发现双方继承的 List 都挺像的，一个是 AbstractSequentialList 一个是 AbstractList 类。都是 1300 多行代码，先看哪个都差不多，先看 ArrayList 他实现了个 RandomAccess LinkedList 却没有实现

package java.util;

/**
 * Marker interface used by <tt>List</tt> implementations to indicate that
 * they support fast (generally constant time) random access.  The primary
 * purpose of this interface is to allow generic algorithms to alter their
 * behavior to provide good performance when applied to either random or
 * sequential access lists.
 *
 * <p>The best algorithms for manipulating random access lists (such as
 * <tt>ArrayList</tt>) can produce quadratic behavior when applied to
 * sequential access lists (such as <tt>LinkedList</tt>).  Generic list
 * algorithms are encouraged to check whether the given list is an
 * <tt>instanceof</tt> this interface before applying an algorithm that would
 * provide poor performance if it were applied to a sequential access list,
 * and to alter their behavior if necessary to guarantee acceptable
 * performance.
 *
 * <p>It is recognized that the distinction between random and sequential
 * access is often fuzzy.  For example, some <tt>List</tt> implementations
 * provide asymptotically linear access times if they get huge, but constant
 * access times in practice.  Such a <tt>List</tt> implementation
 * should generally implement this interface.  As a rule of thumb, a
 * <tt>List</tt> implementation should implement this interface if,
 * for typical instances of the class, this loop:
 * <pre>
 *     for (int i=0, n=list.size(); i &lt; n; i++)
 *         list.get(i);
 * </pre>
 * runs faster than this loop:
 * <pre>
 *     for (Iterator i=list.iterator(); i.hasNext(); )
 *         i.next();
 * </pre>
 *
 * <p>This interface is a member of the
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @since 1.4
 */
public interface RandomAccess {
}

该接口的主要目的是允许通用算法更改其行为，以便在应用于随机访问或顺序访问列表时提供良好的性能.他只是一个标志性接口，做标注用的，1.5后一般都用注解来做这个事情。表明实现这个这个接口的 List 集合是支持 快速随机访问 的

实现了这个接口的 list 实例使用 for 会比使用 Iterator 更快！

出自上面的注释

所以我们得出第一点结论：ArrayList 支持 快速随机访问，LinkedList 不支持 。

ArrayList 随机访问很快， LinkedList「链表」 插入删除很快

qeue

扩容角度

• ArrayList 扩容

先给 ArrayList 个初始长度：

List a  = new ArrayList<>(4);

ArrayList 内部会产生一个等长的 Object 数组 elementData，每次 add 的时候都会检测是否需要扩容：

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        // add后的长度 - 当前容量 > 0
        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);
    }

 int oldCapacity = elementData.length;
 int newCapacity = oldCapacity + (oldCapacity >> 1);

通过代码可知，每次扩容为旧的1.5倍。切最大长度不超过 2147483639

• LinkedList

List a  = new LinkedList();

LinkedList「链表」不能初始化开辟容量，因为 LinkedList 数据结构需要两两相连，做不到初始化给定长度。

由此可见链表的独特结构比数组要更占内存

源码：

 public boolean add(E e) {
        linkLast(e);
        return true;
    }
    
    
 void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }   

链表源码更简单，定义经典的节点（Node）结构追加到链表尾部，链表长度 +1, addFirst 、addLast 同理。

所以链表不需要提前扩容，不怕越界，随用随插即可。理论上没有边界。

结论

原文链接：github.com/pkwenda/Blo…