ArrayList与LinkedList源码分析-从源码角度分析数组与链表的区别

ArrayList与LinkedList都是线性表，是可以储存具有相同特性的数据元素的有限序列。但它们内部实现是截然不同的，分别代表了数组和链表的两种实现，这也注定了它们算法的时间复杂度与空间复杂度是不一样的，需要择优使用在不同的场景。接下来将源码（JDK1.8）细节去分析它们的差异。

ArrayList源码分析

  • 无参构造函数
transient Object[] elementData;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

elementData是一个Object数组，使用transient关键字修饰,transient关键字与Serializable接口配合使用，使用transient关键字修饰的变量不会被序列化。

  • int参数构造
private static final Object[] EMPTY_ELEMENTDATA = {};
public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

当传入的initialCapacity大于0时，初始化一个长度为initialCapacity的Object数组

  • Collection参数构造
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

public interface Collection<E> extends Iterable<E> {
    Object[] toArray();
    <T> T[] toArray(T[] a);
}

Collection是一个接口，List、Set、Queue接口继承自Collection接口，所以这里的参数c可以是List、Set、Queue的实现类。toArray()方法有两个，分别返回Object数组和泛型数组。如果toArray()是泛型数组，则拷贝一份到Object数组中并返回。

  • add(E e)方法
    public boolean add(E e) {
        ensureCapacityInternal(size + 1); 
        elementData[size++] = e;
        return true;
    }

    private static final int DEFAULT_CAPACITY = 10;
    private void ensureCapacityInternal(int minCapacity) {
        //如果实际存储数组 是空数组，则最小需要容量就是默认容量
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;//结构改变次数

        //如果数组（elementData)的长度小于最小需要的容量（minCapacity）就扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

ArrayList在没指定initialCapacity时就是相当于会使用延迟分配对象数组空间，当第一次插入元素时才分配10（默认）个对象空间。假如有20个数据需要添加，那么会分别在第一次的时候，将ArrayList的容量变为10；之后扩容增加数组的size>>1的长度,也就是会按照 1.5倍增长。也就是当添加第11个数据的时候，Arraylist继续扩容变为10*1.5=15；当添加第16个数据时，继续扩容变为15 * 1.5 =22个。

  • add(int index, E element)
    public void add(int index, E element) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        ensureCapacityInternal(size + 1);  // 扩容，和add(E e)一样
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

System.arraycopy()方法是一个原生的静态方法，用于从源数组拷贝元素到目标数组中
System.arraycopy() 方法如下:

public static native void arraycopy(Object src, int srcPos,Object dest, int destPos,
int length);

src: 源数组 .
srcPos: 源数组中开始拷贝的索引值
dest: 目标数组
destPos: 拷贝到目标数组开始的索引值
length: 拷贝元素的个数
add(int index, E element)就是将index后面的数组copy了一份，并将索引值加1，然后将数组index索引赋值。

  • E get(int index)
    public E get(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        return (E) elementData[index];
    }
  • E set(int index, E element)
    public E set(int index, E element) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        E oldValue = (E) elementData[index];
        elementData[index] = element;
        return oldValue;
    }
  • E remove(int index)
    public E remove(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        modCount++;
        E oldValue = (E) elementData[index];

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null;

        return oldValue;
    }

numMoved表示要左移的元素，是否是大于0，大于0则将index后的元素左移一个位置，并将最后一个索引的最后一个元素置空。如果等于0，说明是index最后一个元素的索引，不需要左移，直接将最后一个索引置空。

  • boolean remove(Object o)
public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null;
    }

判断要移除的object是否为空，为空则移除第一个为null的元素。不为空时则用equals进行比较，如果元素没有重写equals方法，就比较内存地址，有重写就比较定义的equals规则，移除第一个内存地址相同或equals规则相同的元素。

ArrayList总结

  • 1.底层数组实现，使用默认构造方法初始化出来的容量是10
  • 2.扩容的长度是在原长度基础上加上>>1
  • 3.底层是数组，get获取元素性能很好
  • 4.线程不安全，所有的方法均不是同步方法也没有加锁，因此多线程下慎用
  • 5.添加删除和插入需要复制数组 性能较低

LinkedList源码分析

  • 无参构造
    public LinkedList() {
    }
  • Collection参数构造
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

        //将c中的元素都添加到链表中
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);//添加到链表尾部
    }

    //在序号为index处，添加c中所有的元素到当前链表中（后向添加）
    public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);//检查索引是否合法

        Object[] a = c.toArray();//将集合转换为数组
        int numNew = a.length;
        if (numNew == 0)
            return false;

        Node<E> pred, succ;
        if (index == size) {//构造方法会走这里，如果index为元素个数，即index个结点为尾结点
            succ = null;
            pred = last;//前指向指向尾结点，构造方法last这里是null
        } else {
            succ = node(index); 
            pred = succ.prev;   
        }

        //for循环结束后，数组a里面的元素都添加到当前链表里面，后向添加
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            //新生成一个结点，结点的前向指针指向pred,后向指针为null
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)
                //如果pred为null，则succ为当前头结点,构造方法会走这里
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;//pred移动到新结点
        }

        if (succ == null) {
            last = pred;//succ为null，这表示index为尾结点之后，构造方法会走这里
        } else {
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;//元素个数+num
        modCount++;//修改次数+1
        return true;
    }

Collection参数的构造方法将Collection转成数组，并循环遍历数组长度创建Node节点，并将双向链表前后指针赋值。

  • add(E e) 、offer(E e)
   public boolean offer(E e) {
        return add(e);
    }

    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++;
    }

add(E e)调用linkLast(E e)方法把元素添加到尾部，添加到尾部时创建新的节点，prev指针指向最后一个节点，next指针指向null。当最后一个节点为空，说明当前linkedlist元素为空，把新节点作为第一个节点。否则将原来的最后节点的next指针指向新节点。

  • add(int index, E element)
    public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

    Node<E> node(int index) {
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

    void linkBefore(E e, Node<E> succ) {
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

当add(int index, E element)传入索引==size,调用linkLast(element)添加到后面，在add(E e)中已经分析。不等于size,调用linkBefore(element, node(index))添加到中间或最前面，node(index)方法获取原Node节点，因为采用双向链表的设计，获取原Node节点只需遍历一半，将时间复杂度O(n)变成了O(n/2)，这也是双向链表比单向链表的优点。继续回到linkBefore(E e, Node<E> succ)分析，首先获取原索引Node节点的prev指针，创建新节点，新节点的prev指向原Node的prev，next指针指向原Node。当原节点不为空，将原Node的next指针指向新Node，如果原节点为空，首节点赋值为新Node。

  • E remove(int index)
    public E remove(int index) {
        checkElementIndex(index);//检查索引是否合法
        return unlink(node(index));
    }

    E unlink(Node<E> x) {
        final E element = x.item;
        final Node<E> next = x.next;//后一个节点
        final Node<E> prev = x.prev;//前一个节点

        if (prev == null) {//移除的是第一个节点
            first = next;
        } else {
            prev.next = next;//前一个节点的next指针指向后一个节点
            x.prev = null;//移除原节点的prev指针指向
        }

        if (next == null) {//如果移除的是最后一个节点
            last = prev;//将最后的last赋值为前一个节点
        } else {
            next.prev = prev;//将后一个节点的prev指针指向前一个节点
            x.next = null;//移除原节点的next指针指向
        }

        x.item = null;//置空原节点
        size--;
        modCount++;
        return element;
    }

E remove(int index)调用E unlink(Node<E> x)方法，获取索引Node的item，和前后节点，将前后节点的prev和next指针对应指向，并断开了原节点prev和next指向，并置空原索引节点，返回原节点item。

  • boolean remove(Object o)
public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

boolean remove(Object o)比E remove(int index)多了一步，需要先遍历获取索引，然后再调用unlink(Node<E> x)方法，，其他和E remove(int index)一样。

LinkedList总结

  • 1.LinkedList的实现是基于双向链表的，且头结点中不存放数据。
  • 2.无参构造方法直接建立一个仅包含head节点的空链表；包含Collection的构造方法，先调用无参构造方法建立一个空链表，而后将Collection中的数据加入到链表的尾部后面 。
  • 3.在查找和删除某元素时，源码中都划分为该元素为null和不为null两种情况来处理，LinkedList中允许元素为null。
  • 4.LinkedList是基于链表实现的，不存在容量不足的问题，所以没有扩容的方法。
  • 5.Node node(int index)方法。该方法返回双向链表中指定位置处的节点，而链表中是没有下标索引的，要指定位置出的元素，就要遍历该链表，从源码的实现中，我们看到这里有一个加速动作。源码中先将index与长度size的一半比较，如果index<(size<<1)，就只从位置0往后遍历到位置index处，而如果index>(size<<1)，就只从位置size往前遍历到位置index处。这样可以减少一部分不必要的遍历，从而提高一定的效率。
  • 6.LinkedList是基于链表实现的，插入删除效率高，查找效率低。
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 205,386评论 6赞 479
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 87,939评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,851评论 0赞 341
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,953评论 1赞 278
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,971评论 5赞 369
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,784评论 1赞 283
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,126评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,765评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 43,148评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,744评论 2赞 323
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,858评论 1赞 333
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,479评论 4赞 322
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,080评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,053评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,278评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,245评论 2赞 352
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,590评论 2赞 343