去年去阿里面试，被问到ArrayList和LinkedList，我是这样回答的！

前言

在一开始基础面的时候，很多面试官可能会问List集合一些基础知识，比如：

  • ArrayList默认大小是多少，是如何扩容的？
  • ArrayList和LinkedList的底层数据结构是什么？
  • ArrayList和LinkedList的区别？分别用在什么场景？
  • 为什么说ArrayList查询快而增删慢？
  • Arrays.asList方法后的List可以扩容吗？
  • modCount在非线程安全集合中的作用？
  • ArrayList和LinkedList的区别、优缺点以及应用场景

ArrayList(1.8)

ArrayList是由动态再分配的Object[]数组作为底层结构，可设置null值，是非线程安全的。

ArrayList成员属性

//默认的空的数组，在构造方法初始化一个空数组的时候使用
private static final Object[] EMPTY_ELEMENTDATA = {};

//使用默认size大小的空数组实例
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//ArrayList底层存储数据就是通过数组的形式，ArrayList长度就是数组的长度。
transient Object[] elementData; 

//arrayList的大小
private int size;

那么ArrayList底层数据结构是什么呢？

很明显，使用动态再分配的Object[]数组作为ArrayList底层数据结构了，既然是使用数组实现的，那么数组特点就能说明为什么ArrayList查询快而增删慢？

因为数组是根据下标查询不需要比较，查询方式为：首地址＋（元素长度＊下标），基于这个位置读取相应的字节数就可以了，所以非常快；但是增删会带来元素的移动，增加数据会向后移动，删除数据会向前移动，导致其效率比较低。

ArrayList的构造方法

  • 带有初始化容量的构造方法
  • 无参构造方法
  • 参数为Collection类型的构造器
//带有初始化容量的构造方法
public ArrayList(int initialCapacity) {
    //参数大于0，elementData初始化为initialCapacity大小的数组
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    //参数小于0，elementData初始化为空数组
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    //参数小于0，抛出异常
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

//无参构造方法
public ArrayList() {
    //在1.7以后的版本，先构造方法中将elementData初始化为空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    //当调用add方法添加第一个元素的时候，会进行扩容,扩容至大小为DEFAULT_CAPACITY=10
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

那么ArrayList默认大小是多少？

从无参构造方法中可以看出，一开始默认为一个空的实例elementData为上面的DEFAULTCAPACITY_EMPTY_ELEMENTDATA，当添加第一个元素的时候会进行扩容，扩容大小就是上面的默认容量DEFAULT_CAPACITY为10

ArrayList的Add方法

  • boolean add(E)：默认直接在末尾添加元素
  • void add(int，E)：在特定位置添加元素，也就是插入元素
  • boolean addAll(Collection<? extends E> c)：添加集合
  • boolean addAll(int index, Collection<? extends E> c)：在指定位置后添加集合

boolean add(E)

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

通过ensureCapacityInternal方法为确定容量大小方法。在添加元素之前需要确定数组是否能容纳下，size是数组中元素个数，添加一个元素size+1。然后再数组末尾添加元素。

其中，ensureCapacityInternal方法包含了ArrayList扩容机制grow方法，当前容量无法容纳下数据时1.5倍扩容，进行：

private void ensureCapacityInternal(int minCapacity) {
    //判断当前的数组是否为默认设置的空数据，是否取出最小容量
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //包括扩容机制grow方法
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
        //记录着集合的修改次数，也就每次add或者remove它的值都会加1
        modCount++;

        //当前容量容纳不下数据时（下标超过时），ArrayList扩容机制：扩容原来的1.5倍
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //ArrayList扩容机制：扩容原来的1.5倍
        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);
    }

ArrayList是如何扩容的？

根据当前的容量容纳不下新增数据时，ArrayList会调用grow进行扩容：

//相当于int newCapacity = oldCapacity + oldCapacity/2
int newCapacity = oldCapacity + (oldCapacity >> 1);

扩容原来的1.5倍。

void add(int，E)

public void add(int index, E element) {
    //检查index也就是插入的位置是否合理,是否存在数组越界
    rangeCheckForAdd(index);
    //机制和boolean add(E)方法一样
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

ArrayList的删除方法

  • remove(int)：通过删除指定位置上的元素，
  • remove(Object)：根据元素进行删除，
  • clear()：将elementData中每个元素都赋值为null，等待垃圾回收将这个给回收掉，
  • removeAll(collection c)：批量删除。

remove(int)

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);
    //将--size上的位置赋值为null，让gc(垃圾回收机制)更快的回收它。
    elementData[--size] = null; // clear to let GC do its work
    //返回删除的元素
    return oldValue;
}

为什么说ArrayList删除元素效率低？

因为删除数据需要将数据后面的元素数据迁移到新增位置的后面，这样导致性能下降很多，效率低。

remove(Object)

public boolean remove(Object o) {
    //如果需要删除数据为null时，会让数据重新排序，将null数据迁移到数组尾端
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                //删除数据，并迁移数据
                fastRemove(index);
                return true;
            }
    } else {
        //循环删除数组中object对象的值，也需要数据迁移
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

可以看出，arrayList是可以存放null值。

LinkedList(1.8)

LinkedList是一个继承于AbstractSequentialList的双向链表。它也可以被当做堆栈、队列或双端队列进行使用，而且LinkedList也为非线程安全， jdk1.6使用的是一个带有 header节头结点的双向循环链表， 头结点不存储实际数据 ，在1.6之后，就变更使用两个节点first、last指向首尾节点。

LinkedList的主要属性

//链表节点的个数 
transient int size = 0; 
//链表首节点
 transient Node<E> first; 
//链表尾节点
 transient Node<E> last; 
//Node节点内部类定义
private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

一旦变量被transient修饰，变量将不再是对象持久化的一部分，该变量内容在序列化后无法获得访问

LinkedList构造方法

无参构造函数， 默认构造方法声明也不做，first和last节点会被默认初始化为null。

*
/** Constructs an empty list. \*/*

public LinkedList() {}

LinkedList插入

由于LinkedList由双向链表作为底层数据结构，因此其插入无非由三大种

  • 尾插： add(E e)、addLast(E e)、addAll(Collection<? extends E> c)

  • 头插： addFirst(E e)

  • 中插： add(int index, E element)

    可以从源码看出，在链表首尾添加元素很高效，在中间添加元素比较低效，首先要找到插入位置的节点，在修改前后节点的指针。

尾插-add(E e)和addLast(E e)

//常用的添加元素方法
public boolean add(E e) {
    //使用尾插法
    linkLast(e);
    return true;
}

//在链表尾部添加元素
public void addLast(E e) {
        linkLast(e);
    }

//在链表尾端添加元素
void linkLast(E e) {
        //尾节点
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        //判断是否是第一个添加的元素
        //如果是将新节点赋值给last
        //如果不是把原首节点的prev设置为新节点
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        //将集合修改次数加1
        modCount++;
    }

头插-addFirst(E e)

public void addFirst(E e) {
    //在链表头插入指定元素
    linkFirst(e);
}

private void linkFirst(E e) {
            //获取头部元素,首节点
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        //链表头部为空，（也就是链表为空）
        //插入元素为首节点元素
        // 否则就更新原来的头元素的prev为新元素的地址引用
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        //
        size++;
        modCount++;
    }

中插-add(int index, E element)

当index不为首尾的的时候，实际就在链表中间插入元素。

 // 作用：在指定位置添加元素
    public void add(int index, E element) {
        // 检查插入位置的索引的合理性
        checkPositionIndex(index);

        if (index == size)
            // 插入的情况是尾部插入的情况：调用linkLast（）。
            linkLast(element);
        else
            // 插入的情况是非尾部插入的情况（中间插入）：linkBefore
            linkBefore(element, node(index));
    }

    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;  // 得到插入位置元素的前继节点
        final Node<E> newNode = new Node<>(pred, e, succ);  // 创建新节点，其前继节点是succ的前节点，后接点是succ节点
        succ.prev = newNode;  // 更新插入位置（succ）的前置节点为新节点
        if (pred == null)
            // 如果pred为null，说明该节点插入在头节点之前，要重置first头节点 
            first = newNode;
        else
            // 如果pred不为null，那么直接将pred的后继指针指向newNode即可
            pred.next = newNode;
        size++;
        modCount++;
    }

LinkedList 删除

删除和插入一样，其实本质也是只有三大种方式，

  • 删除首节点:removeFirst()

  • 删除尾节点:removeLast()

  • 删除中间节点 ：remove(Object o)、remove(int index)

    在首尾节点删除很高效，删除中间元素比较低效要先找到节点位置，再修改前后指针指引。

删除中间节点-remove(int index)和remove(Object o)

remove(int index)和remove(Object o)都是使用删除指定节点的unlink删除元素

 public boolean remove(Object o) {
     //因为LinkedList允许存在null，所以需要进行null判断        
     if (o == null) {
         //从首节点开始遍历
         for (Node<E> x = first; x != null; x = x.next) {
             if (x.item == null) {
                 //调用unlink方法删除指定节点
                 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;
 } 

//删除指定位置的节点，其实和上面的方法差不多
    //通过node方法获得指定位置的节点，再通过unlink方法删除
    public E remove(int index) {
        checkElementIndex(index);

        return unlink(node(index));
    }

 //删除指定节点
    E unlink(Node<E> x) {
        //获取x节点的元素，以及它上一个节点，和下一个节点
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
        //如果x的上一个节点为null，说明是首节点，将x的下一个节点设置为新的首节点
        //否则将x的上一节点设置为next，将x的上一节点设为null
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }
        //如果x的下一节点为null，说明是尾节点，将x的上一节点设置新的尾节点
        //否则将x的上一节点设置x的上一节点，将x的下一节点设为null
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }
        //将x节点的元素值设为null，等待垃圾收集器收集
        x.item = null;
        //链表节点个数减1
        size--;
        //将集合修改次数加1
        modCount++;
        //返回删除节点的元素值
        return element;
    }

删除首节点-removeFirst()

//删除首节点
public E remove() {
        return removeFirst();
    }
 //删除首节点
 public E removeFirst() {
      final Node<E> f = first;
      //如果首节点为null，说明是空链表，抛出异常
      if (f == null)
          throw new NoSuchElementException();
      return unlinkFirst(f);
  }
  //删除首节点
  private E unlinkFirst(Node<E> f) {
      //首节点的元素值
      final E element = f.item;
      //首节点的下一节点
      final Node<E> next = f.next;
      //将首节点的元素值和下一节点设为null，等待垃圾收集器收集
      f.item = null;
      f.next = null; // help GC
      //将next设置为新的首节点
      first = next;
      //如果next为null，说明说明链表中只有一个节点，把last也设为null
      //否则把next的上一节点设为null
      if (next == null)
          last = null;
      else
          next.prev = null;
      //链表节点个数减1
      size--;
      //将集合修改次数加1
      modCount++;
      //返回删除节点的元素值
      return element;
 }

删除尾节点-removeLast()

    //删除尾节点
    public E removeLast() {
        final Node<E> l = last;
        //如果首节点为null，说明是空链表，抛出异常
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }
    private E unlinkLast(Node<E> l) {
           //尾节点的元素值
        final E element = l.item;
        //尾节点的上一节点
        final Node<E> prev = l.prev;
        //将尾节点的元素值和上一节点设为null，等待垃圾收集器收集
        l.item = null;
        l.prev = null; // help GC
        //将prev设置新的尾节点
        last = prev;
        //如果prev为null，说明说明链表中只有一个节点，把first也设为null
        //否则把prev的下一节点设为null
        if (prev == null)
            first = null;
        else
            prev.next = null;
        //链表节点个数减1
        size--;
        //将集合修改次数加1
        modCount++;
        //返回删除节点的元素值
        return element;
    }

其他方法也是类似的，比如查询方法 LinkedList提供了get、getFirst、getLast等方法获取节点元素值。

modCount属性的作用？

modCount属性代表为结构性修改（ 改变list的size大小、以其他方式改变他导致正在进行迭代时出现错误的结果）的次数，该属性被Iterator以及ListIterator的实现类所使用，且很多非线程安全使用modCount属性。

​ 初始化迭代器时会给这个modCount赋值，如果在遍历的过程中，一旦发现这个对象的modCount和迭代器存储的modCount不一样，Iterator或者ListIterator 将抛出ConcurrentModificationException异常，

这是jdk在面对迭代遍历的时候为了避免不确定性而采取的 fail-fast（快速失败）原则：

在线程不安全的集合中，如果使用迭代器的过程中，发现集合被修改，会抛出ConcurrentModificationExceptions错误，这就是fail-fast机制。对集合进行结构性修改时，modCount都会增加，在初始化迭代器时，modCount的值会赋给expectedModCount，在迭代的过程中，只要modCount改变了，int expectedModCount = modCount等式就不成立了，迭代器检测到这一点，就会抛出错误：urrentModificationExceptions。

总结

ArrayList和LinkedList的区别、优缺点以及应用场景

区别：

  • ArrayList是实现了基于动态数组的数据结构，LinkedList是基于链表结构。
  • 对于随机访问的get和set方法查询元素，ArrayList要优于LinkedList，因为LinkedList循环链表寻找元素。
  • 对于新增和删除操作add和remove，LinkedList比较高效，因为ArrayList要移动数据。

优缺点：

  • 对ArrayList和LinkedList而言，在末尾增加一个元素所花的开销都是固定的。对ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对LinkedList而言，这个开销是 统一的，分配一个内部Entry对象。
  • 在ArrayList集合中添加或者删除一个元素时，当前的列表移动元素后面所有的元素都会被移动。而LinkedList集合中添加或者删除一个元素的开销是固定的。
  • LinkedList集合不支持 高效的随机随机访问（RandomAccess），因为可能产生二次项的行为。
  • ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间

应用场景:

ArrayList使用在查询比较多，但是插入和删除比较少的情况，而LinkedList用在查询比较少而插入删除比较多的情况

©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 218,204评论 6赞 506
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 93,091评论 3赞 395
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 164,548评论 0赞 354
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,657评论 1赞 293
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,689评论 6赞 392
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,554评论 1赞 305
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,302评论 3赞 418
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 39,216评论 0赞 276
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,661评论 1赞 314
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,851评论 3赞 336
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,977评论 1赞 348
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,697评论 5赞 347
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,306评论 3赞 330
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,898评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,019评论 1赞 270
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 48,138评论 3赞 370
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,927评论 2赞 355