---

前言

刷LeetCode的时候用了List，用得少已经有些恍惚了。所以今天整理一下List接口还有它的一些实现类，加深理解。
（以下内容基于JDK1.8）

一、List是什么？

List接口是Collection的子接口，实现一种线性表的数据结构。存放在List中的所有元素都有一个下标（从0开始），可以通过下标访问List中的元素。同时，List中可以包含重复元素。

二、常用方法

List接口除继承Collection的方法之外，还定义了一些自己的方法。使用这些方法可以实现定位访问、查找、迭代和返回子线性表。

• Collection常用的方法如下：
  boolean add(E e):向集合中添加元素e；
  boolean remove(E e)：向集合中删除指定元素o；
  boolean contains（E e）：返回集合中是否包含指定的元素e；
  boolean isEmpty（）：返回集合是否为空；
  int size（）：返回集合的大小（元素个数）；
  还有一些批量操作和数组操作的常见方法，可参见API。

---

• List的常用方法如下：
  E get（int index）： 返回指定下标的处的元素；
  E set（int index）： 设置指定下标出的元素；
  void add（int index, E element）:将指定元素插入到指定下标处；
  E remove（int index）：删除指定下标处的元素；
  abstract boolean addAll（int index，Collection <? extends E> c）:在指定下标处插入集合c中的全部元素；

三、ArrayList

1.简介

ArrayList是最常用的线性表实现类，通过数组实现的集合对象。ArrayList类实际上实现了一个变长的对象数组，其元素可以动态增加和删除。它的定位访问时间是常量时间。

2.ArrayList构造器

无参构造下的默认容量是10，也可以使用带容量的参数构造。

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);}}/*** Constructs an empty list with an initial capacity of ten.*/public ArrayList() {//DEFAULTCAPACITY_EMPTY_ELEMENTDATA = 10this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}/*** Constructs a list containing the elements of the specified* collection, in the order they are returned by the collection's* iterator.** @param c the collection whose elements are to be placed into this list* @throws NullPointerException if the specified collection is null*/public ArrayList(Collection<? extends E> c) {elementData = c.toArray();if ((size = elementData.length) != 0) {// c.toArray might (incorrectly) not return Object[] (see 6260652)if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, size, Object[].class);} else {// replace with empty array.this.elementData = EMPTY_ELEMENTDATA;}}

3.添加元素（扩容机制）

ArrayList类中的add()方法代码：

    /*** Appends the specified element to the end of this list.** @param e element to be appended to this list* @return <tt>true</tt> (as specified by {@link Collection#add})*/public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!!elementData[size++] = e;return true;}

其中的elementData是存储元素的数组：

    /*** The array buffer into which the elements of the ArrayList are stored.* The capacity of the ArrayList is the length of this array buffer. Any* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA* will be expanded to DEFAULT_CAPACITY when the first element is added.*/transient Object[] elementData; // non-private to simplify nested class access

分析add()引用的方法：ensureCapacityInternal(int minCapacity)

	//此时minCapacity=size+1private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}

ArrayList类中的calculateCapacity()方法代码：

	//如果list为空，则返回默认值（10）和minCapacity的最大值；否则返回minCapacityprivate static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;}

ArrayList类中的ensureExplicitCapacity()方法代码：

private void ensureExplicitCapacity(int minCapacity) {modCount++;  //初始值为0// overflow-conscious codeif (minCapacity - elementData.length > 0)//当容量不足的时候，使用grow函数进行扩容grow(minCapacity);}

新容量 = 旧容量 + 0.5倍旧容量，也就是扩容1.5倍
ArrayList类中的grow()方法代码：

private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;//新容量 = 旧容量 + 0.5倍旧容量，也就是扩容1.5倍int newCapacity = oldCapacity + (oldCapacity >> 1);if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)//如果新容量超过了最大容量值，则调用hugeCapacity进行扩容newCapacity = hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a win:elementData = Arrays.copyOf(elementData, newCapacity);}

如果超过最大容量值，就是用Integer的最大值，否则使用设置的最大容量值
ArrayList类中的hugeCapacity()方法代码：

    private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}

---

LinkedList

1、简介

LinkedList也实现了List接口（也实现了Deque，Cloneable，Serializable，即支持队列，克隆和可序列化），相对于ArrayList来说，它们的最大区别在于底层数据结构不同，LinkedList的底层是一个双向链表，这也决定了它的最大优点，那就是对于数据的修改比ArrayList更加方便快捷。相对于ArrayList，LinkedList插入是更快的。因为LinkedList不需要改变数组的大小，也不需要在数组装满的时候要将所有的数据重新装入一个新的数组，类似于插入数据，删除数据时，LinkedList也优于ArrayList，其时间复杂度仅为O(1)，而ArrayList删除数据是开销很大的，因为这需要重排数组中的数据。

2、添加元素

add（）无参方法这里默认尾插

    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;elsel.next = newNode;size++;modCount++;}

也可以指定头插和尾插：

    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;if (f == null)last = newNode;elsef.prev = newNode;size++;modCount++;}public void addLast(E e) {linkLast(e);}/*** Links e as last element.*/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;elsel.next = newNode;size++;modCount++;}