6.1.2 add(int index, E element)方法
// 作用：在指定位置添加元素 public void add(int index, E element) { // 检查插入位置的索引的合理性 checkPositionIndex(index); if (index == size) // 插入的情况是尾部插入的情况：调用linkLast（）解释如上。 linkLast(element); else // 插入的情况是非尾部插入的情况（中间插入）：linkBefore（）见下面。 linkBefore(element, node(index)); } private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private boolean isPositionIndex(int index) { return index >= 0 && index <= size; } 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的前节点，后接点是succ节点 succ.prev = newNode; // 更新插入位置（succ）的前置节点为新节点 if (pred == null) // 如果pred为null，说明该节点插入在头节点之前，要重置first头节点 first = newNode; else // 如果pred不为null，那么直接将pred的后继指针指向newNode即可 pred.next = newNode; size++; modCount++; }
6.1.3 get(int index)方法
public E get(int index) { // 元素下表的合理性检查 checkElementIndex(index); // node(index)真正查询匹配元素并返回 return node(index).item; } // 作用：查询指定位置元素并返回 Node<E> node(int index) { // assert isElementIndex(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; }
6.1.4 remove(int index)方法
// 作用：移除指定位置的元素 public E remove(int index) { // 移除元素索引的合理性检查 checkElementIndex(index); // 将节点删除 return unlink(node(index)); } 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; // 得到指定节点的前继节点 // 如果prev为null表示删除是头节点，否则就不是头节点 if (prev == null) { first = next; } else { prev.next = next; x.prev = null; // 置空需删除的指定节点的前置节点（null） } // 如果next为null,则表示删除的是尾部节点，否则就不是尾部节点 if (next == null) { last = prev; } else { next.prev = prev; x.next = null; // 置空需删除的指定节点的后置节点 } // 置空需删除的指定节点的值 x.item = null; size--; // 数量减1 modCount++; return element; }
6.1.5 clear()方法
// 清空链表 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循环，进行逐条置空；直到最后一个元素 for (Node<E> x = first; x != null; ) { Node<E> next = x.next; x.item = null; x.next = null; x.prev = null; x = next; } // 置空头和尾为null first = last = null; size = 0; modCount++; }
6.1.6 indexOf(Object o)
// 返回元素在链表中的索引，如果不存在则返回-1 public int indexOf(Object o) { int index = 0; // 如果元素为null，进行如下循环判断 if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { // 元素不为null.进行如下循环判断 for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; }
6.2 Duque接口
6.2.1 addFirst(E e)方法
// 作用：在链表头插入指定元素 public void addFirst(E e) { linkFirst(e); } private void linkFirst(E e) { final Node<E> f = first; // 获取头部元素 final Node<E> newNode = new Node<>(null, e, f); // 创建新的头部元素（原来的头部元素变成了第二个） first = newNode; // 链表头部为空，（也就是链表为空） if (f == null) last = newNode; // 头尾元素都是e else f.prev = newNode; // 否则就更新原来的头元素的prev为新元素的地址引用 size++; modCount++; }
6.2.2 addLast(E e)方法
// 作用：在链表尾部添加元素e public void addLast(E e) { // 上面已讲解过，参考上面。add()方法 linkLast(e); }
6.2.3 push(E e)方法
// 作用:往链表头部添加元素e public void push(E e) { addFirst(e); }
6.2.4 getFirst()方法
// 作用：得到头元素 public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; }
6.2.5 getLast()方法
// 作用：得到尾部元素 public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; }
6.2.6 peek()方法
// 作用：返回头元素，并且不删除。如果不存在也不错，返回null public E peek() { final Node<E> f = first; return (f == null) ? null : f.item; }
6.2.7 peekFirst()方法
// 作用：返回头元素，并且不删除。如果不存在也不错，返回null public E peekFirst() { final Node<E> f = first; return (f == null) ? null : f.item; }
6.2.8 peekLast()方法
// 作用：返回尾元素，如果为null,则就返回null public E peekLast() { final Node<E> l = last; return (l == null) ? null : l.item; }
6.2.9 poll()方法
// 作用：返回头节点元素，并删除头节点。并将下一个节点设为头节点。 public E poll() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); }
6.2.10 pollFirst()方法
// 作用：返回头节点，并删除头节点，并将下一个节点设为头节点。 public E pollFirst() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); }
6.2.11 pollLast()方法
// 作用：返回尾节点，并且将尾节点删除，并将尾节点的前一个节点置为尾节点 public E pollLast() { final Node<E> l = last; return (l == null) ? null : unlinkLast(l); }
6.2.12 pop()方法
// 作用：删除头节点，如果头结点为null.则抛出异常 public E pop() { return removeFirst(); } public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); }
6.2.13 push(E e)方法
// 作用：将元素添加到头部 public void push(E e) { addFirst(e); } public void addFirst(E e) { linkFirst(e); } private void linkFirst(E e) { final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; }
6.3 其他
6.3.1 removeFirstOccurrence(Object o)
//移除第一次出现的元素。（从前向后遍历集合） //底层调用remove（）方法，通过从前向后遍历集合。 public boolean removeFirstOccurrence(Object o) { return remove(o); }
6.3.2 removeLastOccurrence(Object o)
//移除第一次出现的元素。（从后向前遍历集合） 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; }
6.3.3 clone()
克隆方法：
首先获取从辅助方法返回的LinkedList对象，接着把该对象的所有域都设置为初始值。
然后把LinkedList中所有的内容复制到返回的对象中。
public Object clone() { LinkedList<E> 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<E> x = first; x != null; x = x.next) clone.add(x.item); return clone; }
克隆的辅助方法：
直接调用超类的clone（）方法，然后把得到的Object对象转换为LinkedList类型。
Object的clone（）方法是本地方法（通过native修饰）
6.3.4 toArray()
转化为数组：（没有参数）
通过遍历LinkedList中的每个节点，把值添加到数组中。
public Object[] toArray() { Object[] result = new Object[size]; int i = 0; for (Node<E> x = first; x != null; x = x.next) result[i++] = x.item; return result; }
6.3.5 toArray(T[`] a)
/** * 泛型方法 * 在方法内部，如果a的长度小于集合的大小的话， * 通过反射创建一个和集合同样大小的数组， * 接着把集合中的所有元素添加到数组中。 * 如果数组的元素的个数大于集合中元素的个数，则把a[size]设置 * 为空。 * 我估计代码设计者这样设计代码的目的是为了能够通过返回值观察到 * LinkedList集合中原来的元素有哪些。通过null把集合中的元素凸显出来。 * ArrayList中也有同样的考虑和设计。 * * @param a * @param <T> * @return */ public <T> 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<E> x = first; x != null; x = x.next) result[i++] = x.item; if (a.length > size) a[size] = null; return a; }
6.3.6 writeObject(java.io.ObjectOutputStream s)
将LinkedList写入到流中。（也就是把LinkedList状态保存到流中）（序列化）
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<E> x = first; x != null; x = x.next) s.writeObject(x.item); }
6.3.7 readObject(java.io.ObjectInputStream s)
从流中把LinkedList读取出来（读取流，拼装成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()); }
6.3.8 迭代器
①返回ListIterator迭代器：
public ListIterator<E> listIterator(int index) { checkPositionIndex(index); return new ListItr(index); } • 1 • 2 • 3 • 4
②返回Iterator迭代器：
public Iterator<E> descendingIterator() { return new DescendingIterator(); }
LinkedList的迭代器也是提供了两种，一种是指提供向后遍历的Iterator，另一种是List的专有迭代器ListIterator。
