JDK1.8源码阅读记录
JAVA.Util包
LinkedList类
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
LinkedList，是链式列表，底层基于双向链表实现，可以在首尾、或指定索引处操作元素，元素可以重复，可当作栈、队列、双端队列使用。不是线程安全的。可克隆，序列化。
LinkedList适用于频繁在中间位置插入、删除元素的场合。但随机访问速度较慢，需要从头开始逐个找。LinkedList虽然有涉及到索引值，但其索引值的实现是通过遍历取得，并不等于普通数组自带的索引值。
与ArrayList相比，ArrayList基于动态数组，以数组的形式存储，内存是连续的，随机访问速度快，由于每次插入和删除都需要移动数组中的元素，因此不适合于在线性表中间需要频繁进行插入和删除操作。
属性
transient int size = 0;//LinkedList长度
transient Node<E> first;//LinkedList首节点
transient Node<E> last;//LinkedList尾节点
transient表示该类实例在序列化的时候不会考虑这些属性。
在这里，要提示下本类的内部类，表示节点，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;
}
}
声明为私有的，明确只有在本外部类才可以使用。
- item，表示该节点的值或内容
- next，表示该节点的后一个节点
- prev，表示该节点的前一个节点
构造方法
//实例一个空链表
public LinkedList() {
}
//将集合c里的元素作为节点，实例链表
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
//由于构造函数在使用的时候，size=0，因此这里的index也为0
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
Object[] a = c.toArray();//以c为源，创建新数组a
int numNew = a.length;//新数组a的长度
if (numNew == 0)//空数组，返回false，表示无添加
return false;
Node<E> pred, succ;//定义某个节点的前后节点
if (index == size) {//相当于在链表尾部添加，若链表为空，也相当于在头部添加
succ = null;//尾部添加，暂不用考虑某节点的后一个节点
pred = last;//尾部添加，以原链表的最后一个节点作为要添加节点的前个节点
} else {//非尾部添加
succ = node(index);//获取指定索引处的节点，作为要添加节点的后个节点
pred = succ.prev;//指定索引处的节点的前个节点，作为要添加节点的前个节点
}
for (Object o : a) {//真正的添加操作
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);//由对象e（o）创建新节点，顺便链接前节点
if (pred == null)//相当于头部添加
first = newNode;//新节点作为头节点
else
pred.next = newNode;//通过pred的next链接本新节点
pred = newNode;//单个节点添加完毕，顺便把pred赋值为本新节点
}
if (succ == null) {//表示此前的添加为尾部添加
last = pred;//指定本链表的尾部节点为最后一个加入本链表的新节点
} else {//非尾部添加
pred.next = succ;//由最后一个加入本链表的新节点链接原链表的后部分节点
succ.prev = pred;//由原链表的后部分节点链接最后一个加入本链表的新节点
}
size += numNew;//长度加上这次添加的节点数
modCount++;//修改次数增1
return true;//返回true，表示由添加新节点
}
常用方法
在LinkedList中，有多种节点的增删改操作，但在链表中的增、删、改操作与addAll（）方法中执行的真正增加操作思路类似，每次执行完毕后，都要modCount增1。
getLast()返回此列表中的最后一个元素（非节点），链表为空会抛出异常getFirst()返回此列表中的第一个元素（非节点），链表为空会抛出异常removeFirst()删除链表的头节点，并返回该节点的元素，链表为空会抛出异常removeLast()删除链表的尾节点，并返回该节点的元素，链表为空会抛出异常addFirst(E e)将指定的元素插入此列表的开头。无返回值。addLast(E e)将指定的元素追加到此列表的末尾。无返回值。contains(Object o)如果此列表包含指定的元素，则返回true。size()返回链表的大小（int值）add(E e)将指定的元素追加到此列表的末尾，增加成功返回trueremove(Object o)从此列表中删除第一次出现的指定元素，如果存在，则将其删除。如果此列表不包含元素，则不变。删除成功返回true。clear()从该列表中删除所有元素。 此调用返回后，列表将为空。无返回值。get(int index)返回此列表中指定位置的元素。set(int index, E element)用指定的元素替换此列表中指定位置的元素。返回旧值。add(int index, E element)将指定的元素插入此列表中的指定位置。 将当前在该位置的元素（如果有的话）和任何后继元素向右移动（在其索引处增加一个）。无返回值。remove(int index)删除指定索引值处的元素，并返回该元素。
查找操作方法
indexOf(Object o)返回指定元素在此列表中首次出现的索引，如果此列表不包含该元素，则返回-1。- lastIndexOf(Object o)返回指定元素在此列表中最后一次出现的索引；如果此列表不包含该元素，则返回-1。
队列操作方法
peek()检索但不删除此列表的头（第一个元素）。返回该元素，若链表为空，则返回null。element()检索但不删除此列表的头（第一个元素）。返回该元素，若链表为空，则抛出异常。poll()检索并删除此列表的头（第一个元素）。返回该元素，若链表为空，则返回null。remove()检索并删除此列表的头（第一个元素）。返回该元素，若链表为空，则抛出异常。offer(E e)将指定的元素添加为此列表的尾部（最后一个元素）。增加成功返回true。相当于add(e)。offerFirst(E e)将指定的元素插入此列表的前面。增加成功返回true。相当于addFirst(e)。offerLast(E e)将指定的元素插入此列表的后面。增加成功返回true。相当于addLast(e)。peekFirst()检索但不删除此列表的第一个元素，返回该元素，如果此列表为空，则返回 null。peekLast()检索但不删除此列表的最后一个元素，返回该元素，如果此列表为空，则返回null。pollFirst()检索并删除此列表的第一个元素，返回该元素，如果此列表为空，则返回null。pollLast()检索并删除此列表的最后一个元素，返回该元素，如果此列表为空，则*或返回{null。push(E e)将元素压入此列表表示的堆栈。换句话说，将元素插入此列表的前面。无返回值。pop()从此列表表示的堆栈中弹出一个元素。换句话说，删除并返回此列表的第一个元素。removeFirstOccurrence(Object o)删除首次出现在此列表中的指定元素（从头到尾遍历列表时）。如果列表不包含该元素，则它保持不变。删除成功返回true。removeLastOccurrence(Object o)删除此列表中最后一次出现的指定元素（从头到尾遍历列表时）。如果列表不包含该元素，则它保持不变。删除成功返回true。
迭代器方法
listIterator(int index)返回列表中元素的列表迭代器（以适当的顺序），从列表中的指定位置开始。descendingIterator()返回列表中元素的迭代器，操作顺序跟列表迭代器相反。
转载：https://blog.csdn.net/weixin_43459704/article/details/104577385
查看评论