// 无参构造器，构造一个容量大小为 10 的空的 list 集合，但构造函数只是给 elementData 
// 赋值了一个空的数组，其实是在第一次添加元素时容量扩大至 10 的。
public ArrayList() { 
 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; 
} 


// 当使用无参构造函数时是把 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 赋值给 elementDat a。
// 当 initialCapacity 为零时则是把 EMPTY_ELEMENTDATA 赋值给 elementData。
// 当 initialCapacity 大于零时初始化一个大小为 initialCapacity 的 object数组并赋值给 ele mentData。 
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); 
 } 
} 


//将 Collection 转化为数组，数组长度赋值给 size。 如果 size 不为零，则判断 elem entData 的 class 类型是否为 ArrayList，不是的话则做一次转换。 如果 size 为零，则把 EMPTY_ELEMENTDATA 赋值给 elementData，相当于new ArrayList(0)。 
public ArrayList(Collection<? extends E> c) { 
  Object[] a = c.toArray();  
   if ((size = a.length) != 0) { 
     if (c.getClass() == ArrayList.class) { 
       elementData = a; 
     } else { 
       elementData = Arrays.copyOf(a, size, Object[].class);
     } 
   } else { 
     // 指向空数组 
     elementData = EMPTY_ELEMENTDATA; 
   } 
}

添加元素

•   尾部添加，效率较高

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

•   插入，后面的元素均要移动，效率相对较差

public void add(int index, E element) { 
  rangeCheckForAdd(index);//下标越界检查 
  ensureCapacityInternal(size + 1); //同上判断扩容,记录操作数
  // 依次复制插入位置及后面的数组元素，到后面一格，不是移动，因此复制完后，
  // 添加的下标位置和下一个位置指向对同一个对象 
  System.arraycopy(elementData, index, elementData, index + 1, size ‐ index); 
  elementData[index] = element;//再将元素赋值给该下标 
  size++;
}

扩容

   先直接扩容1.5倍，如果扩容后的容量小于指定要扩容的容量，则以指定的扩容扩容。如果指定容量非常大，则以Integer的最大值或其减8来扩容。

private void grow(int minCapacity) { 
  int oldCapacity = elementData.length;//获取当前数组长度 
  int newCapacity = oldCapacity + (oldCapacity >> 1);//默认将扩容至原来容量的 1.5 倍

  // 如果1.5倍太小的话，则将我们所需的容量大小 赋值给newCapacity  
  if (newCapacity ‐ minCapacity < 0)
   newCapacity = minCapacity; 

  // 如果1.5倍太大或者我们需要的容量太大，那就直接
  // 拿newCapacity = (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MA X_ARRAY_SIZE 来扩容
  if (newCapacity ‐ MAX_ARRAY_SIZE > 0) 
   newCapacity = hugeCapacity(minCapacity); 
  // 然后将原数组中的数据 复制到大小为 newCapacity 的新数组中，并将新数组赋值给 elementData。
  elementData = Arrays.copyOf(elementData, newCapacity); 
}

删除：

  删除指定位置元素后，后面的元素都会往前移动，然后把最后一个元素置空

public E remove(int index) {
  //  删除是否越界
  rangeCheck(index);
  //  操作数加1
  modCount++;
  //  找出删除元素
  E oldValue = elementData(index);
  int numMoved = size - index - 1;
  if (numMoved > 0)
     // 将删除位置后面的元素赋值到前面一位的位置上
     System.arraycopy(elementData, index+1, elementData, index,numMoved);
     // 将最后一个元素置空 
     elementData[--size] = null; // clear to let GC do its work
     // 返回删除元素值
     return oldValue;
}

清空ArrayList的三种方法

List aa= new ArrayList<>();
aa.add("111");
aa.add("112");
aa.add("113");
System.out.println(aa); // [111, 112, 113]

// 直接调内部方法清空
aa.clear();
System.out.println(aa);  // []

//  for循环清空，遍历list总数次，每次删除第一个元素
int b =aa.size();
for (int i = 0; i < b; i++) {
    aa.remove(0);
}
System.out.println(aa);  // []

//  迭代器清空，每次判断下一个元素是否存在，存在先遍历该元素，然后删除该元素
Iterator  it =aa.iterator();
while (it.hasNext()){
    it.next();
    it.remove();
}

其他重要API

LinkedList：

    底层是双向循环链表实现，增删效率搞，查找效率低。

构造函数

LinkedList（） // 用于创建一个空的链表。
LinkedList(Collection<? extends E> collection) // 创建一个LinkedList，保护Collection中的全部元素。

常用方法

添加元素

boolean add（Object element）// 它将元素附加到列表的末尾。
void addFirst(E element) // 元素附加到列表的头部
void addLast(Eelement) // 元素附加到列表的尾部

查询头尾元素

Object getFirst() // 它返回链表的第一个元素。

Object getLast() // 它返回链接列表的最后一个元素。

查找指定元素索引

int indexOf(Object element) // 如果找到元素，它将返回元素第一次出现的索引。否则，它返回-1。
int lastIndexOf(Object element) // 如果找到元素，它将返回元素最后一次出现的索引。否则，它返回-1。

删除元素

E remove(int location)
E removeFirst() // 删除并返回链接列表的头部一个元素
E removeLast() // 删除并返回链接列表的尾部一个元素

其他API

void clear() // 它删除列表中的所有元素。
Object clone() // 它用于制作现有链接列表的副本。
Object set(int index，Object element) // 它用于用新元素替换列表中的现有元素。
boolean contains(Object element) // 如果元素存在于列表中，则返回true。