本文共 42794 字，大约阅读时间需要 142 分钟。
【JDK源码分析系列】LinkedList 源码分析
【0】LinkedList 整体架构
【1】LinkedList 源码MCL视图
LinkedList 的 MCL 视图如下图所示，包括内部类的MCL视图；
【2】LinkedList 源码分析相关知识点总结
/** * superClone 方法，克隆 LinkedList 的父类； * 单独使用 superClone 方法可以实现 LinkedList 的浅拷贝； */ @SuppressWarnings("unchecked") private LinkedList superClone() { try { return (LinkedList ) super.clone(); } catch (CloneNotSupportedException e) { throw new InternalError(e); } } /** * Returns a shallow copy of this {@code LinkedList}. (The elements * themselves are not cloned.) * * @return a shallow copy of this {@code LinkedList} instance */ /** * LinkedList 类实现 Cloneable 接口，Cloneable 接口是一个标志接口； * 实现 clone() 方法； * */ public Object clone() { //克隆 LinkedList 的父类； LinkedList clone = superClone(); // Put clone into "virgin" state clone.first = clone.last = null; clone.size = 0; clone.modCount = 0; // Initialize clone with our elements for (Node x = first; x != null; x = x.next) // add -> linkLast // linkLast 方法中会 new 节点，即可实现深拷贝； clone.add(x.item); return clone; }
【3】LinkedList 源码注解
package java.util;import java.util.function.Consumer;/** * Doubly-linked list implementation of the {@code List} and {@code Deque} * interfaces. Implements all optional list operations, and permits all * elements (including {@code null}). * * 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. * *
Note that this implementation is not synchronized. * If multiple threads access a linked list concurrently, and at least * one of the threads modifies the list structurally, it must be * synchronized externally. (A structural modification is any operation * that adds or deletes one or more elements; merely setting the value of * an element is not a structural modification.) This is typically * accomplished by synchronizing on some object that naturally * encapsulates the list. * * If no such object exists, the list should be "wrapped" using the * {@link Collections#synchronizedList Collections.synchronizedList} * method. This is best done at creation time, to prevent accidental * unsynchronized access to the list:
* List list = Collections.synchronizedList(new LinkedList(...));
* * The iterators returned by this class's {@code iterator} and * {@code listIterator} methods are fail-fast: if the list is * structurally modified at any time after the iterator is created, in * any way except through the Iterator's own {@code remove} or * {@code add} methods, the iterator will throw a {@link * ConcurrentModificationException}. Thus, in the face of concurrent * modification, the iterator fails quickly and cleanly, rather than * risking arbitrary, non-deterministic behavior at an undetermined * time in the future. * *
Note that the fail-fast behavior of an iterator cannot be guaranteed * as it is, generally speaking, impossible to make any hard guarantees in the * presence of unsynchronized concurrent modification. Fail-fast iterators * throw {@code ConcurrentModificationException} on a best-effort basis. * Therefore, it would be wrong to write a program that depended on this * exception for its correctness: the fail-fast behavior of iterators * should be used only to detect bugs. * *
This class is a member of the * * Java Collections Framework. * * @author Josh Bloch * @see List * @see ArrayList * @since 1.2 * @param
the type of elements held in this collection *//** * LinkedList 类继承 AbstractSequentialList 类； * 实现 List，Deque，Cloneable，java.io.Serializable 接口； */public class LinkedList extends AbstractSequentialList implements List , Deque , Cloneable, java.io.Serializable{ /** * size 成员变量； * transient 关键字表明变量不参与序列化； */ transient int size = 0; /** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */ /** * 首节点； */ transient Node first; /** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */ /** * 尾节点； */ transient Node last; /** * Constructs an empty list. */ /** * 构造方法，构造一个空的List； */ public LinkedList() { } /** * 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 */ /** * 使用集合变量构造LinkedList； */ public LinkedList(Collection c) { //构造一个空的List； this(); //将集合C添加到List中； addAll(c); } /** * Links e as first element. */ /** * 该方法在当前 List 的首节点之前添加新的节点； */ // 从头部追加 private void linkFirst(E e) { // 局部 Node 变量指向当前 List 的 first 节点； // 头节点赋值给临时变量 final Node f = first; //新建 Node 变量，该节点首节点为 null， 并指向 f 即当前 List 的首节点； // 新建节点，前一个节点指向 null，e 是新建节点，f 是新建节点的下一个节点，目前值是头节点的值 final Node newNode = new Node<>(null, e, f); //first 向上移动一个节点，即当前 List 的首节点上移一个节点； // 新建节点成为头节点 first = newNode; //f==null， 表明原 List 为空，此时确定原 List 的尾节点位置； // 头节点为空，就是链表为空，头尾节点是一个节点 if (f == null) last = newNode; else //f != null， 原 List 的首节点的前一个节点设置为 newNode，即完成双向链表中的节点的双向互指； //上一个头节点的前一个节点指向当前节点 f.prev = newNode; size++; //fast-fail机制； modCount++; } /** * Links e as last element. */ /** * 该方法在当前 List 的末尾添加新的节点； */ // 从尾部开始追加节点 void linkLast(E e) { // Node 类型变量，指向当前List的尾节点； // 把尾节点数据暂存 final Node l = last; // 新建 Node 类型变量，其前一个节点指向当前List的尾节点，后一个节点指向为null； // 新建新的节点，初始化入参含义： // l 是新节点的前一个节点，当前值是尾节点值 // e 表示当前新增节点，当前新增节点后一个节点是 null final Node newNode = new Node<>(l, e, null); // 当前 List 的尾节点指向 newNode，即当前 List 的尾节点向下移动一位； // 新建节点追加到尾部 last = newNode; // l==null，表明当前 List 为空，则当前 List 的首节点为新增的节点； // 如果链表为空 (l 是尾节点，尾节点为空，链表即空)， 头部和尾部是同一个节点， 都是新建的节点 if (l == null) first = newNode; // 否则把前尾节点的下一个节点， 指向当前尾节点 else // 当前 List 非空，指定当前 List 的尾节点的下一个节点为新增节点； l.next = newNode; // 大小和版本更改 size++; // fast-fail机制； modCount++; } /** * Inserts element e before non-null Node succ. */ /** * 该方法在当前 List 的指定节点之前添加新的节点； */ void linkBefore(E e, Node succ) { // assert succ != null; // Node 类型变量，指向当前 List 中指定节点的前一个节点； final Node pred = succ.prev; //新建 Node 节点，该节点前一个节点为指定节点的前一个节点，后一个节点为指定的节点； final Node newNode = new Node<>(pred, e, succ); //修改指定节点的前一个节点为 newNode； succ.prev = newNode; // pred==null, 表明当前 List 只有一个节点，新增的节点为当前 List 的首节点； if (pred == null) first = newNode; else // 修改指定节点前一个节点的后一个节点为新增节点 newNode； pred.next = newNode; size++; // fast-fail机制； modCount++; } /** * Unlinks non-null first node f. */ /** * 该方法将当前 List 的首节点从 List 中删除； */ // 从头删除节点 f 是链表头节点 private E unlinkFirst(Node f) { // assert f == first && f != null; // 获取当前 List 的首节点中的元素； // 拿出头节点的值，作为方法的返回值 final E element = f.item; //新建节点指向当前 List 首节点的下一个节点； // 拿出头节点的下一个节点 final Node next = f.next; //清空当前 List 的首节点 //帮助 GC 回收头节点 f.item = null; f.next = null; // help GC //原 List 的首节点后移一个节点； // 头节点的下一个节点成为头节点 first = next; //next==null，表明原 List 仅有一个节点，last=null表明将当前 List 清空； //如果 next 为空，表明链表为空 if (next == null) last = null; //链表不为空，头节点的前一个节点指向 null else //清除 next 节点的前项节点，即将next节点设置为当前 List 的首节点； next.prev = null; //修改链表大小和版本 size--; //fast-fail机制； modCount++; return element; } /** * Unlinks non-null last node l. */ /** * 该方法将当前 List 的尾节点从 List 中删除； */ private E unlinkLast(Node l) { // assert l == last && l != null; //获取当前 List 的尾节点的元素； final E element = l.item; //新建节点指向当前 List 的尾节点的前项节点； final Node prev = l.prev; //清空当前 List 的尾节点； l.item = null; l.prev = null; // help GC //原 List 的尾节点前移； last = prev; //prev==null,表明原 List 仅有一个节点， first=null 表明将当前 List 清空； if (prev == null) first = null; else //清除 prev 节点的后项节点，即将 prev 节点设置为当前 List 的尾节点； prev.next = null; size--; //fast-fail机制； modCount++; return element; } /** * Unlinks non-null node x. */ /** * 该方法将当前 List 的指定节点从 List 中删除； */ E unlink(Node x) { // assert x != null; //获取指定节点 x 的元素； final E element = x.item; //新建节点指向指定节点的前项与后项节点； final Node next = x.next; final Node prev = x.prev; //prev==null 表明指定节点 x 为原 List 的首节点； if (prev == null) { //原 List 的首节点后移； first = next; } else { //删除指定的节点 x; prev.next = next; x.prev = null; } //next==null表明指定节点 x 为原 List 的尾节点； if (next == null) { //原 List 的尾节点前移； last = prev; } else { //删除指定的节点 x； next.prev = prev; x.next = null; } //清空指定节点 x 的元素； x.item = null; size--; // fast-fail机制； modCount++; return element; } /** * Returns the first element in this list. * * @return the first element in this list * @throws NoSuchElementException if this list is empty */ /** * 该方法用于获取当前 List 首节点的元素 */ public E getFirst() { final Node f = first; if (f == null) throw new NoSuchElementException(); return f.item; } /** * Returns the last element in this list. * * @return the last element in this list * @throws NoSuchElementException if this list is empty */ /** * 该方法用于获取当前 List 的尾节点的元素； */ public E getLast() { final Node l = last; if (l == null) throw new NoSuchElementException(); return l.item; } /** * Removes and returns the first element from this list. * * @return the first element from this list * @throws NoSuchElementException if this list is empty */ /** * 该方法用于删除当前 List 的首节点； */ public E removeFirst() { final Node f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } /** * Removes and returns the last element from this list. * * @return the last element from this list * @throws NoSuchElementException if this list is empty */ /** * 该方法用于删除当前 List 的尾节点； */ public E removeLast() { final Node l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); } /** * Inserts the specified element at the beginning of this list. * * @param e the element to add */ /** * 该方法用于向当前 List 的首节点之前添加节点； */ public void addFirst(E e) { linkFirst(e); } /** * Appends the specified element to the end of this list. * * This method is equivalent to {@link #add}. * * @param e the element to add */ /** * 该方法用于向当前 List 的尾节点之后添加节点； */ public void addLast(E e) { linkLast(e); } /** * Returns {@code true} if this list contains the specified element. * More formally, returns {@code true} if and only if this list contains * at least one element {@code e} such that * (o==null ? e==null : o.equals(e)). * * @param o element whose presence in this list is to be tested * @return {@code true} if this list contains the specified element */ /** * 该方法用于判断 Object 是否存在于当前的 List 中； */ public boolean contains(Object o) { return indexOf(o) != -1; } /** * Returns the number of elements in this list. * * @return the number of elements in this list */ /** * 该方法用于返回当前 LinkedList 的大小 */ public int size() { //size 为 LinkedList 类的成员变量； return size; } /** * Appends the specified element to the end of this list. * *
This method is equivalent to {@link #addLast}. * * @param e element to be appended to this list * @return {@code true} (as specified by {@link Collection#add}) */ /** * 该方法用于在当前 List 的末尾添加节点； */ public boolean add(E e) { linkLast(e); return true; } /** * 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 * (o==null ? get(i)==null : o.equals(get(i))) * (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 */ /** * 该方法遍历当前 List， 删除当前 List 中第一个包含元素 o 的节点； */ public boolean remove(Object o) { if (o == null) { for (Node
x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } /** * Appends all of the elements in the specified collection to the end of * this list, in the order that they are returned by the specified * collection's iterator. The behavior of this operation is undefined if * the specified collection is modified while the operation is in * progress. (Note that this will occur if the specified collection is * this list, and it's nonempty.) * * @param c collection containing elements to be added to this list * @return {@code true} if this list changed as a result of the call * @throws NullPointerException if the specified collection is null */ /** * 将集合 c 添加到当前 List 的 size 索引之后，即在当前 List 的末尾添加集合 c 中的元素； */ public boolean addAll(Collection c) { return addAll(size, c); } /** * Inserts all of the elements in the specified collection into this * list, starting at the specified position. Shifts the element * currently at that position (if any) and any subsequent elements to * the right (increases their indices). The new elements will appear * in the list in the order that they are returned by the * specified collection's iterator. * * @param index index at which to insert the first element * from the specified collection * @param c collection containing elements to be added to this list * @return {@code true} if this list changed as a result of the call * @throws IndexOutOfBoundsException {@inheritDoc} * @throws NullPointerException if the specified collection is null */ /** * 该方法在当前 List 的指定的索引处添加集合元素； */ public boolean addAll(int index, Collection c) { checkPositionIndex(index); //集合c转化为数组； Object[] a = c.toArray(); int numNew = a.length; //新增集合中没有元素，则返回 false，无须修改； if (numNew == 0) return false; //声明 Node 类型的变量，pred 为当前节点的前项节点，succ 为当前节点； Node pred, succ; if (index == size) { succ = null; pred = last; } else { succ = node(index); pred = succ.prev; } //循环遍历数组 a 中的元素，构建链表 for (Object o : a) { //获取Object数组a中的元素 @SuppressWarnings("unchecked") E e = (E) o; //新建 Node 实例 Node newNode = new Node<>(pred, e, null); if (pred == null) first = newNode; else pred.next = newNode; pred = newNode; } //调整原始链表的节点位置 if (succ == null) { //若当前节点 succ 为null，则将 last 指向新增序列的最后一个节点，相当于在原始序列末尾添加新增序列； last = pred; } else { //若当前节点不为null，则将新增元素序列添加到 succ 指向的节点之前； pred.next = succ; succ.prev = pred; } //调整原始List长度； size += numNew; //验证fast-fail机制； modCount++; return true; } /** * Removes all of the elements from this list. * The list will be empty after this call returns. */ /** * 该方法用于清除当前 List； */ public void clear() { // Clearing all of the links between nodes is "unnecessary", but: // - helps a generational GC if the discarded nodes inhabit // more than one generation // - is sure to free memory even if there is a reachable Iterator for (Node x = first; x != null; ) { Node next = x.next; x.item = null; x.next = null; x.prev = null; x = next; } first = last = null; size = 0; //fast-fail机制； modCount++; } // Positional Access Operations /** * 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} */ /** * 该方法用于获取当前 List 中的元素； */ public E get(int index) { //检查索引的有效性； checkElementIndex(index); //返回索引处节点的元素； return node(index).item; } /** * Replaces the element at the specified position in this list with the * specified element. * * @param index index of the element to replace * @param element element to be stored at the specified position * @return the element previously at the specified position * @throws IndexOutOfBoundsException {@inheritDoc} */ /** * 该方法用于设置当前 List 索引 index 处的值为 element； */ public E set(int index, E element) { checkElementIndex(index); //Node x 指向当前 List 中索引 index 处的节点； Node x = node(index); //修改索引 index 处的节点的元素； E oldVal = x.item; x.item = element; return oldVal; } /** * Inserts the specified element at the specified position in this list. * Shifts the element currently at that position (if any) and any * subsequent elements to the right (adds one to their indices). * * @param index index at which the specified element is to be inserted * @param element element to be inserted * @throws IndexOutOfBoundsException {@inheritDoc} */ /** * 该方法用于将元素 element 添加到当前 List 的 index 索引处； */ public void add(int index, E element) { //检查索引的有效性； checkPositionIndex(index); //若索引 index 为当前 List 的末尾索引，则将元素添加到原 List 的末尾； if (index == size) linkLast(element); else //否则,在当前 List index 索引处的节点之前添加元素； linkBefore(element, node(index)); } /** * Removes the element at the specified position in this list. Shifts any * subsequent elements to the left (subtracts one from their indices). * Returns the element that was removed from the list. * * @param index the index of the element to be removed * @return the element previously at the specified position * @throws IndexOutOfBoundsException {@inheritDoc} */ /** * 该方法用于从当前 List 中删除索引 index 处的节点； */ public E remove(int index) { //检查节点的有效性； checkElementIndex(index); //从当前 List 中删除索引 index 处的节点； return unlink(node(index)); } /** * Tells if the argument is the index of an existing element. */ /** * 该方法用于判断索引 index 是否为元素索引； * 元素索引范围为 0 -- size - 1； */ private boolean isElementIndex(int index) { return index >= 0 && index < size; } /** * Tells if the argument is the index of a valid position for an * iterator or an add operation. */ /** * 判断索引是否为位置索引； * 位置索引的范围为 0--size； */ private boolean isPositionIndex(int index) { return index >= 0 && index <= size; } /** * Constructs an IndexOutOfBoundsException detail message. * Of the many possible refactorings of the error handling code, * this "outlining" performs best with both server and client VMs. */ /** * 构造异常信息； */ private String outOfBoundsMsg(int index) { return "Index: "+index+", Size: "+size; } /** * 检查元素索引的正确性并抛出异常； */ private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } /** * checkPositionIndex：索引不在List的范围内则抛出 IndexOutOfBoundsException 异常； */ /** * 检查位置索引的正确性并抛出异常； */ private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } /** * Returns the (non-null) Node at the specified element index. */ /** * 返回当前 List 索引 index 处的节点； */ // 根据链表索引位置查询节点 // // 注意 : // 从源码中我们可以发现， LinkedList 并没有采用从头循环到尾的做法， 而是采取了简单二分法， // 首先看看 index 是在链表的前半部分，还是后半部分。如果是前半部分，就从头开始寻找，反之亦然 Node node(int index) { // assert isElementIndex(index); //对半查找，减少遍历次数； // 如果 index 处于队列的前半部分，从头开始找，size >> 1 是 size 除以 2 的意思 if (index < (size >> 1)) { Node x = first; // 直到 for 循环到 index 的前一个 node 停止 for (int i = 0; i < index; i++) x = x.next; return x; } else {// 如果 index 处于队列的后半部分，从尾开始找 Node x = last; // 直到 for 循环到 index 的后一个 node 停止 for (int i = size - 1; i > index; i--) x = x.prev; return x; } } // Search Operations /** * Returns the index of the first occurrence of the specified element * in this list, or -1 if this list does not contain the element. * More formally, returns the lowest index {@code i} such that * (o==null ? get(i)==null : o.equals(get(i))), * or -1 if there is no such index. * * @param o element to search for * @return the index of the first occurrence of the specified element in * this list, or -1 if this list does not contain the element */ /** * 该方法遍历当前 List 以确定 Object 元素的索引； */ public int indexOf(Object o) { int index = 0; //当 o==null时, 返回当前 List 中第一个元素为 null 的节点的索引； if (o == null) { for (Node x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; } /** * Returns the index of the last occurrence of the specified element * in this list, or -1 if this list does not contain the element. * More formally, returns the highest index {@code i} such that * (o==null ? get(i)==null : o.equals(get(i))), * or -1 if there is no such index. * * @param o element to search for * @return the index of the last occurrence of the specified element in * this list, or -1 if this list does not contain the element */ /** * 反向遍历当前 List 查找 Object o 在当前 List 中的逆向索引； */ public int lastIndexOf(Object o) { int index = size; if (o == null) { for (Node x = last; x != null; x = x.prev) { index--; if (x.item == null) return index; } } else { for (Node x = last; x != null; x = x.prev) { index--; if (o.equals(x.item)) return index; } } return -1; } // Queue operations. /** * Retrieves, but does not remove, the head (first element) of this list. * * @return the head of this list, or {@code null} if this list is empty * @since 1.5 */ /** * 确定当前 List 的首节点元素； */ public E peek() { final Node f = first; return (f == null) ? null : f.item; } /** * Retrieves, but does not remove, the head (first element) of this list. * * @return the head of this list * @throws NoSuchElementException if this list is empty * @since 1.5 */ /** * 获取当前 List 的首节点元素； */ public E element() { return getFirst(); } /** * Retrieves and removes the head (first element) of this list. * * @return the head of this list, or {@code null} if this list is empty * @since 1.5 */ /** * 从当前 List 中删除首节点，并返回删除的首节点的元素； */ public E poll() { final Node f = first; return (f == null) ? null : unlinkFirst(f); } /** * Retrieves and removes the head (first element) of this list. * * @return the head of this list * @throws NoSuchElementException if this list is empty * @since 1.5 */ /** * 从当前 List 中删除首节点，并返回删除的首节点的元素； */ public E remove() { return removeFirst(); } /** * Adds the specified element as the tail (last element) of this list. * * @param e the element to add * @return {@code true} (as specified by {@link Queue#offer}) * @since 1.5 */ /** * 将特定的元素作为当前 List 的尾节点加入当前 List； */ public boolean offer(E e) { return add(e); } // Deque operations /** * Inserts the specified element at the front of this list. * * @param e the element to insert * @return {@code true} (as specified by {@link Deque#offerFirst}) * @since 1.6 */ /** * 将特定的元素添加到当前 List 的起始处； * 相当于从首段入队； */ public boolean offerFirst(E e) { addFirst(e); return true; } /** * Inserts the specified element at the end of this list. * * @param e the element to insert * @return {@code true} (as specified by {@link Deque#offerLast}) * @since 1.6 */ /** * 将特定的元素添加到当前 List 的末尾； * 相当于从尾端入队； */ public boolean offerLast(E e) { addLast(e); return true; } /** * Retrieves, but does not remove, the first element of this list, * or returns {@code null} if this list is empty. * * @return the first element of this list, or {@code null} * if this list is empty * @since 1.6 */ /** * 获取当前 List 的首节点元素； */ public E peekFirst() { final Node f = first; return (f == null) ? null : f.item; } /** * Retrieves, but does not remove, the last element of this list, * or returns {@code null} if this list is empty. * * @return the last element of this list, or {@code null} * if this list is empty * @since 1.6 */ /** * 获取当前 List 的尾节点的元素； */ public E peekLast() { final Node l = last; return (l == null) ? null : l.item; } /** * Retrieves and removes the first element of this list, * or returns {@code null} if this list is empty. * * @return the first element of this list, or {@code null} if * this list is empty * @since 1.6 */ /** * 获取当前 List 的首节点元素，并将首节点从当前 List 中删除； * 相当于首端出队； */ public E pollFirst() { final Node f = first; return (f == null) ? null : unlinkFirst(f); } /** * Retrieves and removes the last element of this list, * or returns {@code null} if this list is empty. * * @return the last element of this list, or {@code null} if * this list is empty * @since 1.6 */ /** * 获取当前 List 的尾节点元素，并将尾节点从当前 List 中删除； * 相当于尾端出队； */ public E pollLast() { final Node l = last; return (l == null) ? null : unlinkLast(l); } /** * Pushes an element onto the stack represented by this list. In other * words, inserts the element at the front of this list. * * This method is equivalent to {@link #addFirst}. * * @param e the element to push * @since 1.6 */ /** * 在当前 List 的首端添加元素； * 相当于入栈； */ public void push(E e) { addFirst(e); } /** * Pops an element from the stack represented by this list. In other * words, removes and returns the first element of this list. * *
This method is equivalent to {@link #removeFirst()}. * * @return the element at the front of this list (which is the top * of the stack represented by this list) * @throws NoSuchElementException if this list is empty * @since 1.6 */ /** * 移除当前 List 的首端元素； * 相当于出栈； */ public E pop() { return removeFirst(); } /** * Removes the first occurrence of the specified element in this * list (when traversing the list from head to tail). If the list * does not contain the element, it is unchanged. * * @param o element to be removed from this list, if present * @return {@code true} if the list contained the specified element * @since 1.6 */ /** * 删除当前 List 中首先包含元素 Object o 的节点； */ public boolean removeFirstOccurrence(Object o) { return remove(o); } /** * Removes the last occurrence of the specified element in this * list (when traversing the list from head to tail). If the list * does not contain the element, it is unchanged. * * @param o element to be removed from this list, if present * @return {@code true} if the list contained the specified element * @since 1.6 */ /** * 删除当前 List 中最后包含元素 Object o 的节点； */ public boolean removeLastOccurrence(Object o) { if (o == null) { for (Node
x = last; x != null; x = x.prev) { if (x.item == null) { unlink(x); return true; } } } else { for (Node x = last; x != null; x = x.prev) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } /** * Returns a list-iterator of the elements in this list (in proper * sequence), starting at the specified position in the list. * Obeys the general contract of {@code List.listIterator(int)}. * * The list-iterator is fail-fast: if the list is structurally * modified at any time after the Iterator is created, in any way except * through the list-iterator's own {@code remove} or {@code add} * methods, the list-iterator will throw a * {@code ConcurrentModificationException}. Thus, in the face of * concurrent modification, the iterator fails quickly and cleanly, rather * than risking arbitrary, non-deterministic behavior at an undetermined * time in the future. * * @param index index of the first element to be returned from the * list-iterator (by a call to {@code next}) * @return a ListIterator of the elements in this list (in proper * sequence), starting at the specified position in the list * @throws IndexOutOfBoundsException {@inheritDoc} * @see List#listIterator(int) */ /** * 新建一个当前 List 的迭代器； */ public ListIterator
listIterator(int index) { //检查位置索引的正确性； checkPositionIndex(index); //返回 ListItr 实例； return new ListItr(index); } /** * ListItr 内部类，实现 ListIterator 接口； */ // 双向迭代器 // // 迭代顺序 方法 // 从尾到头迭代方法 hasPrevious、previous、previousIndex // 从头到尾迭代方法 hasNext、next、nextIndex private class ListItr implements ListIterator { //lastReturned：最近返回的节点，表示当前 List 中最近一次被修改的节点； //上一次执行 next() 或者 previos() 方法时的节点位置 private Node lastReturned = null; //next：指向下一个节点； private Node next; //下一个节点的位置 private int nextIndex; //判断 fast-fail 机制； //expectedModCount：期望版本号；modCount：目前最新版本号 private int expectedModCount = modCount; //构造方法； ListItr(int index) { // assert isPositionIndex(index); next = (index == size) ? null : node(index); nextIndex = index; } //判断当前 List 是否存在剩余的元素； public boolean hasNext() { return nextIndex < size; } //获取当前 List 中当前节点的下一个节点； public E next() { //检查 fast-fail 机制； //检查期望版本号有无发生变化 checkForComodification(); //再次检查 if (!hasNext()) throw new NoSuchElementException(); // next 是当前节点， 在上一次执行 next() 方法时被赋值的 // 第一次执行时是在初始化迭代器的时候， next 被赋值的 lastReturned = next; //next 节点后移； // next 是下一个节点了，为下次迭代做准备 next = next.next; nextIndex++; //返回当前节点的元素； return lastReturned.item; } //判断当前 List 是否存在前项的元素； // 如果上次节点索引位置大于 0，就还有节点可以迭代 public boolean hasPrevious() { return nextIndex > 0; } //获取当前 List 中当前节点的前一个节点； public E previous() { checkForComodification(); if (!hasPrevious()) throw new NoSuchElementException(); // next 为空场景 : 1. 说明是第一次迭代， 取尾节点(last); 2. 上一次操作把尾节点删除掉了 // next 不为空场景 : 说明已经发生过迭代了， 直接取前一个节点即可(next.prev) lastReturned = next = (next == null) ? last : next.prev; // 索引位置变化 nextIndex--; return lastReturned.item; } //返回类成员变量 nextIndex public int nextIndex() { return nextIndex; } public int previousIndex() { return nextIndex - 1; } //从当前 List 中移除最近一次被修改的节点； public void remove() { //检查 fast-fail 机制； checkForComodification(); // lastReturned 是本次迭代需要删除的值， 分以下空和非空两种情况 : // lastReturned 为空， 说明调用者没有主动执行过 next() 或者 previos() 直接报错 // lastReturned 不为空， 是在上次执行 next() 或者 previos() 方法时赋的值 if (lastReturned == null) throw new IllegalStateException(); Node lastNext = lastReturned.next; //删除当前 List 中最近一次被修改的节点； unlink(lastReturned); // next == lastReturned 的场景分析 : // 从尾到头递归顺序， 并且是第一次迭代， 并且要删除最后一个元素的情况下 // 这种情况下， previous() 方法里面设置了 lastReturned = next = last, // 所以 next 和 lastReturned 会相等 if (next == lastReturned) // 这时候 lastReturned 是尾节点， lastNext 是 null， 所以 next 也是 null， // 这样在 previous() 执行时， 发现 next 是 null， 就会把尾节点赋值给 next next = lastNext; else nextIndex--; lastReturned = null; //改变了当前 List，修改 expectedModCount expectedModCount++; } //设置当前 List 中最近一次被修改的节点的元素值； public void set(E e) { if (lastReturned == null) throw new IllegalStateException(); checkForComodification(); lastReturned.item = e; } //向当前 List 添加节点； public void add(E e) { checkForComodification(); lastReturned = null; if (next == null) linkLast(e); else linkBefore(e, next); nextIndex++; expectedModCount++; } //遍历当前 List 中剩余的元素； public void forEachRemaining(Consumer action) { Objects.requireNonNull(action); while (modCount == expectedModCount && nextIndex < size) { action.accept(next.item); lastReturned = next; next = next.next; nextIndex++; } checkForComodification(); } //检查 fast-fail机制； final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } } /** * 内部类，定义 Node 结构； */ private static class Node { // 节点值 E item; // 指向的下一个节点 Node next; // 指向的前一个节点 Node prev; // 构造方法 // 初始化参数顺序分别是：前一个节点、本身节点值、后一个节点 Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } } /** * @since 1.6 */ /** * 获取反向迭代器实例； */ public Iterator descendingIterator() { return new DescendingIterator(); } /** * Adapter to provide descending iterators via ListItr.previous */ /** * 内部类定义反向迭代器，实现 Iterator 接口； */ private class DescendingIterator implements Iterator { private final ListItr itr = new ListItr(size()); public boolean hasNext() { return itr.hasPrevious(); } public E next() { return itr.previous(); } public void remove() { itr.remove(); } } /** * superClone 方法，克隆 LinkedList 的父类； * 单独使用 superClone 方法可以实现 LinkedList 的浅拷贝； */ @SuppressWarnings("unchecked") private LinkedList superClone() { try { return (LinkedList ) super.clone(); } catch (CloneNotSupportedException e) { throw new InternalError(e); } } /** * Returns a shallow copy of this {@code LinkedList}. (The elements * themselves are not cloned.) * * @return a shallow copy of this {@code LinkedList} instance */ /** * LinkedList 类实现 Cloneable 接口，Cloneable 接口是一个标志接口； * 实现 clone() 方法； * */ public Object clone() { //克隆 LinkedList 的父类； LinkedList clone = superClone(); // Put clone into "virgin" state clone.first = clone.last = null; clone.size = 0; clone.modCount = 0; // Initialize clone with our elements for (Node x = first; x != null; x = x.next) // add -> linkLast // linkLast 方法中会 new 节点，即可实现深拷贝； clone.add(x.item); return clone; } /** * Returns an array containing all of the elements in this list * in proper sequence (from first to last element). * * The returned array will be "safe" in that no references to it are * maintained by this list. (In other words, this method must allocate * a new array). The caller is thus free to modify the returned array. * *
This method acts as bridge between array-based and collection-based * APIs. * * @return an array containing all of the elements in this list * in proper sequence */ /** * 将 LinkedList 转化为数组，遍历 LinkedList 将其中的节点的元素取出放入数组中并返回新建的数组； */ public Object[] toArray() { Object[] result = new Object[size]; int i = 0; for (Node
x = first; x != null; x = x.next) result[i++] = x.item; return result; } /** * Returns an array containing all of the elements in this list in * proper sequence (from first to last element); the runtime type of * the returned array is that of the specified array. If the list fits * in the specified array, it is returned therein. Otherwise, a new * array is allocated with the runtime type of the specified array and * the size of this list. * * If the list fits in the specified array with room to spare (i.e., * the array has more elements than the list), the element in the array * immediately following the end of the list is set to {@code null}. * (This is useful in determining the length of the list only if * the caller knows that the list does not contain any null elements.) * *
Like the {@link #toArray()} method, this method acts as bridge between * array-based and collection-based APIs. Further, this method allows * precise control over the runtime type of the output array, and may, * under certain circumstances, be used to save allocation costs. * *
Suppose {@code x} is a list known to contain only strings. * The following code can be used to dump the list into a newly * allocated array of {@code String}: * *
* String[] y = x.toArray(new String[0]);
* * Note that {@code toArray(new Object[0])} is identical in function to * {@code toArray()}. * * @param a the array into which the elements of the list are to * be stored, if it is big enough; otherwise, a new array of the * same runtime type is allocated for this purpose. * @return an array containing the elements of the list * @throws ArrayStoreException if the runtime type of the specified array * is not a supertype of the runtime type of every element in * this list * @throws NullPointerException if the specified array is null */ /** * 使用泛型，将 LinkedList 转化为特定类型的数组； * */ @SuppressWarnings("unchecked") public T[] toArray(T[] a) { if (a.length < size) // a.length < size 则将数组 a 扩容为 size 大小的数组； a = (T[])java.lang.reflect.Array.newInstance( a.getClass().getComponentType(), size); int i = 0; //新建 Object 类型数组，指向数组 a，此时 result 与 a 共用一段空间； Object[] result = a; for (Node x = first; x != null; x = x.next) //向 result 中添加元素等价于向数组 a 中添加元素； result[i++] = x.item; // a.length > size 则将数组 a 截断为 size 大小的数组； if (a.length > size) a[size] = null; return a; } private static final long serialVersionUID = 876323262645176354L; /** * Saves the state of this {@code LinkedList} instance to a stream * (that is, serializes it). * * @serialData The size of the list (the number of elements it * contains) is emitted (int), followed by all of its * elements (each an Object) in the proper order. */ /** * LinkedList 序列化操作，对于 LinkedList 元素为 null 的节点不做序列化； */ private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { // Write out any hidden serialization magic s.defaultWriteObject(); // Write out size s.writeInt(size); // Write out all elements in the proper order. for (Node x = first; x != null; x = x.next) s.writeObject(x.item); } /** * Reconstitutes this {@code LinkedList} instance from a stream * (that is, deserializes it). */ /** * LinkedList 反序列化操作； */ @SuppressWarnings("unchecked") private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { // Read in any hidden serialization magic s.defaultReadObject(); // Read in size int size = s.readInt(); // Read in all elements in the proper order. for (int i = 0; i < size; i++) linkLast((E)s.readObject()); } /** * Creates a late-binding * and fail-fast {@link Spliterator} over the elements in this * list. * * The {@code Spliterator} reports {@link Spliterator#SIZED} and * {@link Spliterator#ORDERED}. Overriding implementations should document * the reporting of additional characteristic values. * * @implNote * The {@code Spliterator} additionally reports {@link Spliterator#SUBSIZED} * and implements {@code trySplit} to permit limited parallelism.. * * @return a {@code Spliterator} over the elements in this list * @since 1.8 */ @Override public Spliterator
spliterator() { return new LLSpliterator (this, -1, 0); } /** * 内部类，定义了一个并行迭代器； */ /** A customized variant of Spliterators.IteratorSpliterator */ static final class LLSpliterator implements Spliterator { static final int BATCH_UNIT = 1 << 10; // batch array size increment static final int MAX_BATCH = 1 << 25; // max batch array size; final LinkedList list; // null OK unless traversed Node current; // current node; null until initialized int est; // size estimate; -1 until first needed int expectedModCount; // initialized when est set int batch; // batch size for splits LLSpliterator(LinkedList list, int est, int expectedModCount) { this.list = list; this.est = est; this.expectedModCount = expectedModCount; } //用于获取当前 LinkedList 的大小； final int getEst() { int s; // force initialization // lst 用于指向 list 成员变量，即指向 LinkedList 本身； final LinkedList lst; if ((s = est) < 0) { if ((lst = list) == null) s = est = 0; else { expectedModCount = lst.modCount; current = lst.first; s = est = lst.size; } } return s; } //估计 LinkedList 的大小； public long estimateSize() { return (long) getEst(); } /** * 尝试拆分 LinkedList； * 多次调用 trySplit 方法，LinkedList 将被拆分成许多段的切片； * 切片大小按照 BATCH_UNIT 2*BATCH_UNIT ... 增长； */ public Spliterator trySplit() { //Node 类型变量用于指向 LinkedList 首节点； Node p; int s = getEst(); if (s > 1 && (p = current) != null) { /** * n 为每一段切片的最后一个索引，在 LinkedList 中的索引； * 若第一个切片没有包含当前 LinkedList 中的所有元素， * 则下一次 trySplit 取 BATCH_UNIT * 调用次数 大小的切片， * 继续存放 LinkedList 中剩余的元素； */ int n = batch + BATCH_UNIT; if (n > s) n = s; if (n > MAX_BATCH) n = MAX_BATCH; //新建 n 大小的 Object 数组； Object[] a = new Object[n]; int j = 0; //将 LinkedList 中 n 个节点的元素取出； do { a[j++] = p.item; } while ((p = p.next) != null && j < n); current = p; batch = j; est = s - j; /** * 使用数组 a 中 0-j 的切片创建一个 ArraySpliterator * ArraySpliterator 为 Spliterators的内部类，实现了 Spliterator 接口 */ return Spliterators.spliterator(a, 0, j, Spliterator.ORDERED); } return null; } /** * 此处遍历 LinkedList 中剩余的元素，并对元素执行 action 定义的操作 */ public void forEachRemaining(Consumer action) { Node p; int n; if (action == null) throw new NullPointerException(); if ((n = getEst()) > 0 && (p = current) != null) { current = null; est = 0; do { E e = p.item; p = p.next; action.accept(e); } while (p != null && --n > 0); //while (p != null && --n > 0)：防止 LinkedList 存在元素为 null 的节点； } //fast-fail机制； if (list.modCount != expectedModCount) throw new ConcurrentModificationException(); } /** * 在 LinkedList 后移一个节点，对节点中的元素指定 action 定义的操作； */ public boolean tryAdvance(Consumer action) { Node p; if (action == null) throw new NullPointerException(); if (getEst() > 0 && (p = current) != null) { --est; E e = p.item; current = p.next; /** * 此处元素执行 action 定义的操作 */ action.accept(e); if (list.modCount != expectedModCount) throw new ConcurrentModificationException(); return true; } return false; } public int characteristics() { return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED; } }} 致谢
本博客为博主的学习实践总结，并参考了众多博主的博文，在此表示感谢，博主若有不足之处，请批评指正。
发表评论
最新留言
关于作者
