LinkedList的源码分析
LinkedList的源码分析
- LinkedList的源码分析
- 一总体分析
- 1 链表的结点类
- 二双向链表操作相关方法
- 1 linkFirstE e
- 2 linkLastE e
- 3 linkBeforeE e NodeE succ
- 4 unlinkFirstNodeE f
- 5 unlinkLastNodeE l
- 6 unlinkNodeE x
- 三List和Deque接口共有方法实现
- 1 containsObject o
- 2 size
- 3 addE e
- 4 removeObject o
- 四Deque接口的实现
- 1 getFirst
- 2 getLast
- 3 removeFirst
- 4 removeLast
- 5 addFirstE e
- 6 addLastE e
- 7 peek
- 8 element
- 9 poll
- 10 remove
- 11 offerE e
- 12 offerFirstE e
- 13 offerLastE e
- 14 peekFirst
- 15 peekLast
- 16 pollFirst
- 17 pollLast
- 18 pushE e
- 19 pop
- 20 removeFirstOccurrenceObject o
- 21 removeLastOccurrenceObject o
- 22 descendingIterator
- 五List接口的实现
- 1 addAllCollection extends E c
- 2 addAllint index Collection extends E c
- 3 clear
- 4 getint index
- 5 setint index E element
- 6 addint index E element
- 7 removeint index
- 8 indexOfObject o
- 9 lastIndexOfObject o
- 10 listIteratorint index
- 11 toArray
- 12 toArrayT a
- 13 spliterator
- 六相关的辅助操作
- 1 isElementIndexint index
- 2 isPositionIndexint index
- 3 outOfBoundsMsgint index
- 4 checkElementIndexint index
- 5 checkPositionIndexint index
- 6 nodeint index
- 7 ListIterator的实现内部类
- 8 DescendingIterator类内部类
- 9 superClone
- 10 clone
- 11 LLSpliteratorE implements SpliteratorE内部类
- 七序列化
- 1 writeObjectjavaioObjectOutputStream s
- 2 readObjectjavaioObjectInputStream s
- 一总体分析
一、总体分析
- LinkedList是List和Deque的双向链表实现，实现了列表的所有的可选操作，允许列表元素为null。
- 所有的操作都是基于双向链表的。寻找某个索引的元素的操作将会从链表头到尾遍历链表，无论索引是否很接近。
- 这个实现不是同步的，是非线性安全的。如果多个线程同时访问一个LinkedList，并且至少有一个线程在修改链表的结构（删除、添加元素，改变元素的值不是结构的修改），需要进行同步控制，这一般由封装LinkedList的对象进行。
- 如果没有这样的对象，可以使用Collections.synchronizedList方法获得同步的列表，最好是在创建列表的时候就用该方法创建，以避免意外的非同步访问列表、
- 这个类的迭代器（iterator和listIterator方法返回的）是fail-fast机制的：如果迭代过程中，列表的结构发生改变会抛出ConcurrentModificationException（iterator自己的remove和add方法除外），因此，存在并发修改的情况下，iterator快速失败并清除，而不是做任意的，潜在危险的操作。
- 在不同步的并发修改的情况下，并不能肯定保证fail-fast机制。
这个类可以当做List使用，也可以当做队列/双端队列、栈使用。
这个类有有一个头指针和尾指针指向头尾结点，结点中包含一个指向前一个结点的指针和一个指向后一个结点的指针，其中，头结点没有上一个结点，尾结点没有下一个指针。当列表为空的时候，头尾指针都指向null。同时LinkedList还支持索引方式访问列表。LinkedList内部结构如图所示：
public class LinkedList<E>extends AbstractSequentialListimplements List, Deque, Cloneable, java.io.Serializable
{transient int size = 0; //默认不序列化，链表的大小/*** 指向第一个结点的指针* Invariant: (first == null && last == null) ||* (first.prev == null && first.item != null) //头结点没有前一个结点*/transient Node first; //默认不序列化/*** 指向最后一个结点的指针* Invariant: (first == null && last == null) ||* (last.next == null && last.item != null) //尾结点没有下一个结点*/transient Node last; //默认不序列化/*** 空的构造函数，创建一个空的链表*/public LinkedList() {}/*** 构造一个包含传入的集合元素的列表，顺序是集合的迭代器返回元素的顺序** @param c 提供数据集合* @throws NullPointerException 如果传入的集合是null的，则抛出该异常*/public LinkedList(Collectionextends E> c) {this(); //调用自己的无参构造函数addAll(c); //调用addAll方法，将所有的元素加入到列表中}...//序列号，序列化是使用private static final long serialVersionUID = 876323262645176354L;
} 1.1 链表的结点类
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;}
} 二、双向链表操作相关方法
2.1 linkFirst(E e)
作为链表的头结点加入链表
private void linkFirst(E e) {final Node f = first; //先记录原来的头结点//创建一个新的结点，指定它的上一个结点为null，下一个结点为当前的头结点final Node newNode = new Node<>(null, e, f); first = newNode; //头指针指向新创建的头结点if (f == null) //如果列表原来为空，那么尾节点指向当前头结点last = newNode;else//如果原来列表不为空，则让原来的头结点prev指针指向新建的头结点f.prev = newNode; size++; //增大列表大小modCount++; //增加列表修改次数
} 2.2 linkLast(E e)
作为链表尾结点插入链表
void linkLast(E e) {final Node l = last; //记录原来的尾结点//创建一个结点，指定上一个结点为原来的尾结点，下一个结点为nullfinal Node newNode = new Node<>(l, e, null); last = newNode; //尾指针指向新建的结点if (l == null) //原来的尾结点为null，则头指针指向新建的结点first = newNode;else//原来的列表不为空，则使得原来的尾结点的下一个结点指向新建的结点l.next = newNode;size++; //增大列表大小modCount++; //增加列表修改次数
} 2.3 linkBefore(E e, Node succ)
在不为null的结点succ前面插入一个结点e
void linkBefore(E e, Node succ) {// assert succ != null; 需要确保succ不为nullfinal Node pred = succ.prev; //获得succ的前一个//新建一个结点，前一个结点为succ的前一结点，后一个结点为succfinal Node newNode = new Node<>(pred, e, succ);succ.prev = newNode; //succ的前一个结点设置为新建的结点//如果原来succ是头结点则，头指针指向新建的结点（新建的结点为头结点）if (pred == null)first = newNode;else//否则设置原来succ的前一个结点的后一个结点为新建的结点pred.next = newNode;size++; //增大列表大小modCount++; //增加列表修改次数
} 2.4 unlinkFirst(Node f)
删除头结点，需要保证 f 不为null且指向头结点，返回删除结点的值
private E unlinkFirst(Node f) {// assert f == first && f != null;final E element = f.item; //记录头结点的值final Node next = f.next; //记录下一个结点，需要作为新的头结点f.item = null; //释放该结点的值f.next = null; //删除指向下一个结点的引用，便于垃圾回收first = next; //头指针指向 f 的下一个结点//f 下一个结点为空，链表说明只有一个结点，尾指针指向空if (next == null) last = null;else//删除头结点，next作为头结点，使其上一个结点指向nullnext.prev = null;size--; //减小链表大小modCount++; //增加修改次数return element; //返回头结点的值
} 2.5 unlinkLast(Node l)
删除尾结点，需要保证 l 不为null且指向尾结点，返回删除的结点的值
private E unlinkLast(Node l) {// assert l == last && l != null;final E element = l.item; //记录尾结点的值final Node prev = l.prev; //记录尾结点的前一个结点l.item = null; //释放尾结点的值l.prev = null; //释放指向前一个结点的指针 last = prev; //使前面一个结点作为尾结点//如果 l 上一个结点，说明链表只有一个结点，头指针指向空if (prev == null) first = null;else//删除尾结点后，prev作为尾结点，使其下一个结点为nullprev.next = null;size--; //减小链表大小modCount++; //增加修改次数return element; //返回尾结点的值
} 2.6 unlink(Node x)
删除中间结点 x，需要保证 x 不为null，返回删除结点的值，可以是头结点和尾结点；
E unlink(Node x) {// assert x != null;final E element = x.item; //记录删除结点的值final Node next = x.next; //记录上一个结点final Node prev = x.prev; //记录下一个结点//如果上一个结点为null，则表示删除的是头结点，则头指针指向下一个结点if (prev == null) {first = next;} else {//prev结点的next指针指向next结点prev.next = next;x.prev = null; //将x结点的前一个指针指向null}//如果下一个结点为null，则表示删除的是尾结点，则尾指针指向下一个结点if (next == null) {last = prev;} else {next.prev = prev;x.next = null; //将x结点的下一个指针指向null}x.item = null; //释放结点的值size--; //减小列表的大小modCount++; //增加修改次数return element; //返回删除的节点的值
} 三、List和Deque接口共有方法实现
3.1 contains(Object o)
该方法用于判断 o 是否包含在列表中（列表至少存在一个o，当o为null时，判断列表中是否存在元素为null的元素），如果包含，则返回true，否则返回false
public boolean contains(Object o) {return indexOf(o) != -1;
}3.2 size()
返回列表的大小
public int size() {return size;
}3.3 add(E e)
该方法用于向列表的末尾添加一个元素，并返回是否添加成功，这个方法和addLast方法一致。
public boolean add(E e) {linkLast(e); //调用添加尾结点的方法return true; //没有异常，返回true
}3.4 remove(Object o)
该方法用于删除一个给定的元素o，删除第一在列表中找到的 o 元素。如果列表中不存在这个元素，列表不会改变。删除最小索引的元素e，如果 o==null ? e==null : o.equals(e)，如果列表中包含元素o，则返回true（也即，当执行了这个方法后，列表发生改变）。
public boolean remove(Object o) {if (o == null) { //如果o为null，则查找列表中为null的元素。for (Node x = first; x != null; x = x.next) { //从链表头开始查找if (x.item == null) { //找到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; //没有找到对应的元素，返回false
} 四、Deque接口的实现
4.1 getFirst()
该方法用于返回列表的第一个元素，列表中没有元素则抛出NoSuchElementException异常
public E getFirst() {final Node f = first; //获得头指针if (f == null) //头指针为空，则列表为空，抛出异常throw new NoSuchElementException();return f.item; //返回头结点的值
} 4.2 getLast()
该方法用于返回列表的最后一个元素，列表中没有元素则抛出NoSuchElementException异常
public E getLast() {final Node l = last; //获得尾指针if (l == null) //尾指针指向null，则列表为空，抛出异常throw new NoSuchElementException();return l.item; //返回尾结点的值
} 4.3 removeFirst()
该方法用于删除列表的第一个元素，如果列表为空，则抛出NoSuchElementException异常，返回第一个元素的值
public E removeFirst() {final Node f = first; //获得头指针if (f == null) //头指针为空，说明列表为空，抛出异常throw new NoSuchElementException();return unlinkFirst(f); //调用删除头结点的方法
} 4.4 removeLast()
该方法用于删除列表的最后一个元素，如果列表为空，则抛出NoSuchElementException异常，返回最后一个元素的值
public E removeLast() {final Node l = last; //获得尾指针if (l == null) //尾指针为空，说明列表为空，抛出异常throw new NoSuchElementException();return unlinkLast(l); //调用删除尾结点的方法
} 4.5 addFirst(E e)
在列表的第一个元素的位置添加一个元素
public void addFirst(E e) {linkFirst(e); //调用添加头结点的方法
}4.6 addLast(E e)
在列表的末尾添加一个元素
public void addLast(E e) {linkLast(e); //调用添加尾结点的方法
}4.7-4.11是队列的实现
4.7 peek()
返回头结点的元素，但不删除头结点，如果队列（列表）为空，则返回null
public E peek() {final Node f = first; //获得头结点//判断头指针是否为null，不是则返回头结点元素值return (f == null) ? null : f.item;
} 4.8 element()
返回头结点的元素，但不删除头结点，如果队列（列表）为空，则抛出NoSuchElementException
public E element() {return getFirst(); //调用getFirst()，并返回头结点的值
}4.9 poll()
删除头结点并返回头结点的值，如果队列空，返回null。
public E poll() {final Node f = first; //获得头结点return (f == null) ? null : unlinkFirst(f); //如果不为null则调用删除头结点方法
} 4.10 remove()
删除头结点，并返回头结点的值，如果队列为空，则抛出异常NoSuchElementException
public E remove() {return removeFirst(); //调用removeFirst()，并返回头结点的值
}4.11 offer(E e)
向队列尾添加一个元素，返回是否添加成功
public boolean offer(E e) {return add(e); //调用列表的add(E e)方法
}后面的是双端队列的实现
4.12 offerFirst(E e)
在列表头添加一个元素
public boolean offerFirst(E e) {addFirst(e); //调用添加第一个元素的方法return true;
}4.13 offerLast(E e)
在列表尾添加一个元素
public boolean offerLast(E e) {addLast(e); //调用添加最后一个元素的方法return true;
}4.14 peekFirst()
获得列表第一个元素但不删除，如果列表为空则返回null，与peek()一样
public E peekFirst() {final Node f = first; //获得头结点//如果头结点是null则返回null，否则头结点的元素值return (f == null) ? null : f.item; } 4.15 peekLast()
获得列表最后一个元素但不删除，如果列表为空则返回null
public E peekLast() {final Node l = last; //获得尾结点//如果尾结点是null则返回null，否则头结点的元素值return (l == null) ? null : l.item;
} 4.16 pollFirst()
删除头结点并返回头结点的值，如果队列空，返回null。
public E pollFirst() {final Node f = first; //获得头结点return (f == null) ? null : unlinkFirst(f); //如果不为null则调用删除头结点方法
} 4.17 pollLast()
删除尾结点并返回尾结点的值，如果队列空，返回null。
public E pollLast() {final Node l = last; //获得尾结点return (l == null) ? null : unlinkLast(l); //如果不为null则调用删除尾结点方法
} 4.18-4.19为Deque接口中定义的栈的操作
4.18 push(E e)
将一个元素入栈（栈是列表的表示的），也即在列表开头插入一个元素
public void push(E e) {addFirst(e); //调用addFirst(E e)的方法
}4.19 pop()
实现栈的出栈操作（列表表示的栈），并返回栈顶的元素。也即删除并返回列表的第一个元素，如果列表为空，则抛出NoSuchElementException异常
public E pop() {return removeFirst(); //调用removeFirst()的方法
}4.20 removeFirstOccurrence(Object o)
删除第一个队列中出现的 o（从链表头开始遍历），如果不存在，列表不会改变。如果删除元素，则返回true，否则返回false
public boolean removeFirstOccurrence(Object o) {return remove(o); //调用remove(Object o)方法
}4.21 removeLastOccurrence(Object o)
删除队列中最后一次出现的元素，如果不存在这样的元素，队列不会修改，返回false，否则返回true。
public boolean removeLastOccurrence(Object o) {if (o == null) { //如果o为null，寻找最后一个元素值为null的结点，并删除//从列表的结尾开始寻找，找到（第一个）则调用删除结点的方法删除找到的结点，并返回truefor (Node x = last; x != null; x = x.prev) {if (x.item == null) {unlink(x);return true;}}} else { //如果o不为null，寻找最后一个元素值o.equals(x.item)返回true的结点，并删除//从列表的结尾开始寻找，找到（第一个）则调用删除结点的方法删除找到的结点，//并返回truefor (Node x = last; x != null; x = x.prev) {if (o.equals(x.item)) {unlink(x);return true;}}}return false; //没有找到，返回false
} 4.22 descendingIterator()
返回一个递减的迭代器（从最后一个元素开始，向前迭代）
public Iterator descendingIterator() {return new DescendingIterator(); //返回内部类实例
} 五、List接口的实现
5.1 addAll(Collection c)
将传入的集合 c 中的所有元素加入到列表的末尾，以集合 c 的迭代器返回元素的顺序添加。在这个方法操作的过程中，如果传入的集合发生修改，操作结果将变得不明确（当c就是当前列表本身且不为空，就是这种情况）。如果传入的集合c为null，将会抛出NullPointerException异常
public boolean addAll(Collection c) {return addAll(size, c);}5.2 addAll(int index, Collection c)
从index开始，向列表中插入集合 c 中的所有的元素，将原来位于index和其之后的元素向右移，增大他们的索引，添加元素的顺序与集合迭代器返回值相同。
/*** @param index 开始插入元素的下标* @param c 提供数据元素的集合* @return 如果列表改变了，返回true* @throws IndexOutOfBoundsException 当index不在正确的范围是抛出该异常* @throws NullPointerException 集合c为null时*/
public boolean addAll(int index, Collection c) {checkPositionIndex(index); //检查插入位置是否正确Object[] a = c.toArray(); //将集合c转化为数组int numNew = a.length; //需要加入的元素的个数if (numNew == 0) //如果需要加入的元素个数为0,返回falsereturn false;Node pred, succ; //pred为index处结点的上一个结点，succ为index处的结点//当index == size，表示在链表的末尾添加，succ为null，上一个结点为尾结点if (index == size) { succ = null;pred = last;} else {//否则通过node方法找到index处的结点，pred指向其前一个结点succ = node(index);pred = succ.prev;}//在pred之后，succ之前添加元素for (Object o : a) {@SuppressWarnings("unchecked") E e = (E) o;//新建一个结点，指定上一个结点为pred，下一个结点为nullNode newNode = new Node<>(pred, e, null);//如果pred结点为null，则说明添加头结点if (pred == null)first = newNode;else //否则将pred的下一个结点设置为新建的结点pred.next = newNode;pred = newNode; //往后移动元素}//在列表之后添加或者原列表为空，尾指针指向pred（添加的最后一个结点）if (succ == null) {last = pred;} else {//否则设置添加的最后一个结点(pred)的下一个结点为succ，succ的上一个结点为predpred.next = succ;succ.prev = pred;}size += numNew; //修改列表的大小modCount++; //增加列表修改次数return true; //添加了元素，则返回true
} 5.3 clear()
清除列表中的所有元素，操作完成后，列表为空。
虽然清除所有链接不是必须的，但是进行链接清除可以：
帮助进行分代垃圾回收如果废弃的结点占据了一整代推内存
即使创建了迭代器，也能确保释放内存
public void clear() {//从头开始遍历结点，释放结点所有的引用for (Node x = first; x != null; ) {Node next = x.next;x.item = null;x.next = null;x.prev = null;x = next;}first = last = null; //设置头尾指针为nullsize = 0; //设置列表大小为0modCount++; //增加修改次数
} 5.4 get(int index)
获得列表中index处的元素，需要检查index是否在正确的范围，不在正确的范围中，则抛出IndexOutOfBoundsException异常，返回的是index处的元素。
public E get(int index) {checkElementIndex(index); //检查index是否合法return node(index).item; //调用node(int index)获得第index个结点
}5.5 set(int index, E element)
设置第index个元素为 element，返回原来的值。需要检查index是否在正确的范围，不在正确的范围中，则抛出IndexOutOfBoundsException异常。
public E set(int index, E element) {checkElementIndex(index); //检查index是否合法Node x = node(index); //调用node(int index)获得第index个结点E oldVal = x.item; //获得原来的值x.item = element; //将值设置为elementreturn oldVal;
} 5.6 add(int index, E element)
该方法在index的位置添加一个元素element，将原来index和其之后的元素向后移动（索引增大），需要检查添加元素的位置，不在正确的范围将抛出IndexOutOfBoundsException异常。
public void add(int index, E element) {checkPositionIndex(index); //检查index是否正确//index==size，说明在列表的末尾添加一个元素，调用添加尾结点的方法if (index == size)linkLast(element);elselinkBefore(element, node(index)); //否则调用在index结点前插入元素的方法
}5.7 remove(int index)
移除列表第index个元素，后面的元素向左移动（索引减小），返回被移除的元素。需要检查被移除的元素的位置，不在正确的范围将抛出IndexOutOfBoundsException异常。
public E remove(int index) {checkElementIndex(index); //检查index范围return unlink(node(index)); //调用删除结点的方法并返回
}5.8 indexOf(Object o)
查找 o 在列表中位置，如果列表中存在 o，则返回第一个 o 的索引；不存在则返回-1。
o==null ? get(i)==null : o.equals(get(i)) 使得结果为true的第一个i
public int indexOf(Object o) {int index = 0;if (o == null) { //o为null，查找列表中为null的元素//从链表头开始遍历for (Node x = first; x != null; x = x.next) {if (x.item == null)return index;index++;}} else { //o为不为null，查找列表中o.equals(x.item)返回true的元素//从链表头开始遍历for (Node x = first; x != null; x = x.next) {if (o.equals(x.item))return index;index++;}}return -1; //列表中不存在这样的元素，返回-1。
} 5.9 lastIndexOf(Object o)
查找最后一个 o 在列表中位置，如果列表中存在 o，则返回最后一个 o 的索引；不存在则返回-1。该方法与上个方法相反
public int lastIndexOf(Object o) {int index = size; //设置初始为index为列表大小，从尾结点开始查找if (o == null) { //o为null，查找列表中为null的元素//从链表尾开始向前遍历for (Node x = last; x != null; x = x.prev) {index--;if (x.item == null)return index;}} else { //o为不为null，查找列表中o.equals(x.item)返回true的元素//从链表尾开始向前遍历for (Node x = last; x != null; x = x.prev) {index--;if (o.equals(x.item))return index;}}return -1; //列表中不存在这样的元素，返回-1。
} 5.10 listIterator(int index)
该方法返回一个迭代器（ListIterator），从index开始，遵循List.listIterator(int)的基本规定。第一次调用next方法返回的元素就是index处的元素，调用previous方法，返回index的前一个元素。
list-iterator是fail-fast的：当迭代器创建之后，如果有任意的操作（除了迭代器自己的remove和add方法除外）改变列表的结构，将抛出ConcurrentModificationException异常。因此，如果存在同步的操作，迭代器将快速失败，并且清除，而不是做任意的，潜在危险的操作。
/*** @param index 迭代器next方法返回的第一个元素* @return 返回一个特定位置开始的list-iterator* @throws IndexOutOfBoundsException index不在正确范围，抛出此异常*/
public ListIterator listIterator(int index) {checkPositionIndex(index); //检查是否是正确的位置return new ListItr(index); //返回一个ListIterator，内部类的实例
} 5.11 toArray()
返回一个包含所有列表元素的数组，按照正确的顺序排列（从列表的第一个元素到最后一个元素），这个数组是浅拷贝（列表中的结点的元素引用相同，引用的对象的相同的）。这个方法需要创建新的数组来保存对象的引用。这个方法是数组和结合沟通的桥梁。
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; //返回数组
} 5.12 toArray(T[] a)
- 返回一个包含所有列表元素的数组，按照正确的顺序排列（从列表的第一个元素到最后一个元素），数组的返回类型由传入的数组的类型决定。如果传入的数组大小适合存放列表的元素，则返回传入的数组（给传入的数组赋值），否则创建一个新的数组，数组类型是传入的数组的类型。
- 如果传入的数组的大小大于列表的大小，超出的部分使用null填充，这唯一的用处是，如果调用者知道列表中不包含null的元素，则可以知道列表的大小。
- 和toArray()一样，这个方法是数组和结合沟通的桥梁。此外,这种方法允许精确控制输出数组的运行时类型,也可能,在某些情况下,被用来节省分配成本。
- 假设x是一个只有String类型的列表，下面这种调用方式将创建新的数组（方法内）
String[] y = x.toArray(new String[0]);
注意：toArray(new Object[0])和toArray()是一样的
@SuppressWarnings("unchecked")
public T[] toArray(T[] a) {if (a.length < size) //传入的数组不能存放所有的列表元素，创建新的数组a = (T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);int i = 0;Object[] result = a;//从头到尾取出链表的结点，并将结点的值赋给对应的数组元素for (Node x = first; x != null; x = x.next)result[i++] = x.item;//如果传入数组的大小超出列表的大小，剩余部分使用null填充if (a.length > size)a[size] = null;return a; //返回数组
} 5.13 spliterator()
创建一个基于列表的延迟绑定的并且是fail-fast的Spliterator。Spliterator特征是符合的SIZED和ORDERED，重写实现需要指定额外的特征，需要说明
实现注意点：Spliterator指定SUBSIZED和实现trySplit允许有限的并行性
@Override
public Spliterator spliterator() {return new LLSpliterator(this, -1, 0); //返回一个LLSpliterator实例
} 六、相关的辅助操作
6.1 isElementIndex(int index)
判断index是否是元素的正确索引
private boolean isElementIndex(int index) {return index >= 0 && index < size; //当index在[0,size)之间时返回true
}6.2 isPositionIndex(int index)
判断index是否是迭代器或添加元素的正确位置
private boolean isPositionIndex(int index) {return index >= 0 && index <= size; //当index在[0,size]之间时返回true
}6.3 outOfBoundsMsg(int index)
该方法用于生成索引超出列表范围的错误信息（IndexOutOfBoundsException异常的详细信息），和其他许多可能的异常处理代码重构相比，这个方法可以在server模式和client模式的虚拟机上表现得很好。
private String outOfBoundsMsg(int index) {return "Index: "+index+", Size: "+size; //生成并返回异常信息
}6.4 checkElementIndex(int index)
检查index是否是列表的正确索引，不正确则抛出异常，调用了isElementIndex(int index)检查是否是正确的索引
private void checkElementIndex(int index) {if (!isElementIndex(index)) //如果不是正确的索引则抛出异常throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}6.5 checkPositionIndex(int index)
检查index是否是迭代器或添加元素的正确位置，不正确则抛出异常，调用了isPositionIndex(int index)检查是否是正确的范围
private void checkPositionIndex(int index) {if (!isPositionIndex(index)) //如果不是正确的位置则抛出异常throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}6.6 node(int index)
获取第index个结点，并返回一个结点，调用前需要确保调用者已经检查范围。
Node node(int index) {// assert isElementIndex(index);//index在列表前半部分，则从头结点开始查找if (index < (size >> 1)) {Node x = first;for (int i = 0; i < index; i++)x = x.next;return x;} else {//否则（在列表后半部分），从尾结点开始查找Node x = last;for (int i = size - 1; i > index; i--)x = x.prev;return x;}
} 6.7 ListIterator的实现，内部类
private class ListItr implements ListIterator {private Node lastReturned; //上次迭代的结点的指针private Node next; //下一个结点的指针，next返回的元素的结点private int nextIndex; //下一个结点的索引private int expectedModCount = modCount; //期望的修改次数，用于fast-fail机制//构造方法，传入起始迭代索引，并设置下一个结点的值，调用前先检查位置是否正确ListItr(int index) {// assert isPositionIndex(index);//如果index==size表示尾结点的后一个元素，否则通过node(int index)方法找到结点next = (index == size) ? null : node(index);nextIndex = index; //设置下一个结点的索引为index}//是否有下一个元素，当下一个元素nextIndex小于列表大小时，//说明存在下一个元素，返回truepublic boolean hasNext() {return nextIndex < size;}//返回下一个结点，首先检查修改次数，如果发生修改，//则抛出ConcurrentModificationExceptionpublic E next() {checkForComodification(); //检查是否修改if (!hasNext()) //如果没有下一个元素，抛出NoSuchElementException异常throw new NoSuchElementException();lastReturned = next; //设置上一个访问结点指针为next（当前访问结点）next = next.next; //下一个结点指针指向当前结点的下一个结点nextIndex++; //下一个结点索引加1return lastReturned.item; //返回当前结点的元素的值}//判断是否有前一个元素，当nextIndex > 0时，存在上一个结点，返回true，//否则返回falsepublic boolean hasPrevious() {return nextIndex > 0;}//返回上一个结点，首先检查修改次数，如果发生修改，//则抛出ConcurrentModificationExceptionpublic E previous() {checkForComodification(); //检查是否修改if (!hasPrevious()) //如果没有上一个元素，抛出NoSuchElementException异常throw new NoSuchElementException();//当前要返回(next方法)的值为last下一个元素，则是上一个元素为last（尾结点）//否则返回的上一个元素为next(当前结点)的上一个结点，下一个结点也为next.prevlastReturned = next = (next == null) ? last : next.prev;nextIndex--; //减小下一个元素的索引return lastReturned.item; //返回上一个元素的值}//返回下一个元素的索引public int nextIndex() {return nextIndex;}//返回上一个元素的索引public int previousIndex() {return nextIndex - 1; //当前元素索引减1}//删除当前指向的结点public void remove() {checkForComodification(); //检查是否修改//删除上一次调用next方法后的值，如果为null，抛出IllegalStateException异常if (lastReturned == null) throw new IllegalStateException();//记录下一个结点，下一次next方法需要返回的值Node lastNext = lastReturned.next;unlink(lastReturned); //从链表中删除if (next == lastReturned) //如果next结合和lastReturned指向同一个结点（调用previous方法）next = lastNext; //记录下一个结点为lastNextelsenextIndex--; //不相同，next已经指向下一个结点， 下一个结点索引减小lastReturned = null;expectedModCount++; //期望修改次数增大}//设置上一次next方法返回的结点的元素的值public void set(E e) {//删除上一次调用next方法后的值，如果为null，抛出IllegalStateException异常if (lastReturned == null) throw new IllegalStateException();checkForComodification(); //检查修改次数lastReturned.item = e; //修改值}//向列表中添加一个元素public void add(E e) {checkForComodification(); //检查是否修改lastReturned = null;if (next == null) //如果next指向null，说明已经到遍历到尾linkLast(e); //在链表尾添加一个元素elselinkBefore(e, next); //否则在next前添加一个元素nextIndex++; //下一个结点索引增加1（还是指向没有添加前的结点）expectedModCount++; //增加期望修改次数}//对于还未遍历（没有next到尾的），使用特点的动作操作每一个元素public void forEachRemaining(Consumer action) {Objects.requireNonNull(action); //检查action是否为null//如果没有修改过且没有遍历到尾执行操作，每次操作，//修改lastReturned和next指向的结点，增加下一个结点的索引while (modCount == expectedModCount && nextIndex < size) {action.accept(next.item);lastReturned = next;next = next.next;nextIndex++;}checkForComodification(); //检查是否修改}//检查是否修改，修改则抛出ConcurrentModificationException异常final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();}
} 6.8 DescendingIterator类，内部类
该类实现了Iterator（迭代器），通过类中维持一个ListItr类，通过其previous方法实现向前迭代。
private class DescendingIterator implements Iterator<E> {//建立一个从列表尾开始的迭代器private final ListItr itr = new ListItr(size()); //是否有"下一个"，即是否有前一个几点，通过itr的hasPrevious方法实现public boolean hasNext() {return itr.hasPrevious();}//返回"下一个"结点元素值，通过itr的previous方法返回public E next() {return itr.previous();}//删除当前节点，通过itr的remove方法操作public void remove() {itr.remove();}
}6.9 superClone()
调用父类的克隆方法，如果不支持该操作，抛出异常
@SuppressWarnings("unchecked")
private LinkedList superClone() {try {return (LinkedList) super.clone(); //调用父类的克隆方法} catch (CloneNotSupportedException e) { //如果不支持该操作，抛出异常throw new InternalError(e);}
} 6.10 clone()
克隆当前LinkedList实例，返回当前LinkedList的一个浅拷贝
public Object clone() {LinkedList clone = superClone(); //调用父类的clone方法// 设置clone为初始状态clone.first = clone.last = null;clone.size = 0;clone.modCount = 0;// 通过当前列表初始化，向clone添加列表中的元素//创建的新的链表，链表中每一个结点中的元素和当前结点元素引用相同for (Node x = first; x != null; x = x.next)clone.add(x.item);return clone;
} 6.11 LLSpliterator implements Spliterator，内部类
Spliterators.IteratorSpliterator的自定义实现，不太懂
static final class LLSpliterator<E> implements Spliterator<E> {static final int BATCH_UNIT = 1 << 10; // 每次增加的批处理数量（每次批处理数）static final int MAX_BATCH = 1 << 25; // 最大的批处理大小final LinkedList list; // 可以是null，除非需要遍历Node current; // 当前结点，为null直到初始化int est; // 用户查询大小，等于-1直到初始化（还没有被处理过的数量）int expectedModCount; // 当est设置时，初始化，期望的修改次数int batch; // 已经批处理的数量//构造函数LLSpliterator(LinkedList list, int est, int expectedModCount) {this.list = list;this.est = est;this.expectedModCount = expectedModCount;}final int getEst() {int s; // 强制初始化final LinkedList lst;if ((s = est) < 0) {if ((lst = list) == null) //列表为空，est初始化为0s = est = 0;else {expectedModCount = lst.modCount; //初始化expectedModCountcurrent = lst.first; //初始化current，使其指向第一个结点s = est = lst.size; //初始化为列表的大小}}return s; //返回大小}public long estimateSize() { return (long) getEst(); } //获得大小//创建一个更小范围的Spliteratorpublic Spliterator trySplit() {Node p;int s = getEst();if (s > 1 && (p = current) != null) {int n = batch + BATCH_UNIT; //新的分割包含元素数量if (n > s) //n超出当前Spliterator范围，最大为sn = s;if (n > MAX_BATCH) //超出最大范围n = MAX_BATCH;Object[] a = new Object[n];int j = 0;//获取相应的数量的元素，保存到数组do { a[j++] = p.item; } while ((p = p.next) != null && j < n);current = p; //指向剩余元素的第一个batch = j;est = s - j; //est设置为剩余的个数return Spliterators.spliterator(a, 0, j, Spliterator.ORDERED);}return null;}//对剩余的没有的处理的元素执行特定的操作public void forEachRemaining(Consumersuper E> action) {Node p; int n;//“消费者”（执行动作的对象）为null，抛出NullPointerException异常if (action == null) throw new NullPointerException();if ((n = getEst()) > 0 && (p = current) != null) {current = null; //设置为null，处理完成后current应该为null；est = 0; //遍历完后est应该为null//遍历处理do {E e = p.item;p = p.next;action.accept(e);} while (p != null && --n > 0);}if (list.modCount != expectedModCount) //检查是否有修改throw new ConcurrentModificationException();}//对当前的元素执行特定的操作public boolean tryAdvance(Consumersuper E> action) {Node p;//“消费者”（执行动作的对象）为null，抛出NullPointerException异常if (action == null) throw new NullPointerException();if (getEst() > 0 && (p = current) != null) {--est;E e = p.item;current = p.next; //移动到下一个结点action.accept(e); //处理当前元素if (list.modCount != expectedModCount) //检查是否有修改throw new ConcurrentModificationException();return true; //执行没有问题，返回true}return false; //执行失败，返回false}//特征public int characteristics() {return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;}
} 七、序列化
7.1 writeObject(java.io.ObjectOutputStream s)
如果一个可以序列化的类中包含此方法，java序列化不会调用默认的序列化，而是使用该方法实现的类的序列化，将实例的状态保存到一个流中。
private void writeObject(java.io.ObjectOutputStream s)throws java.io.IOException {// 调用默认序列化方法，写入一些隐藏的序列化信息s.defaultWriteObject();// 写列表的大小s.writeInt(size);// 按照正确顺序写列表中数据for (Node x = first; x != null; x = x.next)s.writeObject(x.item);
} 7.2 readObject(java.io.ObjectInputStream s)
如果一个可以序列化的类中包含此方法，反序列化时，java序列化不会调用默认的反序列化，而是使用该方法实现的类的反序列化机制，将一个流中读取实例信息。
@SuppressWarnings("unchecked")
private void readObject(java.io.ObjectInputStream s)throws java.io.IOException, ClassNotFoundException {// 调用默认反序列化方法，读取一些隐藏的序列化信息s.defaultReadObject();// 读取列表的大小int size = s.readInt();// 读取元素，并加入列表，使用添加链表尾结点的方法保存元素for (int i = 0; i < size; i++)linkLast((E)s.readObject());
}本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！