【java】Linklist源码解读JDK1.8
程序员文章站
2022-06-04 18:57:28
...
本文旨在对Linklist源码进行解读，对代码基本进行了逐行注释并且将遇到的问题做出说明。
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
transient int size = 0;//元素个数
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;//头节点
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;//尾节点。
/**
* Constructs an empty 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如果指定的集合为空
*/
public LinkedList(Collection<? extends E> c) {//LInk采用双向链表所以每个节点即知道谁指向他，也知道他指向谁
this();
addAll(c);
}
/**
* Links e as first element.链接e作为第一个元素。
*/
private void linkFirst(E e) {//前插法，给f前面加节点
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);//构造出的（上一节点首地址，本节点元素内容，下节点首地址）
first = newNode;
if (f == null)
last = newNode;//若f为null则，新节点既是头也是尾
else
f.prev = newNode;//否则将f的头指向新节点
size++;//元素个数增加
modCount++;//修改次数增加
}
/**
* Links e as last element.链接e作为最后一个元素。
*/
void linkLast(E e) {//尾插法，给最后一个节点后加
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);//新节点成为最后节点，他只有前驱，没有后继
last = newNode;
if (l == null)
first = newNode;//若本身最后一节点为null，则新节点即为头部也为尾巴
else
l.next = newNode;//不然他就时l的后继
size++;//元素个数增加
modCount++;//修改次数增加
}
/**
* Inserts element e before non-null Node succ.在非空节点succ之前插入元素e。
*/
void linkBefore(E e, Node<E> succ) {//向一指定节点前插法，相当于给两个节点中加一个，本身右边节点前驱是左，左节点后继是右
//那么新节点的后继就是右节点，新节点的前驱就是左节点，所以新节点的前驱就是原本右节点的前驱
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
/**
* Unlinks non-null first node f.取消非空的第一个节点f的链接。
*/
private E unlinkFirst(Node<E> f) {//删除头节点
// assert f == first && f != null;
final E element = f.item;//取出原本头节点的元素
final Node<E> next = f.next;//取出头节点的后继
f.item = null;//全清为null，方便GC
f.next = null; // help GC
first = next;
if (next == null)//若没有后继节点，则说明他是唯一节点，删除后链表为空
last = null;
else
next.prev = null;//将下一节点的前驱设置为null，即原本的后继节点为头节点
size--;//元素个数减一
modCount++;//修改次数加一
return element;//返回原始头节点内容
}
/**
* Unlinks non-null last node l.取消非空最后一个节点l的链接
*/
private E unlinkLast(Node<E> l) {//删除末尾节点，操作与上面思路一致
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
/**
* Unlinks non-null node x.取消非空节点x的链接。
*/
E unlink(Node<E> x) {//删除某一个中间节点
// assert x != null;
final E element = x.item;//取出该节点的元素
final Node<E> next = x.next;//取出该节点后继
final Node<E> prev = x.prev;//取出该节点前驱
if (prev == null) {//若是前驱节点为空，则说明他是头节点，删除他后则他的后继为头节点
first = next;
} else {
prev.next = next;//将前驱节点的next指向后继节点
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;//让后继节点的prev指向前驱
x.next = null;
}
x.item = null;
size--;//元素个数减一
modCount++;//修改次数++
return element;//返回原始元素
}
/**
* Returns the first element in this list.返回列表中的第一个元素。
*
* @return the first element in this list
* @throws NoSuchElementException if this list is empty
*/
public E getFirst() {//得到头节点元素
final Node<E> 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
*/
public E getLast() {//得到尾节点
final Node<E> 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
*/
public E removeFirst() {//删除并返回头节点
final Node<E> 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
*/
public E removeLast() {//删除并返回尾节点
final Node<E> 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
*/
public void addFirst(E e) {//头插法
linkFirst(e);
}
/**
* Appends the specified element to the end of this list.
*
* <p>This method is equivalent to {@link #add}.
*
* @param e the element to add
*/
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
* <tt>(o==null ? e==null : o.equals(e))</tt>.
*
* @param o element whose presence in this list is to be tested
* @return {@code true} if this list contains the specified element
*/
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
*/
public int size() {//返回列表中元素的数目
return size;
}
/**
* Appends the specified element to the end of this list.
*
* <p>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})
*/
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
//从列表中删除指定元素的第一个匹配项，
如果它存在。如果此列表不包含该元素，则它包含
*不变。更正式地说，删除索引最低的元素
* <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
*/
public boolean remove(Object o) {//删除指定元素第一次出现的位置，即从前往后遍历
if (o == null) {//和上面差不多的操作方法
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;//若没找到则返回flase
}
/**
* 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
*/
public boolean addAll(Collection<? extends E> c) {//将集合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
*/
//用addAll方法将集合加入指定下标处其原理就是，先将指定下标处的原节点断开，在将集合链加进去让集合链中第一个元素节点去连原
//节点的前驱节点，再让集合链的最后一个元素节点去将原节点作为后继，实现添加成功
public boolean addAll(int index, Collection<? extends E> c) {//将集合c加到指定下标处
checkPositionIndex(index);//检查index是否为可加入节点下标
Object[] a = c.toArray();//将集合c转化为Object数组
int numNew = a.length;//得到a的长度
if (numNew == 0)
return false;//若a长为0则说明集合c为空
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);//全都先给前驱连上，后继先不管设为null
if (pred == null)//若前驱节点为空，则说明该节点为头节点
first = newNode;
else
pred.next = newNode;//将前驱节点的后指针指向本节点，即补全上一节点的后继
pred = newNode;//每操作完一个节点，便将该节点设置为前驱，便于下次操作
}
if (succ == null) {//若新后继为空
last = pred;//将最后一个处理的节点设置为尾节点
} else {
pred.next = succ;//则将最后一个处理的节点连接上新后继
succ.prev = pred;//将新后继的前驱连接
}
size += numNew;//元素个数增加
modCount++;//操作次数增加
return true;
}
/**
* Removes all of the elements from this list.
* The list will be empty after this call returns.
从列表中删除所有元素。
*调用返回后，列表将为空
*/
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<E> x = first; x != null; ) {//从头往后遍历，每次处理节点的next暂时保存，然后清除，以此达到清除整个链表
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;//将头尾节点设置为空
size = 0;//将元素个数设置为0
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}
*/
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}
*/
public E set(int index, E element) {//将列表中指定位置的元素替换为指定元素。
checkElementIndex(index);//先调查下标合理性
Node<E> x = node(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}
*/
public void add(int index, E element) {//在指定位置加入新节点
checkPositionIndex(index);//检查下标是否可以加入元素
if (index == size)
linkLast(element);//尾加
else
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.//删除列表中指定位置的元素。任何变化
*左边的后续元素(从它们的索引中减去1)。
返回从列表中删除的元素。
*
* @param index the index of the element to be removed
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {//删除指定位置节点
checkElementIndex(index);//检查下标合理性
return unlink(node(index));//先通过下标取出该节点，然后删除
}
/**
* Tells if the argument is the index of an existing element.指示该参数是否为现有元素的索引。
*/
private boolean isElementIndex(int index) {//判断下标合理性，所以最大下标为size-1
return index >= 0 && index < size;
}
/**
* Tells if the argument is the index of a valid position for an说明参数是否为an的有效位置的索引
*迭代器或添加操作。
* iterator or an add operation.
*/
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) {//构造IndexOutOfBoundsException详细信息。
return "Index: "+index+", Size: "+size;
}
private void checkElementIndex(int index) {//检查下标合理性
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private void checkPositionIndex(int index) {//检查该下标处是否可以添加
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* Returns the (non-null) Node at the specified element index.返回指定元素索引处的(非空)节点。
*/
Node<E> node(int index) {//得到指定下标处的节点
// assert isElementIndex(index);
if (index < (size >> 1)) {//若链表元素个数远大于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;
}
}
// 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
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
//返回指定元素第一次出现的索引
*在该列表中，如果该列表不包含该元素，则为-1。
更正式地说，返回最低的索引{@code i}
*
* @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
*/
public int indexOf(Object o) {//指定元素第一次出现的下标，即从前往后找
int index = 0;//先设置初始下标标记位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;//没找到返回-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
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* 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
*/
public int lastIndexOf(Object o) {//返回指定元素最后一次出现的下标，即从后往前找
int index = size;//设置初始下标为元素个数
if (o == null) {//从后往前查找并修改下标
for (Node<E> x = last; x != null; x = x.prev) {
index--;//每遍历到一个就先减下标在操作，因为起始下标为size，若起始下标为size-1则可以先操作后减下标
if (x.item == null)
return index;
}
} else {
for (Node<E> 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
*/
public E peek() {//检查头节点元素
final Node<E> 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
*/
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
*/
public E poll() {//检索并删除头节点
final Node<E> 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
*/
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
*/
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
*/
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
*/
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
*/
public E peekFirst() {//检索但不删除此列表的第一个元素，如果该列表为空，则返回{@code null}
final Node<E> 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
*/
public E peekLast() {//检索但不删除此列表的最后一个元素，如果该列表为空，则返回{@code null}。
final Node<E> 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
*/
public E pollFirst() {//检索并删除列表中的第一个元素，如果该列表为空，则返回{@code null}。
final Node<E> 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
*/
public E pollLast() {//检索并删除列表中的最后一个元素，如果该列表为空，则返回{@code null}。
final Node<E> 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.
将元素推入此列表所表示的堆栈。在其他
* words，将元素插入到列表的前面。
*
* <p>This method is equivalent to {@link #addFirst}.
*
* @param e the element to push
* @since 1.6
*/
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.
从该列表表示的堆栈中弹出一个元素。在其他
* words，删除并返回列表的第一个元素
*
* <p>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
*/
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
*/
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
*/
public boolean removeLastOccurrence(Object o) {//删除元素的最后一次出现的位置
if (o == null) {//从后往前遍历，和上面的操作差不多
for (Node<E> x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> 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)}.<p>
返回此列表中元素的列表迭代器(在适当的情况下)
序列)，从列表中的指定位置开始。
*
* The list-iterator is <i>fail-fast</i>: 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)
*/
public ListIterator<E> listIterator(int index) {//返回此列表中元素的列表迭代器(在适当的情况下)
checkPositionIndex(index);//检查合理性
return new ListItr(index);
}
private class ListItr implements ListIterator<E> {//迭代器类
private Node<E> lastReturned;//最后一次操作的节点
private Node<E> next;//后继节点
private int nextIndex;//下一节点下标
private int expectedModCount = modCount;//将外面修改次数设置进来，保证操作时线程安全
ListItr(int index) {//构造器
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);//取出指定下标元素
nextIndex = index;//将本下标设置成员
}
public boolean hasNext() {//判断是否还有下一个元素
return nextIndex < size;
}
public E next() {//取得下一个元素
checkForComodification();//判断是否
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;//对于下次操作来说，本次操作就是最后一次操作，所以先修改最后一次操作的节点为本节点
next = next.next;//新的后继节点设置为本节点的后继节点
nextIndex++;//下标增加
return lastReturned.item;
}
public boolean hasPrevious() {//判断位置合理
return nextIndex > 0;
}
public E previous() {//取得上一节点
checkForComodification();//检查修改次数，保证线程安全
if (!hasPrevious())
throw new NoSuchElementException();
lastReturned = next = (next == null) ? last : next.prev;//若没后继，则说明下一节点为尾节点，否则就是下节点的前驱
nextIndex--;//下标减了
return lastReturned.item;
}
public int nextIndex() {//下一节点位置，因为在取得下一节点位置时本节点已经为最后操作的节点，所以nexIdex直接返回
return nextIndex;
}
public int previousIndex() {//上一节点位置
return nextIndex - 1;
}
public void remove() {//删除节点
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;//取出该节点后继节点
unlink(lastReturned);//删除该节点
if (next == lastReturned)
next = lastNext;//将后继节点设置为下一节点
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
public void set(E e) {//替换节点元素
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}
public void add(E e) {//加入元素
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
public void forEachRemaining(Consumer<? super E> action) {//遍历
Objects.requireNonNull(action);
while (modCount == expectedModCount && nextIndex < size) {
action.accept(next.item);
lastReturned = next;
next = next.next;
nextIndex++;
}
checkForComodification();
}
final void checkForComodification() {//检查修改次数和内部保存次数是否相同，避免线程安全问题
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
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;
}
}
/**
* @since 1.6
*/
public Iterator<E> descendingIterator() {
return new DescendingIterator();
}