Java集合——List接口学习总结

一、ArrayList实现类

1. 常用方法

	增加：add(int index, E element)删除：remove(int index)  remove(Object o)修改：set(int index, E element)查看：get(int index)判断：常用遍历方式：

		//List集合 遍历：//方式1：普通for循环：System.out.println("---------------------");for(int i = 0;i<list.size();i++){System.out.println(list.get(i));}//方式2：增强for循环：System.out.println("---------------------");for(Object obj:list){System.out.println(obj);}//方式3：迭代器：System.out.println("---------------------");Iterator it = list.iterator();while(it.hasNext()){System.out.println(it.next());}

2. JDK1.8（jdk1.8.0_331）源码下（简要）

重要成员变量和构造方法

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{//重要成员变量private static final int DEFAULT_CAPACITY = 10; //数组默认初始容量private static final Object[] EMPTY_ELEMENTDATA = {}; //实例对象的默认数组,是个空数组private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //与EMPTY_ELEMENTDATA类似，主要用于区分在首次添加元素时判断如何进行扩容transient Object[] elementData; //ArrayList中实际存储元素的Object数组private int size; //计算ArrayList数组的元素数量，不是elementData.lengthprivate static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; //要分配的数组的最大大小,也就是数组极限长度protected transient int modCount = 0;//给迭代器用的，在调用add和remove方法时修改数值//构造方法//空参构造，例如List list = new ArrayList<>();public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; //初始化数组为空数组}//根据传入的initialCapacity，判断初始化数组长度为多少，例如List list1 = new ArrayList<>(100);public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity]; // >0时初始化} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA; //等于0时初始化为空数组} else {throw new IllegalArgumentException("Illegal Capacity: "+ //小于0时，抛出异常，代码健壮性考虑initialCapacity);}}//传入集合Collection下面的实现类，? extends E这个表达式涉及到泛型知识/*List中 <? extends xxx> 定义了List集合的泛型上限，就是定义了一个天花板，输入的类只能从天花板往下找当前类或子类List中<? super xxx> 定义了泛型的下限，就是定义了一个地板，输入的类只能从地板开始往上找当前类或者父类例如：List<Object> a = new ArrayList<>();List<Person> b = new ArrayList<>();List<Student> c = new ArrayList<>();List<? extends Person> list1 = null;List<? super Person> list2 = null;list1 = a;//编译报错，因为list1定义的泛型最大父类（天花板）就是Person，Object类是所有类的父类，超过了定义的天花板Person类list1 = b;//编译正常list1 = c;//编译正常list2 = a;//编译正常list2 = b;//编译正常list2 = c;//编译报错，因为list2定义的泛型最小父类（地板）就是Person，Student类是Person类子类，是低于定义的地板Person类List<? extends Person>:就相当于：List<? extends Person>是List<Person>的父类，也是List<Person的子类>的父类List<? super Person>是List<Person>的父类，也是List<Person的父类>的父类*/public ArrayList(Collection<? extends E> c) {Object[] a = c.toArray(); //转成Obj数组，赋值给aif ((size = a.length) != 0) { //判断数组长度是否为0if (c.getClass() == ArrayList.class) { //判断c的类名是不是ArrayList//是的话就直接赋值给数组elementDataelementData = a; } else {//否则就拷贝复制新数组给elementDataelementData = Arrays.copyOf(a, size, Object[].class); }} else {//数组长度不为0，则实例初始化为空数组elementData = EMPTY_ELEMENTDATA;}}
}

常用方法：add

	//常用方法addpublic boolean add(E e) {ensureCapacityInternal(size + 1);//这一步是计算和判断数组容量elementData[size++] = e; //将传入元素放在数组下标为size的位置,然后size+1,下标是从0开始return true;}private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//如果数组是个空数组的话，返回DEFAULT_CAPACITY和minCapacity的最大值return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;}private void ensureExplicitCapacity(int minCapacity) {modCount++; //迭代器用的计数值，可忽略if (minCapacity - elementData.length > 0) //当 size+1 也就是当前数组元素数量+1，大于当前elementData数组长度时，就需要针对elementData数组扩容grow(minCapacity);}private void grow(int minCapacity) {int oldCapacity = elementData.length; //原先老数组长度int newCapacity = oldCapacity + (oldCapacity >> 1); //新数组长度计算，大概是1.5倍，旧数组长度+(旧数组长度/2)if (newCapacity - minCapacity < 0)newCapacity = minCapacity; //newCapacity < minCapacity时，newCapacity = minCapacityif (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity); //newCapacity超出数组定义的极限长度时的处理elementData = Arrays.copyOf(elementData, newCapacity);}private static int hugeCapacity(int minCapacity) { //超出极限长度时if (minCapacity < 0) // overflowthrow new OutOfMemoryError(); //抛出异常//判断是否大于MAX_ARRAY_SIZE，返回是话Integer.MAX_VALUE，否则MAX_ARRAY_SIZE。//MAX_ARRAY_SIZE之所以是Integer.MAX_VALUE - 8，多出来的8 int（整数） 就等于32 bytes（字节）是防止内存溢出用的，更深入的话涉及JVM和计算机底层了。return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }

样例理解：插入第一个元素时

插入超过10个元素时：

常用方法：remove，这个可以自己看源码，实际原理就是先找到元素e，然后通过System.arraycopy方法把元素e后面所有元素往前移动一位，再把元素末尾置位null

    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);elementData[--size] = null; // clear to let GC do its workreturn oldValue;}public boolean remove(Object o) {if (o == null) {for (int index = 0; index < size; index++)if (elementData[index] == null) {fastRemove(index);return true;}} else {for (int index = 0; index < size; index++)if (o.equals(elementData[index])) {fastRemove(index);return true;}}return false;}private void fastRemove(int index) {modCount++;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}

总结：

• ArrayList底层是使用Object数组实现的，当创建对象时，若使用无参构造，则初始容量为0，此时第一次调用add方法添加就需要扩容为10，元素数量超过数组长度时会进行数组扩容，如需再次扩容为1.5倍。
• 优点：底层是数组，查询效率高，数据可重复
• 缺点：添加或者删除时效率低

3.在JDK1.7和1.8中的区别

4.ListIterator迭代器

出错原因：就是迭代器it和list同时对集合进行操作导致。
出错详解：调用add方法时，ArrayList成员变量里操作次数modCount发生了改变，例如上述代码调用到的add(“ee”)时ArrayList中的成员变量modCount=5（执行了5次add）。list.iterator()返回的Iterator iterator实际是ArrayList源码中内部类Itr实现了接口Iterator。在ArrayList源码中内部类Itr有个成员变量expectedModCount（预期的操作次数）记录，在调用完add(“kk”)后modCount=6，但是expectedModCount还是5，然后继续while走到if时调用next()方法时发现两个变量不一致抛出了并发修改异常。
源码图解：

解决方案：事情让一个“人”做 --》引入新的迭代器：ListIterator。迭代和添加操作都是靠ListIterator来完成的，ListIterator底层实际就通过在同一个数组上，用指针的概念在调整位置。

实际上看源码就知道做了什么事情，就是ArrayList源码实现接口ListIterator自己实现了add方法，把expectedModCount和modCount同步一下。同时内部类Itr实现了remove方法，跟内部类ListItr的add方法是一个道理。

5.面试题：iterator(),Iterator,Iterable关系

1.iterator()是Iterable接口中定义的方法，用于返回一个迭代器（Iterator）对象。

2.Iterator接口是Java集合框架中用于遍历集合元素的标准接口，它定义了一些方法，如hasNext()、next()、remove()等，用于遍历集合中的元素并对其进行操作。

3.Iterable接口是Java集合框架中用于表示“可迭代”的对象的标准接口，它定义了一个iterator()方法，用于返回一个迭代器（Iterator）对象，从而可以遍历集合中的元素。

hashNext()、next()方法源码简化

二、Vector实现类

1. 与ArrayList区别与联系

区别：

• Vector底层扩容长度为原数组2倍，线程安全，效率低
• ArrayList底层扩容长度为原数组1.5倍，线程不安全，效率高

联系：

• 底层都是数组，具有数组的优缺点（查询快，增删慢）
• 都继承了AbstractList类并实现List接口

add方法源码简化

public class Vector<E> extends AbstractList<E> 
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{protected Object[] elementData; //数组protected int elementCount;//元素个数protected int capacityIncrement;//扩容数量private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;public Vector() {//创建时默认数组长度为10，ArrayList创建出来的时候是空数组，第一次调用add才会创建长度10的数组this(10); }public Vector(int initialCapacity) {this(initialCapacity, 0);}public Vector(int initialCapacity, int capacityIncrement) {super();this.elementData = new Object[initialCapacity];this.capacityIncrement = capacityIncrement;}public Vector(Collection<? extends E> c) {Object[] a = c.toArray();elementCount = a.length;if (c.getClass() == ArrayList.class) {elementData = a;} else {elementData = Arrays.copyOf(a, elementCount, Object[].class);}}//为什么Vector是线程安全的，因为方法上都有synchronized关键字进行同步public synchronized boolean add(E e) {modCount++;ensureCapacityHelper(elementCount + 1);elementData[elementCount++] = e;return true;}private void ensureCapacityHelper(int minCapacity) {// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;//这里就是两倍扩容的代码了，在capacityIncrement一直为0的时候，就是oldCapacity+oldCapacityint 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);}}

三、 LinkedList实现类

1. 简要原理图

2. 源码分析（简化版）

JDK1.7和JDK1.8的LinkedList的源码是一致的

public class LinkedList<E>{//E是一个泛型，具体的类型要在实例化的时候才会最终确定transient int size = 0;//集合中元素的数量//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 Node<E> first;//链表的首节点ransient Node<E> last;//链表的尾节点//空构造器：public LinkedList() {}//添加元素操作：public boolean add(E e) {linkLast(e);return true;}void linkLast(E e) {//添加的元素efinal Node<E> l = last;//将链表中的last节点给l 如果是第一个元素的话 l为null//将元素封装为一个Node具体的对象：final Node<E> newNode = new Node<>(l, e, null);//将链表的last节点指向新的创建的对象：last = newNode;if (l == null)//如果添加的是第一个节点first = newNode;//将链表的first节点指向为新节点else//如果添加的不是第一个节点 l.next = newNode;//将l的下一个指向为新的节点size++;//集合中元素数量加1操作modCount++;}//获取集合中元素数量public int size() {return size;}//通过索引得到元素：public E get(int index) {checkElementIndex(index);//健壮性考虑return node(index).item;}Node<E> node(int index) {//如果index在链表的前半段，那么从前往后找if (index < (size >> 1)) {Node<E> x = first;for (int i = 0; i < index; i++)x = x.next;return x;} else {//如果index在链表的后半段，那么从后往前找Node<E> x = last;for (int i = size - 1; i > index; i--)x = x.prev;return x;}}
}

四、其他问题

1.ArrayList源码和Vector源码中的都会有一个成员变量private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8，这个数组容量上限MAX_ARRAY_SIZE为什么要-8？

其实源码中成员变量上面就有英文解释，简要回答就是保证跨平台，有些虚拟机数组会有会有保留字，出于安全性和健壮性考虑所以做了长度限制。可参考以下博客说明。
https://blog.csdn.net/qq_44734036/article/details/118982215

为什么是-8可以参考以下博客说明。
https://blog.csdn.net/fisherish/article/details/117134717

实际上ArrayList能不能直接到达Integer.MAX_VALUE这个，我认为是可以的，ArrayList源码扩容函数里面实际是允许的，只是一开始new ArrayList<>(Integer.MAX_VALUE);这个会报错，但是如果进行扩容操作的话能达到。这个只是从源码上进行的推论，没有实际能验证过。
以下为源码说明：