阅读 770

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 同理。

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

结论

实现方式 应用场景 扩容方式 最大长度
ArrayList 动态数组 读取 1.5倍 2147483639
LinkedList 链表 插入、删除 正常插入末尾 看内存:无限大
插入删除元素时间复杂度 读取元素时间复杂度
ArrayList O(n) O(1)
LinkedList O(1) O(n)

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