Java 容器 --- List（ArrayList、Linke

在一开始基础面的时候，很多面试官可能会问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 的 elementData 加上 transient 修饰（序列化）？

• ArrayList 基于数组实现，并且具有动态扩容特性，因此保存元素的数组不一定都会被使用，那么就没必要全部进行序列化。保存元素的数组 elementData 使用 transient 修饰，该关键字声明数组默认不会被序列化。

• ArrayList 实现了 writeObject() 和 readObject() 来控制只序列化数组中有元素填充那部分内容。

• 序列化时需要使用 ObjectOutputStream 的 writeObject() 将对象转换为字节流并输出。而 writeObject() 方法在传入的对象存在 writeObject() 的时候会去反射调用该对象的 writeObject() 来实现序列化。反序列化使用的是 ObjectInputStream 的 readObject() 方法，原理类似。

ArrayList的构造方法

• 带有初始化容量initialCapacity的构造方法
• 无参构造方法
• 参数为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是如何扩容的？

• 添加元素时使用 ensureCapacityInternal() 方法来保证容量足够，如果不够时，需要使用 grow() 方法进行扩容，新容量的大小为 oldCapacity + (oldCapacity >> 1)，即 oldCapacity+oldCapacity/2。其中 oldCapacity >> 1 需要取整，所以新容量大约是旧容量的 1.5 倍左右（oldCapacity 为偶数就是 1.5 倍，为奇数就是 1.5 倍-0.5）。

• 扩容操作需要调用 Arrays.copyOf() 把原数组整个复制到新数组中，这个操作代价很高，因此最好在创建 ArrayList 对象时就指定大概的容量大小，减少扩容操作的次数。

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

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删除元素效率低？

• 如果删除index位置的元素，需要调用 System.arraycopy() 将 index+1 后面的元素都复制到 index 位置上，该操作的时间复杂度为 O(N)，可以看到 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;
    // 将集合的修改次数+1
    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;  
    // 创建新节点，其前继节点是succ的前节点，后接点是succ节点
    final Node<E> newNode = new Node<>(pred, e, succ);  
    // 更新插入位置（succ）的前置节点为新节点
    succ.prev = newNode;  
    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 都是不同步的，也就是不保证线程安全；Vector：和 ArrayList 类似，但它是线程安全的（一般不使用，效率太低）。

区别：

• 底层数据结构：ArrayList是实现了基于动态数组的数据结构，LinkedList是基于双向链表结构。
• 随机访问效率：对于随机访问的查询get和set，ArrayList要优于LinkedList，因为LinkedList只能顺序访问。ps：跳表可以基于链表进行二分查找。
• 增加和删除的效率：对于插入和删除操作add和remove，LinkedList比较高效，因为ArrayList要移动数据。
• 内存空间占用：LinkedList 比 ArrayList 更占内存，因为 LinkedList 的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素。

优缺点：

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

应用场景:

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

list 的遍历方式和RandomAccess接口

RandomAccess接口只是标识，并不是说 ArrayList实现RandomAccess 接口才具有快速随机访问功能的。下面再总结⼀下 list 的遍历方式选择：

• 实现了 RandomAccess 接口的list，优先选择普通 for 循环 ，其次 for each；
• 未实现 RandomAccess 接口的list，优先选择iterator遍历（for each遍历底层也是通过iterator实现的,），大size的数据，千万不要使用普通for循环。

list三种遍历方式：

//1、方法一:for循环
List<Product> list = new ArayList<Product>();
for(int i=0 ; i< list.size();i++){
   System.out.println(list.get(i).getId()+":"+list.get(i).getName());
}
//2、方法二 ：迭代器
//创建迭代器对象!
Iterator<Product> it = list.iterator();
while(it.hasNext()){
    Product nextPro = it.next();
    System.out.println(nextPro.getId()+" : "+nextPro.getName());
}
//3、方法三：for...each
for(Product pro:list){
    System.out.println(pro.getId()+":"+pro.getName());
}  

Java集合的快速失败机制 “fail-fast”？

• fail-fast 机制是java集合（Collection）中的一种错误机制。当多个线程对同一个集合的内容进行操作时，就可能会产生 fail-fast 事件。例如：当某一个线程A通过 iterator 去遍历某集合的过程中，若该集合的内容被其他线程所改变了；那么线程A访问集合时，就会抛 ConcurrentModificationException 异常，产生 fail-fast 事件。

• 原因：modCount 用来记录 ArrayList等结构发生变化的次数。结构发生变化是指 添加或者删除至少一个元素的所有操作，或者是调整内部数组的大小，仅仅只是设置元素的值不算结构发生变化！

• 在进行序列化或者迭代等操作时，需要比较操作前后 modCount 是否改变，如果改变了需要抛出 ConcurrentModificationException。

解决办法（多线程下如何使用ArrayList？- 前两条）：

• 在遍历过程中所有涉及到改变modCount的地方全部加上synchronized或者直接使用Collections.synchronizedList。这样就可以解决问题，但是不推荐，因为增删造成的同步锁可能会阻塞遍历操作。
• 使用CopyOnWriteArrayList来替换ArrayList。CopyOnWriteArrayList所有可变操作（add、set 等等）都是通过对底层数组进行一次新的复制来实现的。该类产生的开销比较大，但是在两种情况下，它非常适合使用：1）在不能或不想进行同步遍历，但又需要从并发线程中排除冲突时。2）当遍历操作的数量大大超过可变操作的数量时。
• 对于单线程来说，执行删除操作的时候，不要使用集合自身的删除方法，而使用集合中迭代器的删除方法。因为无论是 ArrayList 还是 HashMap，他们对应的迭代器中的 remove 方法中，都有这么一句代码，expectedModCount = modCount，这就意味着，即使删除了，这两个变量也是一直同步的，不会发生 modCount 加 1，而 expectedModCount 不变的情况。

CopyOnWriteArrayList

线程安全的List：CopyOnWriteArrayList（写的时候直接copy整个数组，写的效率比较低，但读不加锁）和Collections.synchronizedList（读也要加锁，导致多线程效率低）

读写分离：

• 写操作在一个复制的数组上进行，读操作还是在原始数组中进行，读写分离，互不影响。
• 写操作需要加锁，防止并发写入时导致写入数据丢失。
• 写操作结束之后需要把原始数组指向新的复制数组。

适用场景

• CopyOnWriteArrayList 在写操作的同时允许读操作，大大提高了读操作的性能，因此很适合读多写少的应用场景！！但是 CopyOnWriteArrayList 有其缺陷：
  • 内存占用：在写操作时需要复制一个新的数组，使得内存占用为原来的两倍左右；
  • 数据不一致：读操作不能读取实时性的数据，因为部分写操作的数据还未同步到读数组中。

所以 CopyOnWriteArrayList 不适合内存敏感以及对实时性要求很高的场景。

注意：CopyOnWrite类还有java.util.concurrent.CopyOnWriteArraySet，都是从jdk1.5加入的。

ArrayList 和 Vector 的区别是什么？

这两个类都实现了 List 接口（List 接口继承了 Collection 接口），他们都是有序集合。

相同点：

• ArrayList和Vector都是继承了相同的父类和实现了相同的接口List
• 底层都是数组实现的
• 初始默认长度都为10（元素个数）

不同点：

• 线程安全：Vector 使用了 Synchronized来实现线程同步，是线程安全的，而 ArrayList是非线程安全的。
• 性能：ArrayList 在性能方面要优于 Vector。
• 扩容：ArrayList 和 Vector 都会根据实际的需要动态的调整容量，只不过在 Vector 扩容每次会增加 1 倍，而 ArrayList 只会增加 约1.5倍。

Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。Arraylist不是同步的，所以在不需要保证线程安全时建议使用Arraylist。

ArrayList和LinkedList哪个更占空间

• 一般情况下，LinkedList的占用空间更大，因为每个节点要维护指向前后地址的两个节点。ps：Node中包含了三个成员，分别是存储数据的item，指向前一个存储单元的点 prev 和指向后一个存储单元的节点 next ，通过这两个节点就可以关联前后的节点，组装成为链表的结构

• 但也不是绝对，如果刚好数据量超过ArrayList默认的临时值时，ArrayList占用的空间也是不小的，因为扩容的原因会浪费将近原来数组一半的容量。ps：如果你只添加一个元素的话，那么会有将近原来一半大小的数组空间被浪费了，如果原先数组很大的话，那么这部分空间的浪费也是不少的。

• 不过，因为ArrayList的数组变量是用transient关键字修饰的，如果集合本身需要做序列化操作的话，ArrayList这部分多余的空间不会被序列化。ps：先调用defaultWriteObject()方法序列化ArrayList中的非transient元素，elementData这个数组对象不去序列化它，而是遍历elementData，只序列化数组里面有数据的元素，这样一来，就可以加快序列化的速度，还能够减少空间的开销。

巨人的肩膀：

https://my.oschina.net/ccwwlx/blog/4311117
https://mp.weixin.qq.com/s/5J-9Kc5CewWIRm2GKSB5Lg