首页 > 代码库 > LinkedList源码分析
LinkedList源码分析
LinkedList的声明
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
基本和ArrayList一样，除了实现了Deque<E>接口以及没有实现RandomAccess接口。
Deque是double ended queue（双端队列）的缩写，表示LinkedList可以作为队列，栈，双向队列的实现。
而没有实现RandomAccess接口则是表明其无法通过索引来进行快速访问，即每次访问都要O(n)。
LinkedList的域
介绍域之前先介绍一个LinkedList关键的内部类Node
1 private static class Node<E> { 2 E item; 3 Node<E> next; 4 Node<E> prev; 5 6 Node(Node<E> prev, E element, Node<E> next) { 7 this.item = element; 8 this.next = next; 9 this.prev = prev; 10 } 11 }
Node表示一个节点，而LinkedList则是由一个个节点连接组成，一个节点内部保存着LinkedList要保存的对象和他前一个和后一个节点的引用。
1 transient int size = 0; 2 3 transient Node<E> first; 4 5 transient Node<E> last;
size表示LinkedList中所包含的节点个数，first保存着第一个节点的引用，last则是最后一个节点的引用。
注意到这三个域都是用了transient来修饰的，和ArrayList一样，LinkedList序列化也是调用了writeObject和readObject方法。
1 private void writeObject(java.io.ObjectOutputStream s) 2 throws java.io.IOException { 3 // Write out any hidden serialization magic 4 s.defaultWriteObject(); 5 6 // Write out size 7 s.writeInt(size); 8 9 // Write out all elements in the proper order. 10 for (Node<E> x = first; x != null; x = x.next) 11 s.writeObject(x.item); 12 } 13 14 private void readObject(java.io.ObjectInputStream s) 15 throws java.io.IOException, ClassNotFoundException { 16 // Read in any hidden serialization magic 17 s.defaultReadObject(); 18 19 // Read in size 20 int size = s.readInt(); 21 22 // Read in all elements in the proper order. 23 for (int i = 0; i < size; i++) 24 linkLast((E)s.readObject()); 25 } 26 27 void linkLast(E e) { 28 final Node<E> l = last; 29 final Node<E> newNode = new Node<>(l, e, null); 30 last = newNode; 31 if (l == null) 32 first = newNode; 33 else 34 l.next = newNode; 35 size++; 36 modCount++; 37 }
发现readObject中在循环读取节点的同时调用了linkLast函数，已经把head和last进行了赋值，具体的linkLast函数解析在下面会讲到。
而size在readObject中也起到重要作用，于是在writeObject中需要直接写入。
那三个域都在函数中赋值了，序列化的时候就可以不必重复序列化，提高了IO的效率，去除了冗杂度。
LinkedList的构造方法
1 public LinkedList() { 2 }
无参的构造方法，没有进行任何的操作，即域内所有值都是默认。
1 public LinkedList(Collection<? extends E> c) { 2 this(); 3 addAll(c); 4 }
带一个Collection型参数的构造方法，先调用了无参的构造方法，然后调用了addAll函数，这个函数在下面会讲到。
LinkedList比ArrayList的构造方法简单许多，因为他不依赖于数组，没有过多的操作。
所有的增加删除节点都会实时改变整个LinkedList，所以他的关键方法会相对而言更加复杂。
LinkedList的关键方法
1 public E get(int index) { 2 checkElementIndex(index); 3 return node(index).item; 4 } 5 6 Node<E> node(int index) { 7 // assert isElementIndex(index); 8 9 if (index < (size >> 1)) { 10 Node<E> x = first; 11 for (int i = 0; i < index; i++) 12 x = x.next; 13 return x; 14 } else { 15 Node<E> x = last; 16 for (int i = size - 1; i > index; i--) 17 x = x.prev; 18 return x; 19 } 20 }
在LinkedList中查找处于特定位置（index）不能和ArrayList一样直接利用数组索引访问，那就需要从其中一端往前（后）进行遍历。
源码实现了如果要访问的index小于size的一半，那就从first开始循环逐个访问其next，直到计数器（i从0开始递增）和index相同即为该节点。
否则就从last开始循环访问prev，直到计数器（i从size开始递减）和index相同。
node(int)是一个默认修饰符的方法，如果要从外界调用寻找特定索引的数值，需要调用get(int index)，其内部即用到了node，在这不再赘述。
1 public boolean add(E e) { 2 linkLast(e); 3 return true; 4 } 5 6 public void add(int index, E element) { 7 checkPositionIndex(index); 8 9 if (index == size) 10 linkLast(element); 11 else 12 linkBefore(element, node(index)); 13 } 14 15 void linkLast(E e) { 16 final Node<E> l = last; 17 final Node<E> newNode = new Node<>(l, e, null); 18 last = newNode; 19 if (l == null) 20 first = newNode; 21 else 22 l.next = newNode; 23 size++; 24 modCount++; 25 } 26 27 void linkBefore(E e, Node<E> succ) { 28 // assert succ != null; 29 final Node<E> pred = succ.prev; 30 final Node<E> newNode = new Node<>(pred, e, succ); 31 succ.prev = newNode; 32 if (pred == null) 33 first = newNode; 34 else 35 pred.next = newNode; 36 size++; 37 modCount++; 38 } 39 40 private void checkPositionIndex(int index) { 41 if (!isPositionIndex(index)) 42 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 43 } 44 45 private boolean isPositionIndex(int index) { 46 return index >= 0 && index <= size; 47 }
添加一个元素直接调用linkLast方法，字面解释就是链接到最后，
现将last赋值给临时变量l，然后用参数构建一个节点，把这个节点作为last新的引用，
接下来判断last是否为空（即LinkedList是否为空）,若为空，将first也设为这个节点，
若不为空则把原来的最后一个节点（临时变量l）的next设为last，然后将size加一，modCount加一。
若想在指定位置添加元素，先判断想要添加的位置是否合理，
然后如果添加的位置是最后一个，和直接添加元素相同，直接调用linkLast。
其他情况就是在第一个或者中间添加元素，这里调用了linkBefore函数，
用pred临时存放添加位置节点的前一个节点，然后新增一个节点，把其prev设为pred，next设为处于添加位置的那个节点。
在把添加位置的节点的prev设为新增节点。
再判断pred是否为空（添加节点的前一节点是否为空，即添加位置是否第一个位置），那么就将LinkedList的first设为新增节点。
否则（添加位置不是第一个位置），就把pred（原来添加位置的前一个节点）的next设为新增节点。
最后size加一，modCount加一。
1 public boolean addAll(Collection<? extends E> c) { 2 return addAll(size, c); 3 } 4 5 public boolean addAll(int index, Collection<? extends E> c) { 6 checkPositionIndex(index); 7 8 Object[] a = c.toArray(); 9 int numNew = a.length; 10 if (numNew == 0) 11 return false; 12 13 Node<E> pred, succ; 14 if (index == size) { 15 succ = null; 16 pred = last; 17 } else { 18 succ = node(index); 19 pred = succ.prev; 20 } 21 22 for (Object o : a) { 23 @SuppressWarnings("unchecked") E e = (E) o; 24 Node<E> newNode = new Node<>(pred, e, null); 25 if (pred == null) 26 first = newNode; 27 else 28 pred.next = newNode; 29 pred = newNode; 30 } 31 32 if (succ == null) { 33 last = pred; 34 } else { 35 pred.next = succ; 36 succ.prev = pred; 37 } 38 39 size += numNew; 40 modCount++; 41 return true; 42 }
添加一个集合内所有元素到LinkedList中，先用一个Object数组来存储要存放的所有数据，
然后构建两个Node引用，pred和succ。
如果要插入的位置是LinkedList的末尾，pred指向最后一个节点，succ指向null；
否则pred指向要插入位置的节点，succ指向要插入位置的下一个位置的节点。
然后循环遍历存放数据的Object数组，每一次循环生成一个新的节点newNode，
其prev为pred，数值为存放的数值，next为null。
判定prev是否为null，即要插入的位置是否为首位，如果是就修改first为newNode，不是就把pred.next修改为newNode，最后把pred的指向改为newNode。
这个循环构建了在index之后的一连串数据，但是没有把其和原来后面的数据所连接。
所以最后的操作就是要把插入位置之后的元素和插入的元素进行连接，这个连接只需要操作插入的最后一个元素和插入位置的下一个元素即可。
最后将size+numNew，modCount加一。
注意到这个函数返回的是一个boolean类型，若操作成功返回true否则返回false，而源码中的操作失败当且仅当要插入的数据量为空时成立。
1 public E remove(int index) { 2 checkElementIndex(index); 3 return unlink(node(index)); 4 } 5 6 public boolean remove(Object o) { 7 if (o == null) { 8 for (Node<E> x = first; x != null; x = x.next) { 9 if (x.item == null) { 10 unlink(x); 11 return true; 12 } 13 } 14 } else { 15 for (Node<E> x = first; x != null; x = x.next) { 16 if (o.equals(x.item)) { 17 unlink(x); 18 return true; 19 } 20 } 21 } 22 return false; 23 } 24 25 E unlink(Node<E> x) { 26 // assert x != null; 27 final E element = x.item; 28 final Node<E> next = x.next; 29 final Node<E> prev = x.prev; 30 31 if (prev == null) { 32 first = next; 33 } else { 34 prev.next = next; 35 x.prev = null; 36 } 37 38 if (next == null) { 39 last = prev; 40 } else { 41 next.prev = prev; 42 x.next = null; 43 } 44 45 x.item = null; 46 size--; 47 modCount++; 48 return element; 49 }
删除元素的核心代码是unlink方法，先增加next和prev两个引用来保存删除节点的前一个和后一个节点，
然后判断这个节点是否为第一个，如果是就把first置为空，不是就prev.next改为刚刚保存的next，x.next置为空。
然后判断这个节点是否为最后一个，操作和上类似。
最后把该节点置为null，让GC处理，size减一，modCount加一。
remove(Object o)方法从头遍历直至找到相等的元素，判断是否和传入参数相等，第一个相等的就调用unlink。
而remove(int index)则是直接用node(index)找到然后unlink。
1 public void clear() { 2 // Clearing all of the links between nodes is "unnecessary", but: 3 // - helps a generational GC if the discarded nodes inhabit 4 // more than one generation 5 // - is sure to free memory even if there is a reachable Iterator 6 for (Node<E> x = first; x != null; ) { 7 Node<E> next = x.next; 8 x.item = null; 9 x.next = null; 10 x.prev = null; 11 x = next; 12 } 13 first = last = null; 14 size = 0; 15 modCount++; 16 }
clear方法循环遍历节点然后把节点内的所有值置为null。
JDK注释写道： 将所有相互的引用清空“不是必要的”，但是会方便分代GC收集，
第一是因为如果有节点是在年老代的，而且节点是互相引用的，那GC就不会回收任何节点直到触发一次FULL GC，这样效率较低。
第二是因为有可能有别的（例如一个Iterator）会引用某一节点，那么直到Iterator不消除索引，LinkedList都不能被回收，这不是我们期待的清空。
所以会把引用全部切断置为空，保证GC的效率。
LinkedList的迭代器
ListIterator的声明和域
1 private class ListItr implements ListIterator<E> { 2 private Node<E> lastReturned; 3 private Node<E> next; 4 private int nextIndex; 5 private int expectedModCount = modCount;
lastReturned表示上一个返回的元素，next表示下一个将要返回的元素，
nextIndex记录下一个的索引，expectedModCount记录期望的modCount。
1 public boolean hasNext() { 2 return nextIndex < size; 3 } 4 5 public E next() { 6 checkForComodification(); 7 if (!hasNext()) 8 throw new NoSuchElementException(); 9 10 lastReturned = next; 11 next = next.next; 12 nextIndex++; 13 return lastReturned.item; 14 } 15 16 public boolean hasPrevious() { 17 return nextIndex > 0; 18 } 19 20 public E previous() { 21 checkForComodification(); 22 if (!hasPrevious()) 23 throw new NoSuchElementException(); 24 25 lastReturned = next = (next == null) ? last : next.prev; 26 nextIndex--; 27 return lastReturned.item; 28 } 29 30 public void remove() { 31 checkForComodification(); 32 if (lastReturned == null) 33 throw new IllegalStateException(); 34 35 Node<E> lastNext = lastReturned.next; 36 unlink(lastReturned); 37 if (next == lastReturned) 38 next = lastNext; 39 else 40 nextIndex--; 41 lastReturned = null; 42 expectedModCount++; 43 }
hasNext方法将nextIndex和last比较，若没有达到last即表示没有到末尾，返回true，否则返回false。
next方法将lastReturned和next和nextIndex都往后移一个，然后返回lastReturned.item即可。
previous方法将lastReturned和next都设为last（最后一个时）或next.prev，然后返回lastReturned.item。
remove方法先用lastNext保存lastReturned的下一个元素，因为上一个操作不确定是next还是previous，
所以在unlink元素之后需要判断，当next==lastReturned时表示上一次调用的是previous，就要重新把next设为刚刚保存的lastNext。
否则就直接把nextIndex减一，而不用对next进行更多操作（next仍是物理位置的下一个元素）。
LinkedList源码分析