1、为什么使用集合框架？
假设，一个班级有30个人，我们需要存储学员的信息，是不是我们可以用一个一维数组就解决了？那换一个问题，一个网站每天要存储的新闻信息，我们知道新闻是可以实时发布的，我们并不知道需要多大的空间去存储，我要是去设置一个很大的数组，要是没有存满，或者不够用，都会影响我们，前者浪费的空间，后者影响了业务！
如果并不知道程序运行时会需要多少对象，或者需要更复杂的方式存储对象，那我们就可以使用Java的集合框架
2、集合框架包含的内容
Java集合框架提供了一套性能优良，使用方便的接口和类，他们位于java.util包中。
【接口和具体类】
【算法】
Collections 类提供了对集合进行排序，遍历等多种算法实现！
Java集合类里最基本的接口有：
Collection 接口存储一组不唯一，无序的对象
List 接口存储一组不唯一，有序的对象。
Set 接口存储一组唯一，无序的对象
Map 接口存储一组键值对象，提供key到value的映射
我们现在有4只小狗，我们如何存储它的信息，获取总数，并能够逐条打印狗狗信息！
分析：通过List 接口的实现类ArrayList 实现该需求.
class Dog {
private String name; //构造。。。set、get、。。。toString（）
}
public class TestArrayList {
public static void main(String[] args) { //创建ArrayList对象 , 并存储狗狗
List dogs = new ArrayList();
dogs.add(new Dog("小狗一号"));
dogs.add(new Dog("小狗二号"));
dogs.add(new Dog("小狗三号"));
dogs.add(2, new Dog("小狗四号"));// 添加到指定位置
// .size() ： ArrayList大小
System.out.println("共计有" + dogs.size() + "条狗狗。");
System.out.println("分别是："); // .get(i) ： 逐个获取个元素
for (int i = 0; i < dogs.size(); i++) {
Dog dog = (Dog) dogs.get(i);
System.out.println(dog.getName());
}
}
}
分析：使用List接口提供的remove()、contains()方法
【常用方法】
public boolean add(E e) //将指定的元素追加到此列表的末尾。
public void add(int index,E element)//在此列表中的指定位置插入指定的元素。
//将当前位于该位置的元素（如果有）和任何后续元素（向其索引添加一个）移动。
public int size() //返回此列表中的元素数。
public E get(int index) //返回此列表中指定位置的元素。
public boolean contains(Object o) //如果此列表包含指定的元素，则返回true 。
//更正式地说，返回true当且仅当此列表包含至少一个元素e这样(o==null ? e==null : o.equals(e))。
public E remove(int index) //删除该列表中指定位置的元素。 将任何后续元素移动到左侧（从其索引中减去一个元素）。
public boolean remove(Object o) //从列表中删除指定元素的第一个出现（如果存在）。
//如果列表不包含该元素，则它不会更改。 更正式地，删除具有最低索引i的元素，使得(o==null ? get(i)==null : o.equals(get(i))) （如果存在这样的元素）。
//如果此列表包含指定的元素（或等效地，如果此列表作为调用的结果而更改），则返回true 。
ArrayList和Collection的关系：
ArrayList的数据结构是
说明：底层的数据结构就是数组，数组元素类型为Object类型，即可以存放所有类型数据。我们对ArrayList类的实例的所有的操作底层都是基于数组的。
IDEA快捷键：Ctrl+H
ArrayList的继承结构：
【分析】
为什么要先继承AbstractList，而让AbstractList先实现List？而不是让ArrayList直接实现List？
这里是有一个思想，接口中全都是抽象的方法，而抽象类中可以有抽象方法，还可以有具体的实现方法，正是利用了这一点，让AbstractList是实现接口中一些通用的方法，而具体的类，如ArrayList就继承这个AbstractList类，拿到一些通用的方法，然后自己在实现一些自己特有的方法，这样一来，让代码更简洁，就继承结构最底层的类中通用的方法都抽取出来，先一起实现了，减少重复代码。所以一般看到一个类上面还有一个抽象类，应该就是这个作用。
ArrayList实现了哪些接口？
List接口：我们会出现这样一个疑问，在查看了ArrayList的父类 AbstractList也实现了List接口，那为什么子类ArrayList还是去实现一遍呢？
RandomAccess接口：这个是一个标记性接口，通过查看api文档，它的作用就是用来快速随机存取，有关效率的问题，在实现了该接口的话，那么使用普通的for循环来遍历，性能更高，例如ArrayList。而没有实现该接口的话，使用Iterator来迭代，这样性能更高，例如linkedList。所以这个标记性只是为了让我们知道我们用什么样的方式去获取数据性能更好。
Cloneable接口：实现了该接口，就可以使用Object.Clone()方法了。
Serializable接口：实现该序列化接口，表明该类可以被序列化，什么是序列化？简单的说，就是能够从类变成字节流传输，然后还能从字节流变成原来的类。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
// 版本号
private static final long serialVersionUID = 8683452581122892189L;
// 缺省容量
private static final int DEFAULT_CAPACITY = 10;
// 空对象数组
private static final Object[] EMPTY_ELEMENTDATA = {};
// 缺省空对象数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 元素数组
transient Object[] elementData;
// 实际元素大小，默认为0
private int size;
// 最大数组容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
}
通过IDEA查看源码，看到ArrayList有三个构造方法：
/*
Constructs an empty list with an initial capacity of ten.
这里就说明了默认会给10的大小，所以说一开始arrayList的容量是10.
*/
//ArrayList中储存数据的其实就是一个数组，这个数组就是elementData.
public ArrayList() {
super(); //调用父类中的无参构造方法，父类中的是个空的构造方法
this.elementData = EMPTY_ELEMENTDATA;
//EMPTY_ELEMENTDATA：是个空的Object[]， 将elementData初始化，
//elementData 也是个Object[]类型。
//空的Object[]会给默认大小10
//(注意这里说的大小不是数组的大小而是ArrayList的大小--也就是MAX_ARRAY_SIZE的值,这里说的10是默认的缺省容量int DEFAULT_CAPACITY = 10;)
//等会会解释什么时候赋值的。
}
/*
Constructs an empty list with the specified initial capacity.
构造具有指定初始容量的空列表。
@param initialCapacity the initial capacity of the list
初始容量列表的初始容量
@throws IllegalArgumentException if the specified initial capacity is negative 如果指定的初始容量为负，则为IllegalArgumentException
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//将自定义的容量大小当成初始化 initialCapacity 的大小
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA; //等同于无参构造方法
} else {
//判断如果自定义大小的容量小于0，则报下面这个非法数据异常
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
}
}
/*
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(); //转换为数组
//每个集合的toarray()的实现方法不一样，所以需要判断一下，如果不是Object[].class类 型，那么就需要使用ArrayList中的方法去改造一下。
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;
}
}
这个构造方法不常用，举个例子就能明白什么意思
举个例子： Strudent exends Person ， ArrayList、 Person这里就是泛型 ， 我还有一个Collection、由于这个Student继承了Person，那么根据这个构造方法，我就可以把这个Collection转换为ArrayList， 这就是这个构造方法的作用 。
【总结】ArrayList的构造方法就做一件事情，就是初始化一下储存数据的容器，其实本质上就是一个数组，在其中就叫elementData。
/**
* Appends the specified element to the end of this list.
* 添加一个特定的元素到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) {
//确定内部容量是否够了，size是数组中数据的个数，因为要添加一个元素，所以size+1，先判 断size+1的这个个数数组能否放得下，就在这个方法中去判断是否数组.length是否够用了。
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;//在数据中正确的位置上放上元素e，并且size++
return true;
}
【分析：ensureCapacityInternal(xxx); 确定内部容量的方法】
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//判断初始化的elementData是不是空的数组，也就是没有长度
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//因为如果是空的话，minCapacity=size+1；其实就是等于1，空的数组没有长度就存 放不了，所以要修改容量，因为如果是空的那么size+1就为1，那么1《10这里就将minCapacity变成10，也就是默认大小，但是在这里，还没有真正的初始化这个 elementData的大小。
return Math.max(DEFAULT_CAPACITY, minCapacity);//虽然是比大小但是如果是空的那么minCapacity=size(0)+1=1就必定小于DEFAULT_CAPACITY(10)
}
//确认实际的容量，上面只是将minCapacity=10，这个方法就是真正的判断elementData是否 够用
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
//minCapacity如果大于了实际elementData的长度，那么就说明elementData数组的长度不 够用，不够用那么就要增加elementData的length。这里有的同学就会模糊minCapacity到底是什么 呢，这里给你们分析一下
/*第一种情况：由于elementData初始化时是空的数组，那么第一次add的时候， minCapacity=size+1；也就minCapacity=1，在上一个方法(确定内部容量ensureCapacityInternal)就会判断出是空的数组，就会给将minCapacity=10，到这一步为止， 还没有改变elementData的大小。
第二种情况：elementData不是空的数组了，那么在add的时候，minCapacity=size+1；也就是 minCapacity代表着elementData中增加之后的实际数据个数，拿着它判断elementData的length 是否够用，如果length 不够用，那么肯定要扩大容量，不然增加的这个元素就会溢出。*/
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//arrayList核心的方法，能扩展数组大小的真正秘密。
private void grow(int minCapacity) {
// overflow-conscious code
//将扩充前的elementData大小给oldCapacity
int oldCapacity = elementData.length;
//newCapacity就是1.5倍的oldCapacity
int newCapacity = oldCapacity + (oldCapacity >> 1);
//这句话就是适应于elementData就空数组的时候，length=0，那么oldCapacity=0， newCapacity=0，所以这个判断成立，在这里就是真正的初始化elementData的大小了，就是为10. 前面的工作都是准备工作。
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果newCapacity超过了最大的容量限制，就调用hugeCapacity，也就是将能给的最大值给 newCapacity
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = (minCapacity);
// minCapacity is usually close to size, so this is a win:
//新的容量大小已经确定好了，就copy数组，改变容量大小咯。
elementData = Arrays.copyOf(elementData, newCapacity);
}
//这个就是上面用到的方法，很简单，就是用来赋最大值。
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//如果minCapacity都大于MAX_ARRAY_SIZE，那么就Integer.MAX_VALUE返回，反之将 MAX_ARRAY_SIZE返回。因为maxCapacity是三倍的minCapacity，可能扩充的太大了，就用 minCapacity来判断了。
//Integer.MAX_VALUE:2147483647 MAX_ARRAY_SIZE：2147483639 也就是说最大也就能 给到第一个数值。还是超过了这个限制，就要溢出了。相当于arraylist给了两层防护。
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
public void add(int index, E element) {
//检查index也就是插入的位置是否合理。
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
//这个方法就是用来在插入元素之后，要将index之后的元素都往后移一位，
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//在目标位置上存放元素
elementData[index] = element;
size++;
}
【分析：rangeCheckForAdd(index)】
private void rangeCheckForAdd(int index) {
//插入的位置肯定不能大于size 和小于0
if (index > size || index < 0) //如果是，就报这个越界异常
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
【System.arraycopy(...)：就是将elementData在插入位置后的所有元素，往后面移一位.】
nativeg关键字调用其他语言的代码
Java平台有个用户和本地C代码进行互操作的API，称为Java Native Interface (Java本地接口)。
public static native void arraycopy(Object src,
int srcPos,
Object dest,
int destPos,
int length)
src：源对象
srcPos：源对象对象的起始位置
dest：目标对象
destPost：目标对象的起始位置
length：从起始位置往后复制的长度。
//这段的大概意思就是解释这个方法的用法，复制src到dest，复制的位置是从src的srcPost开始， 到srcPost+length-1的位置结束，复制到destPost上，从destPost开始到destPost+length-1 的位置上，
position, to the specified position of the destination array. A subsequence of array components are copied from the source array referenced by src to the destination array referenced by dest. The number of components copied is equal to the length argument. The components at positions srcPos through srcPos+length-1 in the source array are copied into positions destPos through destPos+length-1, respectively, of the destination array
//告诉你复制的一种情况，如果A和B是一样的，那么先将A复制到临时数组C，然后通过C复制到B，用了 一个第三方参数
If the src and dest arguments refer to the same array object, then the copying is performed as if the components at positions srcPos through srcPos+length-1 were first copied to a temporary array with length components and then the contents of the temporary array were copied into positions destPos through destPos+length-1 of the destination array.
//这一大段，就是来说明会出现的一些问题，NullPointerException和 IndexOutOfBoundsException 还有ArrayStoreException 这三个异常出现的原因。
If dest is null, then a NullPointerException is thrown. If src is null, then a NullPointerException is thrown and the destination array is not modified. Otherwise, if any of the following is true, an ArrayStoreException is thrown and the destination is not modified: The src argument refers to an object that is not an array. The dest argument refers to an object that is not an array. The src argument and dest argument refer to arrays whose component types are different primitive types. The src argument refers to an array with a primitive component type and the dest argument refers to an array with a reference component type. The src argument refers to an array with a reference component type and the dest argument refers to an array with a primitive component type. Otherwise, if any of the following is true, an IndexOutOfBoundsException is thrown and the destination is not modified: The srcPos argument is negative. The destPos argument is negative. The length argument is negative. srcPos+length is greater than src.length, the length of the source array. destPos+length is greater than dest.length, the length of the destination array
//这里描述了一种特殊的情况，就是当A的长度大于B的长度的时候，会复制一部分，而不是完全失败。
Otherwise, if any actual component of the source array from position srcPos through srcPos+length-1 cannot be converted to the component type of the destination array by assignment conversion, an ArrayStoreException is thrown. In this case, let k be the smallest nonnegative integer less than length such that src[srcPos+k] cannot be converted to the component type of the destination array; when the exception is thrown, source array components from positions srcPos through srcPos+k-1 will already have been copied to destination array positions destPos through destPos+k-1 and no other positions of the destination array will have been modified. (Because of the restrictions already itemized, this paragraph effectively applies only to the situation where both arrays have component types that are reference types.)
正常情况下会扩容1.5倍，特殊情况下（新扩展数组大小已经达到了最大值）则只取最大值。
当我们调用add方法时，实际上的函数调用如下：
说明：程序调用add，实际上还会进行一系列调用，可能会调用到grow，grow可能会调用hugeCapacity
【举例】
List<Integer> lists = new ArrayList<Integer>;
lists.add(8);
说明：初始化lists大小为0，调用的ArrayList()型构造函数，那么在调用lists.add(8)方法时，会经过怎样的步骤呢？下图给出了该程序执行过程和最初与最后的elementData的大小。
说明：我们可以看到，在add方法之前开始elementData = {}；调用add方法时会继续调用，直至grow，最后elementData的大小变为10，之后再返回到add函数，把8放在elementData[0]中。
【举例说明二】
List<Integer> lists = new ArrayList<Integer>(6);
lists.add(8);
说明：我们可以知道，在调用add方法之前，elementData的大小已经为6，之后再进行传递，不会进行扩容处理。
其实这几个删除方法都是类似的。我们选择几个讲，其中fastRemove(int)方法是private的，是提供给remove(Object)这个方法用的。
public E remove(int index) {
rangeCheck(index);//检查index的合理性
modCount++;//这个作用很多，比如用来检测快速失败的一种标志。
E oldValue = elementData(index);
//通过索引直接找到该元素--这里elementData是一个方法
/*
E elementData(int index) {
return (E) elementData[index];
}
*/
int numMoved = size - index - 1;//计算要移动的位数。
if (numMoved > 0)
//这个方法也已经解释过了，就是用来移动元素的。
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//将--size上的位置赋值为null，让gc(垃圾回收机制)更快的回收它。
elementData[--size] = null; // clear to let GC do its work
//返回删除的元素.
return oldValue;
}
//感觉这个不怎么要分析吧，都看得懂，就是通过元素来删除该元素，就依次遍历，如果有这个元素， 就将该元素的索引传给fastRemobe(index)，使用这个方法来删除该元素，
//fastRemove(index)方法的内部跟remove(index)的实现几乎一样，这里最主要是知道 arrayList可以存储null值
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;
}
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
public boolean removeAll(Collection<?> c) {
return batchRemove(c, false);//批量删除
}
//这个方法，用于两处地方，如果complement为false，则用于removeAll如果为true，则给 retainAll()用，retainAll（）是用来检测两个集合是否有交集的。
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData; //将原集合，记名为A
int r = 0, w = 0; //r用来控制循环，w是记录有多少个交集
boolean modified = false;
try {
for (; r < size; r++)
//参数中的集合C一次检测集合A中的元素是否有，
if (c.contains(elementData[r]) == complement)
//有的话，就给集合A
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
//如果contains方法使用过程报异常
if (r != size) {
//将剩下的元素都赋值给集合A，
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
//这里有两个用途，在removeAll()时，w一直为0，就直接跟clear一样，全是为 null。
//retainAll()：没有一个交集返回true，有交集但不全交也返回true，而两个集合 相等的时候，返回false，所以不能根据返回值来确认两个集合是否有交集，而是通过原集合的大小是否 发生改变来判断，如果原集合中还有元素，则代表有交集，而元集合没有元素了，说明两个集合没有交集。
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
【set()方法】
说明：获取指定下标索引的元素值
public E set(int index, E element) {
// 检验索引是否合法
rangeCheck(index);
// 旧值
E oldValue = elementData(index);
// 赋新值
elementData[index] = element;
// 返回旧值
return oldValue;
}
【indexOf()方法】
说明：从头开始查找与指定元素相等的元素，注意，是可以查找null元素的，意味着ArrayList中可以存放null元素的。与此函数对应的lastIndexOf，表示从尾部开始查找。
// 从首开始查找数组里面是否存在指定元素
public int indexOf(Object o) {
if (o == null) {// 查找的元素为空
for (int i = 0; i < size; i++) // 遍历数组，找到第一个为空的元素，返回下标
if (elementData[i]==null)
return i;
} else {// 查找的元素不为空
for (int i = 0; i < size; i++)
if (o.equals(elementData[i])) // 遍历数组，找到第一个和指定元素相等的元 素，返回下标
return i;
}
// 没有找到，返回空
return -1;
}
【get()方法】
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
说明：get函数会检查索引值是否合法（只检查是否大于size，而没有检查是否小于0），值得注意的是，在get函数中存在element函数，element函数用于返回具体的元素，具体函数如下：
E elementData(int index) { return (E) elementData[index]; }
说明：返回的值都经过了向下转型（Object -> E），这些是对我们应用程序屏蔽的小细节。
在集合的任何位置（头部，中间，尾部）添加，获取，删除狗狗对象！
分析：插入，删除操作频繁时，可使用LinkedList来提高效率。
LinkedList提供对头部和尾部元素进行添加和删除操作的方法！
【LinkedList的特殊方法】
public void addFirst(E e) //在该列表开头插入指定的元素。
public void addLast(E e) //将指定的元素追加到此列表的末尾。 这个方法相当于add(E) 。
public E getFirst() //返回此列表中的第一个元素。
public E getLast() //返回此列表中的最后一个元素。
public E removeFirst() //从此列表中删除并返回第一个元素。
public E removeLast() //从此列表中删除并返回最后一个元素。
LinkedList是一种可以在任何位置进行高效地插入和移除操作的有序序列，它是基于双向链表实现的。
LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
LinkedList 实现 List 接口，能对它进行队列操作。
LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
LinkedList 是非同步的。
【基础知识补充】
单向链表：
单向循环链表：
双向链表：
双向循环链表：
【LinkedList的数据结构】
如上图所示，LinkedList底层使用的双向链表结构，有一个头结点和一个尾结点，双向链表意味着我们可以从头开始正向遍历，或者是从尾开始逆向遍历，并且可以针对头部和尾部进行相应的操作。
在我们平常中，我们只知道一些常识性的特点：
那我们通过API去查看它的一些特性
1）Doubly-linked list implementation of the `List` and `Deque` interfaces. Implements all optional list operations, and permits all elements (including `null`).
这告诉我们，linkedList是一个双向链表，并且实现了List和Deque接口中所有的列表操作，并且能存 储任何元素，包括null，这里我们可以知道linkedList除了可以当链表使用，还可以当作队列使用，并 能进行相应的操作。
2）All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.
这个告诉我们，linkedList在执行任何操作的时候，都必须先遍历此列表来靠近通过index查找我们所 需要的的值。通俗点讲，这就告诉了我们这个是顺序存取，每次操作必须先按开始到结束的顺序遍历，随 机存取，就是arrayList，能够通过index。随便访问其中的任意位置的数据，这就是随机列表的意思。
通过API再次总结一下LinkedList的特性：
异步，也就是非线程安全
双向链表。由于实现了list和Deque接口，能够当作队列来使用。
是顺序存取结构（注意和随机存取结构两个概念搞清楚）
【分析】
我们可以看到，linkedList在最底层，说明他的功能最为强大，并且细心的还会发现，arrayList有四层，这里多了一层AbstractSequentialList的抽象类，为什么呢？
通过API我们会发现：
public abstract class AbstractSequentialList<E> extends AbstractList<E>
//这里第一段就解释了这个类的作用，这个类为实现list接口提供了一些重要的方法，
//尽最大努力去减少实现这个“顺序存取”的特性的数据存储(例如链表)，
//对于随机存取数据(例如数组)的类应该优先使用AbstractList
//从上面就可以大概知道，AbstractSwquentialList这个类是为了减少LinkedList这种顺序存取 的类的代码复杂度而抽象的一个类，
This class provides a skeletal implementation of the List interface to minimize the effort required to implement this interface backed by a "sequential access" data store (such as a linked list). For random access data (such as an array), AbstractList should be used in preference to this class.
//这一段大概讲的就是这个AbstractSequentialList这个类和AbstractList这个类是完全相反。比如get、add这个方法的实现
This class is the opposite of the AbstractList class in the sense that it implements the "random access" methods (get(int index), set(int index, E element), add(int index, E element) and remove(int index)) on top of the list‘s list iterator, instead of the other way around.
//这里就是讲一些我们自己要继承该类，该做些什么事情，一些规范。
To implement a list the programmer needs only to extend this class and provide implementations for the listIterator and size methods. For an unmodifiable list, the programmer need only implement the list iterator‘s hasNext, next, hasPrevious, previous and index methods.
For a modifiable list the programmer should additionally implement the list iterator‘s set method. For a variable-size list the programmer should additionally implement the list iterator‘s remove and add methods.
The programmer should generally provide a void (no argument) and collection constructor, as per the recommendation in the Collection interface specification.
【接口实现分析】
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
}
List接口：列表，add、set、等一些对列表进行操作的方法
Deque接口：有队列的各种特性，
Cloneable接口：能够复制，使用那个copy方法。
Serializable接口：能够序列化。
应该注意到没有RandomAccess：那么就推荐使用iterator，在其中就有一个foreach，增强的for循环，其中原理也就是iterator，我们在使用的时候，使用foreach或者iterator都可以。
RandomAccess是一个标志接口
表明实现这个这个接口的 List 集合是支持快速随机访问的。也就是说，实现了这个接口的集合是支持 快速随机访问 策略的。
同时，官网还特意说明了，如果是实现了这个接口的 List，那么使用for循环的方式获取数据会优于用迭代器获取数据
for (int i=0, n=list.size(); i < n; i++)
list.get(i);
for (Iterator i=list.iterator(); i.hasNext(); )
i.next();
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
// 实际元素个数
transient int size = 0;
// 头结点
transient Node<E> first;
// 尾结点
transient Node<E> last;
}
transient关键字:
LinkedList的属性非常简单，一个头结点、一个尾结点、一个表示链表中实际元素个数的变量。注意，头结点、尾结点都有transient关键字修饰，这也意味着在序列化时该域是不会序列化的
两个构造方法(两个构造方法都是规范规定需要写的）
【空参构造函数】
public LinkedList() {
}
【有参构造函数】
//将集合c中的各个元素构建成LinkedList链表。
public LinkedList(Collection<? extends E> c) {
// 调用无参构造函数
this();
// 添加集合中所有的元素
addAll(c);
}
说明：会调用无参构造函数，并且会把集合中所有的元素添加到LinkedList中
//根据前面介绍双向链表就知道这个代表什么了，linkedList的奥秘就在这里。
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;
}
}
说明：内部类Node就是实际的结点，用于存放实际元素的地方。
public boolean add(E e) {
// 添加到末尾
linkLast(e);
return true;
}
说明：add函数用于向LinkedList中添加一个元素，并且添加到链表尾部。具体添加到尾部的逻辑是由linkLast函数完成的。
【LinkLast(XXXXX)】
/**
* Links e as last element.
*/
void linkLast(E e) {
final Node<E> l = last;//临时节点l(L的小写)保存last，也就是l指向了最后一个节点
final Node<E> newNode = new Node<>(l, e, null);//将e封装为节点，并且e.prev指向了最后一个节点
last = newNode;//newNode成为了最后一个节点，所以last指向了它
if (l == null)//判断是不是一开始链表中就什么都没有，如果没有，则newNode就成为了第一个节点，first和last都要指向它
first = newNode;
else //正常的在最后一个节点后追加，那么原先的最后一个节点的next就要指向现在真正的最后一个节点，原先的最后一个节点就变成了倒数第二个节点
l.next = newNode;
size++;//添加一个节点，size自增
modCount++;
}
说明：对于添加一个元素至链表中会调用add方法 -> linkLast方法。
【举例一】
List<Integer> lists = new LinkedList<Integer>();
lists.add(5);
lists.add(6);
首先调用无参构造函数，之后添加元素5，之后再添加元素6。具体的示意图如下：
上图的表明了在执行每一条语句后，链表对应的状态。
addAll有两个重载函数，addAll(Collection<? extends E>)型和addAll(int, Collection<? extends E>)型，我们平时习惯调用的addAll(Collection<? extends E>)型会转化为addAll(int, Collection<? extends E>)型。
public boolean addAll(Collection<? extends E> c) {
//继续往下看
return addAll(size, c);
}
addAll(size，c)：这个方法，能包含三种情况下的添加，我们这里分析的只是构造方法，空链表的情况，看的时候只需要按照不同的情况分析下去就行了。
//真正核心的地方就是这里了，记得我们传过来的是size，c
public boolean addAll( int index, Collection<? extends E> c) {
//检查index这个是否为合理。这个很简单，自己点进去看下就明白了。
checkPositionIndex(index);
//将集合c转换为Object数组 a
Object[] a = c.toArray();
//数组a的长度numNew，也就是由多少个元素
int numNew = a.length; if (numNew == 0)
//集合c是个空的，直接返回false，什么也不做。
return false;
//集合c是非空的，定义两个节点(内部类)，每个节点都有三个属性，item、next、prev。注 意：不要管这两个什么含义，就是用来做临时存储节点的。这个Node看下面一步的源码分析，Node就是 linkedList的最核心的实现，可以直接先跳下一个去看Node的分析
Node<E> pred, succ;
//构造方法中传过来的就是index==size
if (index == size) {
//linkedList中三个属性：size、first、last。 size：链表中的元素个数。 first：头节点 last：尾节点，就两种情况能进来这里
//情况一、：构造方法创建的一个空的链表，那么size=0，last、和first都为null。 linkedList中是空的。什么节点都没有。succ=null、pred=last=null
//情况二、：链表中有节点，size就不是为0，first和last都分别指向第一个节点，和最 后一个节点，在最后一个节点之后追加元素，就得记录一下最后一个节点是什么，所以把last保存到 pred临时节点中。
succ = null;
pred = last;
} else {
//情况三、index！=size，说明不是前面两种情况，而是在链表中间插入元素，那么就得知 道index上的节点是谁，保存到succ临时节点中，然后将succ的前一个节点保存到pred中，这样保存 了这两个节点，就能够准确的插入节点了
//举个简单的例子，有2个位置，1、2、如果想插数据到第二个位置，双向链表中，就需要知 道第一个位置是谁，原位置也就是第二个位置上是谁，然后才能将自己插到第二个位置上。如果这里还不 明白，先看一下文章开头对于各种链表的删除，add操作是怎么实现的。
succ = node(index);
pred = succ.prev;
}
//前面的准备工作做完了，将遍历数组a中的元素，封装为一个个节点。
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
//pred就是之前所构建好的，可能为null、也可能不为null，为null的话就是属于情况 一、不为null则可能是情况二、或者情况三
Node<E> newNode = new Node<>(pred, e, null);
//如果pred==null，说明是情况一，构造方法，是刚创建的一个空链表，此时的newNode 就当作第一个节点，所以把newNode给first头节点
if (pred == null)
first = newNode;
else
//如果pred！=null，说明可能是情况2或者情况3，如果是情况2，pred就是last， 那么在最后一个节点之后追加到newNode，如果是情况3，在中间插入，pred为原index节点之前的一 个节点，将它的next指向插入的节点，也是对的
pred.next = newNode;
//然后将pred换成newNode，注意，这个不在else之中，请看清楚了。
pred = newNode;
}
if (succ == null) {
/*如果succ==null，说明是情况一或者情况二，
情况一、构造方法，也就是刚创建的一个空链表，pred已经是newNode了， last=newNode，所以linkedList的first、last都指向第一个节点。
情况二、在最后节后之后追加节点，那么原先的last就应该指向现在的最后一个节点 了，就是newNode。*/
last = pred;
} else {
//如果succ！=null，说明可能是情况三、在中间插入节点，举例说明这几个参数的意义， 有1、2两个节点，现在想在第二个位置插入节点newNode，根据前面的代码，pred=newNode， succ=2，并且1.next=newNode，已经构建好了，pred.next=succ，相当于在newNode.next = 2； succ.prev = pred，相当于 2.prev = newNode， 这样一来，这种指向关系就完成了。 first和last不用变，因为头节点和尾节点没变
pred.next = succ;
//。。
succ.prev = pred;
}
//增加了几个元素，就把 size = size +numNew 就可以了
size += numNew;
modCount++;
return true;
}
说明：参数中的index表示在索引下标为index的结点（实际上是第index + 1个结点）的前面插入。
在addAll函数中，addAll函数中还会调用到node函数，get函数也会调用到node函数，此函数是根据索引下标找到该结点并返回，具体代码如下：
Node<E> node(int index) {
// 判断插入的位置在链表前半段或者是后半段
if (index < (size >> 1)) { // 插入位置在前半段
Node<E> x = first;
for (int i = 0; i < index; i++) // 从头结点开始正向遍历
x = x.next;
return x; // 返回该结点
} else { // 插入位置在后半段
Node<E> x = last;
for (int i = size - 1; i > index; i--) // 从尾结点开始反向遍历
x = x.prev;
return x; // 返回该结点
}
}
说明：在根据索引查找结点时，会有一个小优化，结点在前半段则从头开始遍历，在后半段则从尾开始遍历，这样就保证了只需要遍历最多一半结点就可以找到指定索引的结点。
举例说明调用addAll函数后的链表状态：
List<Integer> lists = new LinkedList<Integer>();
lists.add(5);
lists.addAll(0, Arrays.asList(2, 3, 4, 5));
addAll()中的一个问题：
? 在addAll函数中，传入一个集合参数和插入位置，然后将集合转化为数组，然后再遍历数组，挨个添加数组的元素，但是问题来了，为什么要先转化为数组再进行遍历，而不是直接遍历集合呢
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If this list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* {@code i} such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
* (if such an element exists). Returns {@code true} if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return {@code true} if this list contained the specified element
*/
//首先通过看上面的注释，我们可以知道，如果我们要移除的值在链表中存在多个一样的值，那么我们 会移除index最小的那个，也就是最先找到的那个值，如果不存在这个值，那么什么也不做。
public boolean remove(Object o) {
//这里可以看到，linkedList也能存储null
if (o == null) {
//循环遍历链表，直到找到null值，然后使用unlink移除该值。下面的这个else中也一样
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
【unlink(xxxx)】
/**
* Unlinks non-null node x.
*/
//不能传一个null值过，注意，看之前要注意之前的next、prev这些都是谁。
E unlink(Node<E> x) {
// assert x != null;
//拿到节点x的三个属性
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
//这里开始往下就进行移除该元素之后的操作，也就是把指向哪个节点搞定。
if (prev == null) {
//说明移除的节点是头节点，则first头节点应该指向下一个节点
first = next;
} else {
//不是头节点，prev.next=next：有1、2、3，将1.next指向3
prev.next = next;
//然后解除x节点的前指向。
x.prev = null;
}
if (next == null) {
//说明移除的节点是尾节点
last = prev;
} else {
//不是尾节点，有1、2、3，将3.prev指向1. 然后将2.next=解除指向。
next.prev = prev;
x.next = null;
}
//x的前后指向都为null了，也把item为null，让gc回收它
x.item = null;
size--; //移除一个节点，size自减
modCount++;
return element; //由于一开始已经保存了x的值到element，所以返回。
}
【get(index)查询元素的方法】
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
//这里没有什么，重点还是在node(index)中 node(index)方法上面讲过了|
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
//这个很简单，就是通过实体元素来查找到该元素在链表中的位置。跟remove中的代码类似，只是返回 类型不一样。
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
在LinkedList中除了有一个Node的内部类外，应该还能看到另外两个内部类，那就是ListItr，还有一个是DescendingIterator。
【ListItr内部类】
private class ListItr implements ListIterator<E> { }
看一下他的继承结构，发现只继承了一个ListIterator，到ListIterator中一看：
看到方法名之后，就发现不止有向后迭代的方法，还有向前迭代的方法，所以我们就知道了这个ListItr这个内部类干嘛用的了，就是能让linkedList不光能像后迭代，也能向前迭代。
看一下ListItr中的方法，可以发现，在迭代的过程中，还能移除、修改、添加值得操作
【DescendingIterator内部类】
private class DescendingIterator implements Iterator<E> {
//看一下这个类，还是调用的ListItr，作用是封装一下Itr中几个方法，让使用者以正常的思维 去写代码，例如，在从后往前遍历的时候，也是跟从前往后遍历一样，使用next等操作，而不用使用特殊的previous。
private final ListItr itr = new ListItr(size());
public boolean hasNext() {
return itr.hasPrevious();
}
public E next() {
return itr.previous();
}
public void remove() {
itr.remove();
}
}
linkedList本质上是一个双向链表，通过一个Node内部类实现的这种链表结构。
能存储null值
跟arrayList相比较，就真正的知道了，LinkedList在删除和增加等操作上性能好，而ArrayList在查询的性能上好
从源码中看，它不存在容量不足的情况
linkedList不光能够向前迭代，还能像后迭代，并且在迭代的过程中，可以修改值、添加值、还能移除值。
linkedList不光能当链表，还能当队列使用，这个就是因为实现了Deque接口。
原文：https://www.cnblogs.com/shitouzi-shi/p/14386908.html