用java源代码学数据结构<四>: LinkedList 详解
在数据结构中有基本数据类型：线性表。线性表又可以分为顺序表（数组表）和链表。java中典型顺序表有Vector和ArrayList，链表类就是LinkedList。
个人体会：
1.要想gc（垃圾回收器）回收对象，普通的对象只需要设置为null即可，而复合型对象（如Node）,它包含两个指针对象和一个元素，必须全部设置为Null才能回收
2.在链表节点进行prev、next等操作时，需要注意空指针异常。对此需要相应的作出判断（例如直接设置为first或last对象等）
3.强烈推荐仔细分析下LinkedList中的ListItr迭代器（特别是针对它的previous和next两种访问方式）
package java.util;/*1.LinkedList是一个双向链表，允许包含null元素2.LinkedList是线程不同步的。多线程结构化修改（增加或删除若干个元素，不包括设置元素值）可能造成意想不到的结果3.可以使用同步对象来封装LinkedList类。也可以在开始对象时使用 List list = Collections.synchronizedList(new LinkedList(...))*/public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{/*典型的双向链表节点类，每个节点有数据，前指针（java中就是对象），后指针*/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; } }/*transient1.为了在一个特定对象的一个域上关闭serialization， 可以在这个域前加上关键字transient。2.当一个对象被序列化的时候，transient型变量的值不包括在序列化的表示中， 然而非transient型的变量是被包括进去的。3.size表示链表的元素数目*/ transient int size = 0;//链表头指针 transient Node<E> first;//链表尾指针transient Node<E> last;public LinkedList() { }//集合构造函数public LinkedList(Collection<? extends E> c) { this(); addAll(c); }//将e对象设置到链表头private void linkFirst(E e) { final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f);//重新设置first指针 first = newNode; if (f == null) last = newNode; else//如果原来的first不为空，就将原来的first(即f)接到新的first(newNodw)的后面 f.prev = newNode; size++; modCount++; }//将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; else//如果原来的last不为空，就将新的last(即newNode)接到原来的last(l)的后面 l.next = newNode; size++; modCount++; }//在非空节点succ之前插入对象evoid 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++; }//删除头结点fprivate 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; }//删除尾部节点lprivate 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; }//删除指点节点xE 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;//将节点x的前节点设置为null x.prev = null; } if (next == null) { last = prev; } else { next.prev = prev;//将节点x的后节点设置为null x.next = null; }//x的prev、item、next都为Null,gc就可以回收了 x.item = null; size--; modCount++; return element; }//返回链表头节点中存储的对象public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; }//返回链表尾节点中的对象public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; }//删除头结点，并返回节点中的对象public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); }//删除尾结点，并返回节点中的对象public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); }public void addFirst(E e) { linkFirst(e); }public void addLast(E e) { linkLast(e); }public boolean contains(Object o) { return indexOf(o) != -1; }public int size() { return size; }//默认的add是向链表末尾增加元素public boolean add(E e) { linkLast(e); return true; }//删除指定元素public boolean remove(Object o) {//对于o是否null进行两种比较 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; }public boolean addAll(Collection<? extends E> c) { return addAll(size, c); }public boolean addAll(int index, Collection<? extends E> c) { //index参数检查checkPositionIndex(index); Object[] a = c.toArray(); int numNew = a.length; if (numNew == 0) return false; Node<E> pred, succ;//如果是在链表末尾插入，将pred设置为last if (index == size) { succ = null; pred = last; } else {//否则使用succ暂时保存插入位置后面的一个节点 succ = node(index); pred = succ.prev; } for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o;//迭代插入 Node<E> newNode = new Node<>(pred, e, 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; }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; ) { Node<E> next = x.next;//将节点设置为全null,然后由gc回收 x.item = null; x.next = null; x.prev = null; x = next; } first = last = null; size = 0; modCount++; }public E get(int index) { checkElementIndex(index); return node(index).item; }//将此列表中指定位置的元素替换为指定的元素。返回旧的元素public E set(int index, E element) { checkElementIndex(index); Node<E> x = node(index); E oldVal = x.item; x.item = element; return oldVal; }//在此列表中指定的位置插入指定的元素。public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); }public E remove(int index) { checkElementIndex(index); return unlink(node(index)); }//元素有效位置参数判断private boolean isElementIndex(int index) { return index >= 0 && index < size; }//index==size，表示从结尾开始private boolean isPositionIndex(int index) { return index >= 0 && index <= size; }private String outOfBoundsMsg(int index) { 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)); }//返回指定位置的node对象Node<E> node(int index) { // assert isElementIndex(index);//看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; } }public int indexOf(Object o) {//对o为null或其他对象，使用==或equals方法 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; }//反向查找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; }//获取但不移除此列表的头（第一个元素）。public E peek() { final Node<E> f = first; return (f == null) ? null : f.item;//防止空指针异常 }// 获取但不移除此列表的头（第一个元素）。public E element() { return getFirst(); }//获取并"移除"此列表的头（第一个元素）public E poll() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); }//获取并"移除"此列表的头（第一个元素）。public E remove() { return removeFirst(); }//将指定元素添加到此列表的末尾（最后一个元素）。public boolean offer(E e) { return add(e); }//在此列表的开头插入指定的元素。public boolean offerFirst(E e) { addFirst(e); return true; }//在此列表末尾插入指定的元素public boolean offerLast(E e) { addLast(e); return true; }// 获取但不移除此列表的第一个元素；如果此列表为空，则返回 null。// 感觉跟peek一样public E peekFirst() { final Node<E> f = first; return (f == null) ? null : f.item; } //获取但不移除此列表的最后一个元素；如果此列表为空，则返回 null。 public E peekLast() { final Node<E> l = last; return (l == null) ? null : l.item; }// 获取并移除此列表的第一个元素；如果此列表为空，则返回 null。public E pollFirst() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); }//获取并移除此列表的最后一个元素；如果此列表为空，则返回 null。public E pollLast() { final Node<E> l = last; return (l == null) ? null : unlinkLast(l); }//将e对象加到头部public void push(E e) { addFirst(e); }public E pop() { return removeFirst(); }public boolean removeFirstOccurrence(Object o) { return remove(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; }public ListIterator<E> listIterator(int index) { checkPositionIndex(index); return new ListItr(index); }private class ListItr implements ListIterator<E> { //类似于Vector中的lastRet,用于remove，表示上次迭代（不分next，preivous）返回的对象private Node<E> lastReturned = null; 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();//保存next的节点信息, lastReturned = next; next = next.next; nextIndex++; return lastReturned.item; } public boolean hasPrevious() { return nextIndex > 0; }//同next public E previous() { checkForComodification(); if (!hasPrevious()) throw new NoSuchElementException(); lastReturned = next = (next == null) ? last : next.prev; nextIndex--; return lastReturned.item; } public int nextIndex() { return nextIndex; } public int previousIndex() { return nextIndex - 1; } public void remove() { checkForComodification();//必须先调用itr.next或itr.previous之后才能调用remove和set if (lastReturned == null) throw new IllegalStateException(); Node<E> lastNext = lastReturned.next;//unlink将lastReturned设置为null,同时将lastReturned前后节点连在一起 unlink(lastReturned);/* 调用itr.next()后，lastReturned位于next的前面一个 调用itr.previous()后，lastReturned与next在同一位置*/ if (next == lastReturned)/*1.在previous()中有这样一句lastReturned = next = (next == null) ? last : next.prev;最后return lastReturned.item; 2.如果调用的是itr.previous，则下一次previous要求返回这次previous之前 的那个元素，而此时next和lastReturned都为null,但unlink将lastReturned 的前后节点连在了一起，我们就需要将next设置为当前lastReturned的后面 一个节点，即next = lastNext; */ next = lastNext;//3.因为是向前访问，而删除的元素在next的后面，所以不修改nextIndex else/*同理，如果调用的是next(),则lastReturned在next的前面一个位置，删除了lastReturned所指的对象，没必修改next了*/ nextIndex--;//删除的元素在next的前面 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++; }//检查线程同步 final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }//返回反向迭代器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(); } } @SuppressWarnings("unchecked") private LinkedList<E> superClone() { try { return (LinkedList<E>) super.clone(); } catch (CloneNotSupportedException e) { throw new InternalError(); } }//拷贝复制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; }//一个个的读取，一个个的存储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; }@SuppressWarnings("unchecked") 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; } private static final long serialVersionUID = 876323262645176354L;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); }@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()); }