第四章 JAVA集合之LinkedList源码浅析

       一.概括

      在JDK1.7中LinkedList是一种双链表结构，而不是一种循环双链表结构，LinkedList这种结构适合用来存储增删操作比较多的集合，因为在增删的时候不需要移动元素，只需要改变元素的连接指针就可以了，如果是查询操作比较多的时候，用ArrayList存储比较合适。LinkedList不是线程安全的。

       二.LinkedList的数据结构       

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable可以看到LinkedList继承了AbstractSequentialList接口，AbstractSequentialList接口中有对set,add等方法的实现，但是LinkedList对这些方法进行了重写。LimkedList还实现了Deque接口，Deque接口是一个队列接口，该接口定义了在队列前后操作的方法，例如：void addFirst(E e);void addLast(E e);等方法。

        LinkedList存储元素的基本单元Node<E>       

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; } }       可以看出Node有一个属性用来存储值，还有一个属性是前指针，指向相邻的前一个元素，另一个属性是后指针，指向相邻的后一个元素。当向LinkedList存储元素的时候，这些元素都是封装在一个个Node<E>对象的里面，再由多个Node<E>对象前后相连构造成为一个LinkedList；这个很容易联想到HashMap的基本数据结构Entry，当了解了LinkedList的基本数据机构后，就比较好理解LinkedList的其他操作了。

    

/** *开始指针，指向LinkdList第一个元素 */ transient Node<E> first; /** * 结束指针，指向LinkedList的最后一个元素 */ transient Node<E> last;     在LinkedList中还有这样两个元素,分别指向LinkedList的第一个后最后一个元素，这两个指针将在对LinkdList进行操作的时候被用到。

     LinkedList的构造方法

    

//空构造方法，就是生成一个LinkedList对象 public LinkedList() { } /** * 带有集合参数的构造方法，将会把集合添加到LinkedList中 */ public LinkedList(Collection<? extends E> c) { this(); addAll(c); } public boolean addAll(Collection<? extends E> c) { return addAll(size, c); } //index代表集合c将要被放在LinkedList的位置 public boolean addAll(int index, Collection<? extends E> c) { //判断index是否大于等于0并且小于等于size;如果不满足将被抛出异常 checkPositionIndex(index); Object[] a = c.toArray(); int numNew = a.length; //集合大小为0，直接返回 if (numNew == 0) return false; //pred可以看成是指向集合c的第一个元素的指针， //succ可以看成是指向集合c的最后一个元素的指针 Node<E> pred, succ; //将集合c放在LinkedList的最后面 if (index == size) { succ = null; //pred指向LinkedList的最后一个元素 pred = last; } else { //succ指向LinkedList的第index个元素 succ = node(index); //pred指向第index个元素的前一个元素 pred = succ.prev; } //将数组a中的元素封装在Node里面，并连接起来 for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; //newNode的前指针指向newNode Node<E> newNode = new Node<>(pred, e, null); //说明集合是被放在LinkedList的最前面的 if (pred == null) first = newNode; else //让pred的后指针也指向newNode pred.next = newNode; //相当于指针前移一位 pred = newNode; } /* *如果集合是被放在LinkedList的最后面， *那么LinkedList的结束指针指向集合的最后一个元素就好了 */ if (succ == null) { last = pred; } else { //集合的最后一个元素的下一个指针指向原来LinkedList的第index个元素 pred.next = succ; //原来LinkedList的第index个元素的前指针指向集合的最后一个元素 succ.prev = pred; } //LinkedList新的长度等于以前的长度加上集合的长度 size += numNew; //LinkedList被改动一次就加一 modCount++; return true; }       从带有集合的构造方法中可以看出LinkedList在添加元素的时候主要是设置每一个元素的前后指针，让前后指针指向对的元素，也让其他元素的前后指针指向自己。

       

       三.LinkedList中的一些方法

       1.LinkedList的一些内部基本方法

       

/** * 向LinkedList的链表头添加一个元素 */ private void linkFirst(E e) { //记录LinkedList的头指针所指向的最开始的元素 final Node<E> f = first; //让要添加的元素的后指针指向头指针 final Node<E> newNode = new Node<>(null, e, f); //LinkedList的头指针指向新的添加的元素 first = newNode; /* *如果头指针为空,说明LinkedList一开始是为空 *那么现在添加了一个元素，LinkedList只有一个元素， *头尾指针指向同一个元素 */ if (f == null) last = newNode; else //原LinkedList的第一个元素的前指针指向先添加的元素, //这样就newNode变成第一个元素，原来的第一个元素变为了第二个元素 f.prev = newNode; //LinkedList大小加一 size++; modCount++; } /** * 在LinkedList的最后面添加一个元素 */ void linkLast(E e) { //记录LinkedList的尾指针锁指向的最后一个元素 final Node<E> l = last; //构造新添加的元素，并且让新元素的前指针指向LinkedList的尾指针 final Node<E> newNode = new Node<>(l, e, null); //尾指针从新指向新的元素，所以新的元素是在LinkedList最末端的 last = newNode; /* *如果尾指针为空,说明LinkedList一开始是为空 *那么现在添加了一个元素，LinkedList只有一个元素， *头尾指针指向同一个元素 */ if (l == null) first = newNode; else //原先LinkedList的最后一个元素的后指针指向新添加元素 l.next = newNode; //LinkedList大小加一 size++; modCount++; } /** * 将元素e添加在元素succ之前 */ void linkBefore(E e, Node<E> succ) { // 记录succ前指针所指向的元素 final Node<E> pred = succ.prev; //新添加元素的前指针指向的是pred,后指针指向的是succ final Node<E> newNode = new Node<>(pred, e, succ); //succ的前指针指向newNode succ.prev = newNode; //如果pred为空，说明是在链表头添加元素，LinkedList的头指针指向先添加的元素 if (pred == null) first = newNode; else //pred的后指针指向newNode pred.next = newNode; size++; modCount++; } /** * 删除第一个元素 */ private E unlinkFirst(Node<E> f) { // 记录第一个元素的值 final E element = f.item; //记录第一个元素的下一个元素 final Node<E> next = f.next; f.item = null; f.next = null; // help GC //LinkedList的头指针指向了原先的第二个元素 first = next; //如果第二个元素为空 if (next == null) //尾指针也应该为空 last = null; else //现在LinkedList的第一个元素的的前指针设置为空 next.prev = null; //大小减一 size--; modCount++; return element; } /** * 删除最后一个元素 */ 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; } /** * 删除一个元素，这个元素是LinkedList中的任意元素 */ 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; //如果前一个元素为空，说明删除的是LinedList的头元素 //那么LinkedList的头指针就指向现在的第二个元素 if (prev == null) { first = next; } else { //前元素的后指针指向后元素 prev.next = next; x.prev = null; } //如果后一个元素为空，说明删除的是LinedList的尾元素 //那么LinkedList的头指针就指向现在的倒数第二个元素 if (next == null) { last = prev; } else { //后元素的前指针指向前元素 next.prev = prev; x.next = null; } //最后将x的item设为null x.item = null; size--; modCount++; return element; } 这些方法是供其他方法来调用的，所以知道了这些方法后，也就知道LinekdList提供给外部使用的方法的内部是怎么在操作。

       LinkedList的一些常用方法       

/** * 获取LinkedList的第一个元素 * */ public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; } /** * 获取LinkedList的最后一个元素 */ 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); } /** * 在在LinkedList头部添加一个元素 */ public void addFirst(E e) { linkFirst(e); } /** * 在LinkedList尾添加元素 */ public void addLast(E e) { linkLast(e); } /** * 链表是否包含某一个元素 */ public boolean contains(Object o) { return indexOf(o) != -1; } /** * 求LinkedList的大小 */ public int size() { return size; } /** * 向LinkedList里面添加元素，默认是添加在最后面的 * */ public boolean add(E e) { linkLast(e); return true; } /** *根据值来移除某一个元素，如果LinkedList里面有这个值 *则移除并返回true，如果没有这个值则返回false */ 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; } /** * 将所有元素移除，将LinkedList变为null */ public void clear() { 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++; } // Positional Access Operations /** * 根据下标获取元素 */ public E get(int index) { checkElementIndex(index); return node(index).item; } /** * 替换下标为index的元素的值 */ public E set(int index, E element) { checkElementIndex(index); Node<E> x = node(index); E oldVal = x.item; x.item = element; return oldVal; } /** *将元素element添加到下标为index的位置 */ public void add(int index, E element) { checkPositionIndex(index); //如果下标等于size,说明是将元素添加在LinkedList的最后面 if (index == size) linkLast(element); else linkBefore(element, node(index)); } /** * 按下标移除元素 */ public E remove(int index) { checkElementIndex(index); return unlink(node(index)); }

 

由于LinkedList实现了Quee接口，所以可以将LinkedList作为队列，LinkedList作为队列来使用的一些方法

/** * 获取到队列的第一个元素值 */ public E peek() { final Node<E> f = first; return (f == null) ? null : f.item; } /** * 获取队列的第一个元素指，当队列为空的时候，抛出NoSuchElementException异常 */ public E element() { return getFirst(); } /** * 获取队列的第一个元素指,并移除第一个元素 */ public E poll() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); } /** * 移除队列第一个元素，如果队列为空，将抛出NoSuchElementException异常 */ public E remove() { return removeFirst(); } /** * 在队列尾部添加元素 */ public boolean offer(E e) { return add(e); } // Deque operations /** * 在队列头添加一个元素 */ public boolean offerFirst(E e) { addFirst(e); return true; } /** * 在队列尾部添加一个元素 */ public boolean offerLast(E e) { addLast(e); return true; } /** * 返回第一个元素 */ public E peekFirst() { final Node<E> f = first; return (f == null) ? null : f.item; } /** * 返回最后一个元素 */ public E peekLast() { final Node<E> l = last; return (l == null) ? null : l.item; } /** * 返回第一个元素，并移除第一个元素 */ public E pollFirst() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); } /** * 返回最后一个元素并移除最后一个元素 */ public E pollLast() { final Node<E> l = last; return (l == null) ? null : unlinkLast(l); } /** * 向队列头添加一个元素 */ public void push(E e) { addFirst(e); } /** * 移除第一个元素,并返回元素 */ public E pop() { return removeFirst(); } /** * 从队列头开始，移除第一个为o的元素 * */ public boolean removeFirstOccurrence(Object o) { return remove(o); } /** * 从队尾开始，移除从队尾开始的第一个为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; }       队列中要用的几个方法总结一下

       E peek()                    返回队列的第一个元素

       E poll()                      返回队列的第一个元素并移除第一个元素

       E remove()               返回队列的第一个元素并移除第一个元素

       boolean offer(E e)   向队列的尾部添加一个元素

       void push(E e)         向队列的头部添加一个元素

       E pop()                     返回队列的第一个元素并移除第一个元素

LinkedList的迭代方法和迭代器

/** *LinkedList迭代方法,参数index是表明从下标index的位置开始迭代 * */ public ListIterator<E> listIterator(int index) { checkPositionIndex(index); return new ListItr(index); } /** *LinkedList迭代器 * */ private class ListItr implements ListIterator<E> { // 最近一次返回的节点，也是当前持有的节点 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(); 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() { return nextIndex; } public int previousIndex() { return nextIndex - 1; } //移除当前lastReturned指针指向的元素 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 //添加在next指针所指向的元素之前 linkBefore(e, next); nextIndex++; expectedModCount++; } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } } 举个例子

LinkedList<String> list = new LinkedList<String>(); list.add("First"); list.add("Second"); list.add("Thrid"); System.out.println(list); ListIterator<String> itr = list.listIterator(); while (itr.hasNext()) { System.out.println(itr.next()); } }