接着上一篇文章的源码分析
取出元素
包括方法有：
- peek()
- peekFirst()
- peekLast()
- element()
- get(int index)
- getFirst()
- getLast()
- indexOf(Object o)
- lastIndexOf(Object o)
peek()
/** * 只是访问，但是不移除链表的头元素 */ public E peek() { final Node<E> f = first; return (f == null) ? null : f.item; }
peek() 源码比较简单，直接找到链表的第一个节点，判断是否为null，如果为null，返回null，否则返回链首的元素
peekFirst() ： 源码和peek() 相同
peekLast():
/** * 访问，但是不移除链表中的最后一个元素 * 或者返回null如果链表是空链表 */ public E peekLast() { final Node<E> l = last; return (l == null) ? null : l.item; }
源码也比较好理解
element() :
/** * 只是访问，但是不移除链表的第一个元素 */ public E element() { return getFirst(); } public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; }
与peek()相同的地方都是访问链表的第一个元素，不同是element元素在链表为null的时候会报空指针异常
get(int index) :
/* * 返回链表中指定位置的元素 */ public E get(int index) { checkElementIndex(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; } }
get(int index)源码也是比较好理解，首先对下标进行越界检查，没有越界的话直接找到索引位置对应的node节点，进行返回
getFirst() ：源码和element()相同
getLast(): 直接找到最后一个元素进行返回，和getFist几乎相同
indexOf(Object o) :
/* * 返回第一次出现指定元素的位置，或者-1如果不包含指定元素。 */ public int indexOf(Object o) { int index = 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; }
两种情况：
- 如果需要检索的元素是null，对元素链表进行遍历，返回x的元素为空的位置
- 如果需要检索的元素不是null，对元素的链表遍历，直到找到相同的元素，返回元素下标
lastIndexOf(Object o) :
/* * 返回最后一次出现指定元素的位置，或者-1如果不包含指定元素。 */ public int lastIndexOf(Object o) { int index = size; if (o == null) { for (Node<E> x = last; x != null; x = x.prev) { index--; 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; }
从IndexOf(Object o)源码反向理解
删除
删除节点的示意图如下：
包括的方法有：
- poll()
- pollFirst()
- pollLast()
- pop()
- remove()
- remove(int index)
- remove(Object o)
- removeFirst()
- removeFirstOccurrence(Object o)
- removeLast()
- removeLastOccurrence(Object o)
- clear()
poll() :
/* * 访问并移除链表中指定元素 */ public E poll() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(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; f.next = null; // help GC first = next; if (next == null) last = null; else next.prev = null; size--; modCount++; return element; }
poll()方法也比较简单直接，首先通过Node方法找到第一个链表头，然后把链表的元素和链表头指向的next元素置空，再把next节点的元素变为头节点的元素
pollFirst() : 与poll() 源码相同
pollLast(): 与poll() 源码很相似，不再解释
pop()
/* * 弹出链表的指定元素，换句话说，移除并返回链表中第一个元素 */ public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } // unlinkFirst 源码上面👆有
removeFirst源码就多了如果首部元素为null，就直接抛出异常的操作
remove(int index):
/* * 移除链表指定位置的元素 */ public E remove(int index) { checkElementIndex(index); // 找到index 的节点，断开指定节点 return unlink(node(index)); } // 断开指定节点 E unlink(Node<E> x) { // 找到链接节点的元素，next节点和prev节点 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; x.prev = null; } if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element; }
remove(Object o)
/* * 移除列表中第一次出现的指定元素，如果存在的话。如果列表不包含指定元素，则不会改变， * 更进一步来说，移除索引最小的元素，前提是(o == null ? get(i) == null : o.equals(get(i))) */ public boolean remove(Object o) { // 如果o为null if (o == null) { for (Node<E> x = first; x != null; x = x.next) { // 匹配null对象，删除控对象，返回true if (x.item == null) { unlink(x); return true; } } } else { // 如果不为null for (Node<E> x = first; x != null; x = x.next) { // 匹配对应节点，返回true if (o.equals(x.item)) { unlink(x); return true; } } } return false; }
removeFirst() 和remove() 源码相同
removeFirstOccurrence(Object o)和 remove(Object o) 源码相同
removeLast() 和 pollLast() 相同
removeLastOccurrence(Object o) 和 removeFirstOccurrence(Object o) 相似
clear()
/* * 清空所有元素 */ public void clear() { // 遍历元素，把元素的值置为null for (Node<E> x = first; x != null; ) { Node<E> next = x.next; x.item = null; x.next = null; x.prev = null; x = next; } first = last = null; size = 0; modCount++; }
clear()方法，先找到链表头，循环遍历每一项，把每一项的prev，item，next属性置空，最后再清除first和last节点，注意源码有一点，x = next ，这行代码是向后遍历的意思，根据next的元素再继续向后查找
其他方法
链表最常用的方法就是添加、查找、删除，下面来介绍一下其他的方法
clone()
/* * 链表复制 */ public Object clone() { // 此处的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; } private LinkedList<E> superClone() { try { return (LinkedList<E>) super.clone(); } catch (CloneNotSupportedException e) { throw new InternalError(e); } } // 本地方法 protected native Object clone() throws CloneN
clone() 方法调用superClone()能够获取拷贝过后的值，但是为什么要把first和last置为null，debug的时候就发现clone对象所有的值都为null了，而且为什么又要循环遍历链表再添加一遍？
contains(Object o) : 和index源码几乎相同
set(int index, E element)
/* * 在指定位置替换指定元素 */ public E set(int index, E element) { // 越界检查 checkElementIndex(index); // 找到索引元素所在的位置 Node<E> x = node(index); // 元素替换操作，返回替换之前的元素 E oldVal = x.item; x.item = element; return oldVal; }
descendingIterator()
public Iterator<E> descendingIterator() { return new DescendingIterator(); } private class DescendingIterator implements Iterator<E> { private final ListItr itr = new ListItr(size()); public boolean hasNext() { return itr.hasPrevious(); } public E next() { return itr.previous(); } public void remove() { itr.remove(); } }
descendingIterator 就相当于创建了一个倒置的Iterator，倒叙遍历
listIterator(int index) :
/* * 在指定位置上返回一个列表的迭代器，这个list-Iterator是有快速失败机制的 * 可以参见我的另一篇文章 ArrayList 源码解析 */ public ListIterator<E> listIterator(int index) { checkPositionIndex(index); return new ListItr(index); } // ListItr 是LinkedList的一个内部类 private class ListItr implements ListIterator<E> { // 上一个被返回的节点 private Node<E> lastReturned; // 下一个节点 private Node<E> next; // 下一个下标 private int nextIndex; // 期望的修改次数 = 修改次数，用于判断并发情况 private int expectedModCount = modCount; // 在指定位置创建一个迭代器 ListItr(int index) { next = (index == size) ? null : node(index); nextIndex = index; } // 判断是否有下一个元素 // 判断的标准是下一个索引的值 < size ,说明当前位置最大 = 链表的容量 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() { // 通过元素索引是否等于0，来判断是否达到开头。 return nextIndex > 0; } // 遍历之前的元素 public E previous() { checkForComodification(); if (!hasPrevious()) throw new NoSuchElementException(); // next指向链表的上一个元素 lastReturned = next = (next == null) ? last : next.prev; nextIndex--; return lastReturned.item; } // 下一个索引 public int nextIndex() { return nextIndex; } // 上一个索引 public int previousIndex() { return nextIndex - 1; } // 移除元素，有fail-fast机制 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++; } // 设置当前节点为e，有fail-fast机制 public void set(E e) { if (lastReturned == null) throw new IllegalStateException(); checkForComodification(); lastReturned.item = e; } // 将e添加到当前节点的前面，也有fail-fast机制 public void add(E e) { checkForComodification(); lastReturned = null; if (next == null) linkLast(e); else linkBefore(e, next); nextIndex++; expectedModCount++; } // jdk1.8引入，用于快速遍历链表元素 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(); } // 判断 “modCount和expectedModCount是否相等”，依次来实现fail-fast机制 final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }
toArray()
/* * 返回LinkedList的Object[]数组 */ public Object[] toArray() { Object[] result = new Object[size]; int i = 0; //将链表中所有节点的数据都添加到Object[]数组中 for (Node<E> x = first; x != null; x = x.next) result[i++] = x.item; return result; }
toArray(T[] a)
/* * 返回LinkedList的模板数组。所谓模板数组，即可以将T设为任意的数据类型 */ public <T> T[] toArray(T[] a) { // 若数组a的大小 < LinkedList的元素个数(意味着数组a不能容纳LinkedList中全部元素) // 则新建一个T[]数组，T[]的大小为LinkedList大小，并将该T[]赋值给a。 if (a.length < size) a = (T[])java.lang.reflect.Array.newInstance( a.getClass().getComponentType(), size); //将链表中所有节点的数据都添加到数组a中 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; }
