List (有序可重复)

List列表允许存储相同元素，插入元素和按照下标获取元素方便，具体实现有ArrayList，LinkedList和Vector

• ArrayList 底层基于数组实现，按顺序存储元素以及快速按照元素下标进行获取元素，不可同步的；
• 而Vector底层也是数组，可进行同步操作，在多线程环境下可以使用；
• LikedList是基于链表形式

1. ArrayList

ArrayList继承AbstractList，实现了List<E>, RandomAccess, Cloneable, java.io.Serializable接口；

image.png

1.1构造方法

它的构造方法有三个：

image.png
image.png
image.png

第一个我们可以传入一个int值，来初始化我们ArrayList的初始容量，如：

image.png
第二个是我们不传入初始容量，它会为我们默认构造一个初始容量为10的数组
第三个我们可以传入一个列表

1.2相关方法

• add()

  
  image.png
  

  在添加数据之前，先进行了扩容，然后在数组末尾添加元素

  
  image.png
  image.png
  image.png
  

  容量的拓展将导致数组元素的复制，多次拓展容量将执行多次整个数组内容的复制。若提前能大致判断list的长度，调用ensureCapacity调整容量，将有效的提高运行速度。
  可以理解提前分配好空间可以提高运行速度，但是测试发现提高的并不是很大，而且若list原本数据量就不会很大效果将更不明显。

• add(int index,E element )

public void add(int index, E element) {
        rangeCheckForAdd(index);//检查index是否越界
        ensureCapacityInternal(size + 1);  // 确保容量
        System.arraycopy(elementData, index, elementData, index + 1,//将index以后的元素后移一个
                         size - index);
        elementData[index] = element;
        size++;
    }
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)//元素可以添加在最后尾端
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    //本地的C/C++库方法，直接操纵内存，速度更快
    public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);