List接口特点
1、有序的 collection。
2、可以对列表中每个元素的插入位置进行精确地控制。
3、可以根据元素的索引访问元素，并搜索列表中的元素。
4、列表通常允许重复的元素。
5、允许存在 null 元素。
6、实现List接口的常用类有LinkedList、ArrayList、Vector和Stack。
ArrayList特点
1、java.util.ArrayList<E> : List 接口的大小可变数组的实现类
2、ArrayList 内部基于 数组 存储 各个元素。
3、所谓大小可变数组，是指当 数组容量不足以存放新的元素时，创建新数组，并将原数组中的内容复制过来。
4、源码分析
//elementData中已存放的元素的个数，注意：不是elementData的容量 private int size; //elementData的默认容量为10 private static final int DEFAULT_CAPACITY = 10; //对象数组：ArrayList的底层数据结构，transient表示该字段不进行序列化操作 transient Object[] elementData; //实例化一个空数组 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //实例化一个空数组 private static final Object[] EMPTY_ELEMENTDATA = {}; protected transient int modCount = 0; @Native public static final int MAX_VALUE = 0x7fffffff; private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** *指定初始容量的有参构造 */ public ArrayList(int initialCapacity) { //如果初始容量大于0就，对象数组就指向到一个新的数组，大小为所指定的大小 if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { //如果等于0就指向一个空数组 this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } /** * 无参构造 */ public ArrayList() { //对象数组就指向到一个空数组 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** * 向elementData末尾中添加元素 */ public boolean add(E e) { //确保对象数组elementData有足够的容量，可以将新加入的元素e加进去 ensureCapacityInternal(size + 1); //加入新元素e，size加1 elementData[size++] = e; return true; } // minCapacity = seize+1，即表示执行完添加操作后，数组中的元素个数 private void ensureCapacityInternal(int minCapacity) { //判断是否是空数组 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //用最小容量和10进行比较，取最大值赋值给最小容量 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } /** *确保数组的容量足够存放新加入的元素，若不够，要扩容 */ private void ensureExplicitCapacity(int minCapacity) { modCount++; //如果数组个数（size+1）数组长度就需要进行扩容 if (minCapacity - elementData.length > 0) grow(minCapacity); } private void grow(int minCapacity) { int oldCapacity = elementData.length; // 将旧的数组容量增加为原来的1.5倍作为新的容量 int newCapacity = oldCapacity + (oldCapacity >> 1); //如果新的容量小于数组个数，将数组个数赋值给新容量 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // 如果新的容量大于最大容量，就根据数组个数来决定新的容量大小 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 根据新的容量，将数组拷贝到新的数组并赋值给数组 elementData = Arrays.copyOf(elementData, newCapacity); } private static int hugeCapacity(int minCapacity) { // 如果数组个数小于0抛出OutOfMemoryError异常 if (minCapacity < 0) // overflow throw new OutOfMemoryError(); // 如果最数组个数大于最大容量 就返回最大值，否则返回最大容量 return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } /** * 向elementData指定位置添加元素 */ public void add(int index, E element) { //指定位置检查 rangeCheckForAdd(index); // 扩容检查 ensureCapacityInternal(size + 1); // Increments modCount!! //通过拷贝使数组内位置为 index 到 （size-1）的元素往后移动一位 System.arraycopy(elementData, index, elementData, index + 1, size - index); // 找到位置添加元素 elementData[index] = element; // 元素个数加一 size++; } // 判断指定位置是否超出数组容量 private void rangeCheckForAdd(int index) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } /** * @param src 原数组. * @param srcPos 原数组的起始位置. * @param dest 目标数组. * @param destPos 目标数组的起始位置. * @param length 拷贝长度. */ public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length); public E remove(int index) { //指定位置检查 rangeCheck(index); modCount++; //保留要删除的值 E oldValue = elementData(index); //要移动元素个数 int numMoved = size - index - 1; if (numMoved > 0) //通过拷贝使数组内位置为 index+1到 （size-1）的元素往前移动一位 System.arraycopy(elementData, index+1, elementData, index, numMoved); //清除末尾元素让GC回收 elementData[--size] = null; // clear to let GC do its work //返回删除的值 return oldValue; }
ArrayList在无参的add方法中，每次插入新的元素时，判断数组是否为空，为空则建默认的容量10赋值给minCapacity，判断是否要扩容，第一次添加，数组的size是10，之后添加元素时，在ensureExplicitCapacity方法中判断数组元素个数即size+1（形参minCapacity）是否超过数组长度，超过则需要进行扩容操作，扩容是将旧的容量扩大到1.5倍，然后将数组拷贝到新的数组完成扩容操作。最后将元素添加，并size+1。ArrayList在指定位置添加元素时，是先检查指定位置是否在数组范围内，即数组中元素个数是1，则index得小于或者低于1。然后通过拷贝使数组内位置为 index 到 （size-1）的元素往后移动一位，腾出位置之后放入元素，数组个数加一。
Vector特点
1、java.util.Vector<E> :List 接口的内部用数组存放元素的实现类
2、内部也是用数组存放元素。
3、与 ArrayList 不同的是 扩容方式不同，Vector 每次增长的容量是固定的，大部分方法都被 synchronized 关键字修饰。
4、Vector 是线程安全的。
5、源码分析
protected transient int modCount = 0; //elementData中已存放的元素的个数，注意：不是elementData的容量 protected int elementCount; //对象数组：Vector的底层数据结构 protected Object[] elementData; //增长系数 protected int capacityIncrement; @Native public static final int MAX_VALUE = 0x7fffffff; private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** *指定初始容量和增长系数的有参构造 */ public Vector(int initialCapacity, int capacityIncrement) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); //如果初始容量大于0就，对象数组就指向到一个新的数组，大小为所指定的大小 this.elementData = new Object[initialCapacity]; //给增长系数赋值 this.capacityIncrement = capacityIncrement; } /** *无参构造 */ public Vector() { //调用指定初始容量的有参构造，设置默认初始容量为10 this(10); } /** *指定初始容量的有参构造 */ public Vector(int initialCapacity) { //调用指定初始容量和增长系数的有参构造，设置增长系数为0 this(initialCapacity, 0); } /** * 向elementData末尾添加元素 */ public synchronized boolean add(E e) { modCount++; //确保对象数组elementData有足够的容量，可以将新加入的元素e加进去 ensureCapacityHelper(elementCount + 1); //加入新元素e，elementCount加1 elementData[elementCount++] = e; return true; } public synchronized void addElement(E obj) { modCount++; //确保对象数组elementData有足够的容量，可以将新加入的元素e加进去 ensureCapacityHelper(elementCount + 1); //加入新元素e，elementCount加1 elementData[elementCount++] = obj; } /** * 向elementData指定位置添加元素 */ public void add(int index, E element) { insertElementAt(element, index); } public synchronized void insertElementAt(E obj, int index) { modCount++; // 如果index大于数组个数抛出ArrayIndexOutOfBoundsException异常 if (index > elementCount) { throw new ArrayIndexOutOfBoundsException(index + " > " + elementCount); } //确保对象数组elementData有足够的容量，可以将新加入的元素e加进去 ensureCapacityHelper(elementCount + 1); System.arraycopy(elementData, index, elementData, index + 1, elementCount - index); // 找到位置添加元素 elementData[index] = obj; // 元素个数加一 elementCount++; } /** * @param src 原数组. * @param srcPos 原数组的起始位置. * @param dest 目标数组. * @param destPos 目标数组的起始位置. * @param length 拷贝长度. */ public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length); private void ensureCapacityHelper(int minCapacity) { //元素个数如果大于数组长度就扩容 if (minCapacity - elementData.length > 0) grow(minCapacity); } private void grow(int minCapacity) { int oldCapacity = elementData.length; // 如果指定了增长系数就按照增长系数去增长，没有指定就增加一倍 int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity); //如果新的容量小于数组个数，将数组个数赋值给新容量 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // 如果新的容量大于最大容量，就根据数组个数来决定新的容量大小 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 根据新的容量，将数组拷贝到新的数组并赋值给数组 elementData = Arrays.copyOf(elementData, newCapacity); } private static int hugeCapacity(int minCapacity) { // 如果数组个数小于0抛出OutOfMemoryError异常 if (minCapacity < 0) // overflow throw new OutOfMemoryError(); // 如果最数组个数大于最大容量 就返回最大值，否则返回最大容量 return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
Vector和ArrayList一样都是基于数组实现的，且默认长度都是10，不同的是ArrayList扩容方式是扩大为原来的1.5倍，Vector默认是扩大为原来的两倍。其次Vector的方法都是同步的(Synchronized),是线程安全的，而ArrayList的方法不是。
LinkedList特点
1、java.util.LinkedList<E> :List 接口的实现类和Queue接口子类Deque的实现类
2、内部基于链表实现，增删快、迭代快，随机访问能力较差。
3、链表中的每个节点都是 LinkedList.Node 类型的对象。
4、LinkedList提供额外的get、remove、insert方法在LinkedList的首部或尾部。
5、这些操作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。
6、LinkedList没有同步方法。如果多个线程想访问同一个List，则必须自己实现访问同步。
7、源码分析
// 链表中存放节点个数 transient int size = 0; // 链表头结点 transient Node<E> first; // 链表尾结点 transient Node<E> last; // 节点结构 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; } } /** * 无参构造 */ public LinkedList() { } /** * 有参构造，将集合中元素插入链表 */ public LinkedList(Collection<? extends E> c) { this(); addAll(c); } public boolean addAll(Collection<? extends E> c) { //以size作为插入下标，插入集合中所有 return addAll(size, c); } /** * 以index为下标，添加所有到元素尾部 */ public boolean addAll(int index, Collection<? extends E> c) { //指定位置检查 checkPositionIndex(index); //集合转换为数组 Object[] a = c.toArray(); //获取新增元素数量 int numNew = a.length; //如果新增元素为0就不增加 if (numNew == 0) return false; Node<E> pred, succ; //如果index是size，在链表尾部追加数据 if (index == size) { succ = null;//原节点为空， pred = last;//前置节点为尾节点， } else { //如果index!=size通过遍历获取到原节点 succ = node(index); //原节点的前置节点通过pred进行保留 pred = succ.prev; } //遍历数组，依次插入节点 for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; //生成新节点，前置节点为pred，后置节点为null Node<E> newNode = new Node<>(pred, e, null); //如果前置节点是null,则更新头节点 if (pred == null) first = newNode; else //如果前置节点不为null,则更新前置节点的后置节点为新节点 pred.next = newNode; //设置当前节点为下次的前置节点，为下次插入做准备 pred = newNode; } //在链表尾部加数据时，原节点为null，则更新尾节点为最后插入的节点 if (succ == null) { last = pred; } else { //不是在链表尾部追加数据时,将最后插入的节点的后置节点更新为原节点 pred.next = succ; //原节点的前置节点更新为最后插入的节点 succ.prev = pred; } //更新节点个数 size += numNew; modCount++; return true; } /** * 添加节点 */ public boolean add(E e) { //生成新节点 并插入到 链表尾部， 更新 last/first 节点。 linkLast(e); return true; } //生成新节点 并插入到 链表尾部， 更新 last/first 节点。 void linkLast(E e) { //用l记录尾节点 final Node<E> l = last; //生成新节点 final Node<E> newNode = new Node<>(l, e, null); //更新尾节点 last = newNode; //如果链表为空，更新头节点 if (l == null) first = newNode; else //更新原尾节点的后置节点为新节点 l.next = newNode; //size加1 size++; modCount++; } /** * 添加节点到指定位置 */ public void add(int index, E element) { //指定位置检查 checkPositionIndex(index); //指定位置等于元素个数，在尾节点插入 if (index == size) linkLast(element); else //在中间插入 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) { // 用pred记录指定位置节点(原节点)的前置节点 final Node<E> pred = succ.prev; //生成新节点，前置节点为pred，后置节点为指定位置的节点(原节点) final Node<E> newNode = new Node<>(pred, e, succ); //将新节点作为原节点的前置节点 succ.prev = newNode; //如果原节点的前置节点为空，更新头节点 if (pred == null) first = newNode; else //如果原节点的前置节点不为空则更新前置节点的后置节点为新节点 pred.next = newNode; //更新节点个数 size++; modCount++; } /** * 移除指定位置的节点 */ public E remove(int index) { //指定位置检查 checkElementIndex(index); //移除节点 return unlink(node(index)); } /** * 移除节点 */ E unlink(Node<E> x) { // 记录节点信息 final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; // 删除节点是否为头节点时 if (prev == null) { // 更新头结点为删除节点的后置节点 first = next; } else { //更新删除节点的前置节点的后置节点为删除节点的后置节点 prev.next = next; //删除除节点的前置节点置为null x.prev = null; } // 删除节点是否为尾节点 if (next == null) { // 更新尾结点为删除节点的前置节点 last = prev; } else { //更新删除节点的后置节点的前置节点为删除节点的前置节点 next.prev = prev; //删除除节点的后置节点置为null x.next = null; } //删除除节点的元素值置为null x.item = null; //更新节点数并返回删除节点的元素值 size--; modCount++; return element; } /** * 获取指定位置的节点的元素值 */ public E get(int index) { //指定位置检查 checkElementIndex(index); //获取元素值 return node(index).item; } /** *会根据index处于前半段还是后半段 进行一个折半，以提升查询效率 */ Node<E> node(int index) { //如果index< size/2从头结点开始遍历 if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { //如果index>=size/2从尾结点开始遍历 Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
LinkedList的批量增加是找到添加的位置，然后通过循环数组，依次执行插入节点。LinkedList的移除节点则是先根据index判断及诶单是否存在，再根据所移除节点判断是否为头节点和尾节点，更新移除节点的前置节点和后置节点的信息，然后在把移除节点的信息置为null。查询操作则是根据index是处于前半段还是后半段，进行折半，以此来提高查询效率。
ArrayList和Vector
1、联系
- 都是List接口（List接口继承了Collection接口）的实现类
- 都是基于数组实现的，位置都是有序的，并且数据允许重复
2、区别
- Vector类的方法大部分用synchronized修饰，是线程安全的，而ArrayList是线程不安全的，它的方法之前不是同步的
- 扩容方式不同，Vector是默认增加容量一倍，或者是按照指定的容量增量进行增加。而ArrayList是增加容量为原来的二分之一
ArrayList和LinkedList
1、联系
- 都是List接口（List接口继承了Collection接口）的实现类
- 都是线程不安全的
2、区别
- ArrayList是基于动态数组实现的，LinkedList是基于链表实现的
- 对于随机访问get和set，ArrayList优于LinkedList，因为LinkedList是通过先折半然后遍历节点来获取指定节点，则ArrayList只需要通过索引就可以获取到
- 对于新增和删除操作add和remove，LinkedList优于ArrayList，因为ArrayList要移动数据，而LinkedList只需要记录前后节点即可
牛客网笔试题
1、java 中的集合类包括 ArrayList 、 LinkedList 、 HashMap 等，下列关于集合类描述错误的是？
正确答案: C
A、ArrayList和LinkedList均实现了List接口
B、ArrayList访问速度比LinkedList快
C、随机添加和删除元素时，ArrayList的表现更加快速
D、HashMap实现Map接口，它允许任何类型的键和值对象，并允许将NULL用作键或值
2、实现或继承了Collection接口的是（）
正确答案: B C E
A、Map
B、List
C、Vector
D、Iterator
E、Set
3、ArrayLists和LinkedList的区别，下述说法正确的有？
正确答案: A B C D
A、ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
B、对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。
C、对于新增和删除操作add和remove，LinkedList比较占优势，因为ArrayList要移动数据。
D、ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间。
参考博客链接
https://blog.csdn.net/zxt0601/article/details/77341098
转载请于明显处标明出处