java源码阅读方法 java源码分析之LinkedList

java源码分析之LinkedList  

    LinkedList也和ArrayList一样实现了List接口 但是它执行插入和删除操作时比ArrayList更加高效 因为它是基于链表的 基于链表也决定了它在随机访问方面要比ArrayList逊色一点       除此之外 LinkedList还提供了一些可以使其作为栈 队列 双端队列的方法 这些方法中有些彼此之间只是名称的区别 以使得这些名字在特定的上下文中显得更加的合适   先看LinkedList类的定义   public class LinkedList<E>     extends AbstractSequentialList<E>     implements List<E> Deque<E> Cloneable java io Serializable     LinkedList继承自AbstractSequenceList 实现了List及Deque接口 其实AbstractSequenceList已经实现了List接口 这里标注出List只是更加清晰而已 AbstractSequenceList提供了List接口骨干性的实现以减少实现List接口的复杂度 Deque接口定义了双端队列的操作   LinkedList中之定义了两个属性   private transient Entry<E> header = new Entry<E>(null null null); private transient int size = ;     size肯定就是LinkedList对象里面存储的元素个数了 LinkedList既然是基于链表实现的 那么这个header肯定就是链表的头结点了 Entry就是节点对象了 一下是Entry类的代码       private static class Entry<E> {       E element;       Entry<E> next;       Entry<E> previous;           Entry(E element Entry<E> next Entry<E> previous) {           this element = element;           this next = next;           this previous = previous;     } }       只定义了存储的元素 前一个元素 后一个元素 这就是双向链表的节点的定义 每个节点只知道自己的前一个节点和后一个节点   来看LinkedList的构造方法     public LinkedList() {     header next = header previous = header; } public LinkedList(Collection<? extends E> c) {     this();     addAll(c); }

        LinkedList提供了两个构造方法 第一个构造方法不接受参数 只是将header节点的前一节点和后一节点都设置为自身（注意 这个是一个双向循环链表 如果不是循环链表 空链表的情况应该是header节点的前一节点和后一节点均为null） 这样整个链表其实就只有header一个节点 用于表示一个空的链表 第二个构造方法接收一个Collection参数c 调用第一个构造方法构造一个空的链表 之后通过addAll将c中的元素全部添加到链表中 来看addAll的内容       public boolean addAll(Collection<? extends E> c) {       return addAll(size c);   }   // index参数指定collection中插入的第一个元素的位置   public boolean addAll(int index Collection<? extends E> c) {       // 插入位置超过了链表的长度或小于 报IndexOutOfBoundsException异常       if (index < || index > size)           throw new IndexOutOfBoundsException( Index: +index+                                                   Size: +size);     Object[] a = c toArray(); int numNew = a length; // 若需要插入的节点个数为 则返回false 表示没有插入元素     if (numNew== )         return false;     modCount++;     // 保存index处的节点 插入位置如果是size 则在头结点前面插入 否则获取index处的节点 Entry<E> successor = (index==size ? header : entry(index)); // 获取前一个节点 插入时需要修改这个节点的next引用 Entry<E> predecessor = successor previous; // 按顺序将a数组中的第一个元素插入到index处 将之后的元素插在这个元素后面     for (int i= ; i<numNew; i++) { // 结合Entry的构造方法 这条语句是插入操作 相当于C语言中链表中插入节点并修改指针         Entry<E> e = new Entry<E>((E)a[i] successor predecessor);         // 插入节点后将前一节点的next指向当前节点 相当于修改前一节点的next指针         predecessor next = e;         // 相当于C语言中成功插入元素后将指针向后移动一个位置以实现循环的功能         predecessor = e; } // 插入元素前index处的元素链接到插入的Collection的最后一个节点 successor previous = predecessor; // 修改size     size += numNew;     return true; }       构造方法中的调用了addAll(Collection<? extends E> c)方法 而在addAll(Collection<? extends E> c)方法中仅仅是将size当做index参数调用了addAll(int index Collection<? extends E> c)方法       private Entry<E> entry(int index) {           if (index < || index >= size)               throw new IndexOutOfBoundsException( Index: +index+                                                   Size: +size);           Entry<E> e = header;           // 根据这个判断决定从哪个方向遍历这个链表           if (index < (size >> )) {               for (int i = ; i <= index; i++)                   e = e next;         } else {             // 可以通过header节点向前遍历 说明这个一个循环双向链表 header的previous指向链表的最后一个节点 这也验证了构造方法中对于header节点的前后节点均指向自己的解释             for (int i = size; i > index; i )                 e = e previous;         }         return e;     }       结合上面代码中的注释及双向循环链表的知识 应该很容易理解LinkedList构造方法所涉及的内容 下面开始分析LinkedList的其他方法       add(E e)   public boolean add(E e) {     addBefore(e header);     return true; }     从上面的代码可以看出 add(E e)方法只是调用了addBefore(E e Entry<E> entry)方法 并且返回true       addBefore(E e Entry<E> entry)     private Entry<E> addBefore(E e Entry<E> entry) {     Entry<E> newEntry = new Entry<E>(e entry entry previous);     newEntry previous next = newEntry;     newEntry next previous = newEntry;     size++;     modCount++;     return newEntry; }       addBefore(E e Entry<E> entry)方法是个私有方法 所以无法在外部程序中调用（当然 这是一般情况 你可以通过反射上面的还是能调用到的）       addBefore(E e Entry<E> entry)先通过Entry的构造方法创建e的节点newEntry（包含了将其下一个节点设置为entry 上一个节点设置为entry previous的操作 相当于修改newEntry的 指针 ） 之后修改插入位置后newEntry的前一节点的next引用和后一节点的previous引用 使链表节点间的引用关系保持正确 之后修改和size大小和记录modCount 然后返回新插入的节点       总结 addBefore(E e Entry<E> entry)实现在entry之前插入由e构造的新节点 而add(E e)实现在header节点之前插入由e构造的新节点       add(int index E e)   public void add(int index E element) {     addBefore(element (index==size ? header : entry(index))); }     也是调用了addBefore(E e Entry<E> entry)方法 只是entry节点由index的值决定

        构造方法 addAll(Collection<? extends E> c) add(E e) addBefor(E e Entry<E> entry)方法可以构造链表并在指定位置插入节点 为了便于理解 下面给出插入节点的示意图           addFirst(E e)   public void addFirst(E e) {     addBefore(e header next); }     addLast(E e)   public void addLast(E e) {     addBefore(e header); }     看上面的示意图 结合addBefore(E e Entry<E> entry)方法 很容易理解addFrist(E e)只需实现在header元素的下一个元素之前插入 即示意图中的一号之前 addLast(E e)只需在实现在header节点前（因为是循环链表 所以header的前一个节点就是链表的最后一个节点）插入节点（插入后在 号节点之后）       clear()       public void clear() {   Entry<E> e = header next;   // e可以理解为一个移动的 指针 因为是循环链表 所以回到header的时候说明已经没有节点了   while (e != header) {       // 保留e的下一个节点的引用           Entry<E> next = e next;           // 接触节点e对前后节点的引用           e next = e previous = null;           // 将节点e的内容置空         e element = null;         // 将e移动到下一个节点         e = next; } // 将header构造成一个循环链表 同构造方法构造一个空的LinkedList header next = header previous = header; // 修改size     size = ;     modCount++; }       上面代码中的注释已经足以解释这段代码的逻辑 需要注意的是提到的 指针 仅仅是概念上的类比 Java并不存在 指针 的概念 而只有引用 为了便于理解所以部分说明使用了 指针       contains(Object o)   public boolean contains(Object o) {     return indexOf(o) != ; }     仅仅只是判断o在链表中的索引 先看indexOf(Object o)方法       public int indexOf(Object o) {       int index = ;       if (o==null) {           for (Entry e = header next; e != header; e = e next) {               if (e element==null)                   return index;               index++;           }       } else {         for (Entry e = header next; e != header; e = e next) {             if (o equals(e element))                 return index;             index++;         }     }     return ; }       indexOf(Object o)判断o链表中是否存在节点的element和o相等 若相等则返回该节点在链表中的索引位置 若不存在则放回

        contains(Object o)方法通过判断indexOf(Object o)方法返回的值是否是 来判断链表中是否包含对象o       element()   public E element() {     return getFirst(); }     getFirst()   public E getFirst() {     if (size== )         throw new NoSuchElementException();     return header next element; }     element()方法调用了getFirst()返回链表的第一个节点的元素 为什么要提供功能一样的两个方法 像是包装了一下名字？其实这只是为了在不同的上下文 语境 中能通过更贴切的方法名调用罢了       get(int index)   public E get(int index) {     return entry(index) element; }     get(int index)方法用于获得指定索引位置的节点的元素 它通过entry(int index)方法获取节点 entry(int index)方法遍历链表并获取节点 在上面有说明过 不再陈述       set(int index E element)   public E set(int index E element) {     Entry<E> e = entry(index);     E oldVal = e element;     e element = element;     return oldVal; }     先获取指定索引的节点 之后保留原来的元素 然后用element进行替换 之后返回原来的元素       getLast()   public E getLast()  {     if (size== )         throw new NoSuchElementException();     return header previous element; }     getLast()方法和getFirst()方法类似 只是获取的是header节点的前一个节点的元素 因为是循环链表 所以header节点的前一节点就是链表的最后一个节点       lastIndexOf(Object o)       public int lastIndexOf(Object o) {       int index = size;       if (o==null) {           for (Entry e = header previous; e != header; e = e previous) {               index ;               if (e element==null)                   return index;           }       } else {         for (Entry e = header previous; e != header; e = e previous) {             index ;             if (o equals(e element))                 return index;         }     }     return ; }       因为查找的是last index 即最后一次出现的位置 所以采用由后向前的遍历方式 因为采用了有后向前的遍历 所以index被赋值为size 并且循环体内执行时都进行减操作 分两种情况判断是否存在 分别是null和不为空       offer(E e)   public boolean offer(E e) {     return add(e); }     在链表尾部插入元素       offerFirst(E e)   public boolean offerFirst(E e) {     addFirst(e);     return true; }     在链表开头插入元素       offerLast(E e)   public boolean offerLast(E e) {     addLast(e);     return true; }     在链表末尾插入元素       上面这三个方法都只是调用了相应的add方法 同样只是提供了不同的方法名在不同的语境下使用       peek()   public E peek() {     if (size== )         return null;     return getFirst(); }     peekFirst()   public E peekFirst() {     if (size== )         return null;     return getFirst(); }     peekLast()   public E peekLast() {     if (size== )         return null;     return getLast(); }     上面的三个方法也很简单 只是调用了对应的get方法       poll()   public E poll() {     if (size== )         return null;     return removeFirst(); }     pollFirst()   public E pollFirst() {     if (size== )         return null;     return removeFirst(); }     pollLast()   public E pollLast() {     if (size== )         return null;     return removeLast(); }     poll相关的方法都是获取并移除某个元素 都是和remove操作相关       pop()   public E pop() {     return removeFirst(); }     push(E e)   public void push(E e) {     addFirst(e); }     这两个方法对应栈的操作 即弹出一个元素和压入一个元素 仅仅是调用了removeFirst()和addFirst()方法       下面集中看remove相关操作的方法       remove()   public E remove() {     return removeFirst(); }     remove(int index)   public E remove(int index) {     return remove(entry(index)); }     remove(Object o)       public boolean remove(Object o) {       if (o==null) {           for (Entry<E> e = header next; e != header; e = e next) {               if (e element==null) {                   remove(e);                   return true;               }           }       } else {         for (Entry<E> e = header next; e != header; e = e next) {             if (o equals(e element)) {                 remove(e);                 return true;             }         }     }     return false; }       removeFirst()   public E removeFirst() {     return remove(header next); }     removeLast()   public E removeLast() {     return remove(header previous); }     removeFirstOccurrence()   public boolean removeFirstOccurrence(Object o) {     return remove(o); }     removeLastOccurence()       public boolean removeLastOccurrence(Object o) {       if (o==null) {           for (Entry<E> e = header previous; e != header; e = e previous) {               if (e element==null) {                   remove(e);                   return true;               }           }       } else {         for (Entry<E> e = header previous; e != header; e = e previous) {             if (o equals(e element)) {                 remove(e);                 return true;             }         }     }     return false; }       几个remove方法最终都是调用了一个私有方法 remove(Entry<E> e) 只是其他简单逻辑上的区别 下面分析remove(Entry<E> e)方法       private E remove(Entry<E> e) {       if (e == header)           throw new NoSuchElementException();       // 保留将被移除的节点e的内容   E result = e element;   // 将前一节点的next引用赋值为e的下一节点       e previous next = e next;       // 将e的下一节点的previous赋值为e的上一节点       e next previous = e previous;     // 上面两条语句的执行已经导致了无法在链表中访问到e节点 而下面解除了e节点对前后节点的引用 e next = e previous = null; // 将被移除的节点的内容设为null e element = null; // 修改size大小     size ;     modCount++;     // 返回移除节点e的内容     return result; }       clone()       public Object clone() {       LinkedList<E> clone = null;       try {           clone = (LinkedList<E>) super clone();       } catch (CloneNotSupportedException e) {           throw new InternalError();       }       clone header = new Entry<E>(null null null);       clone header next = clone header previous = clone header;     clone size = ;     clone modCount = ;     for (Entry<E> e = header next; e != header; e = e next)         clone add(e element);     return clone; }       调用父类的clone()方法初始化对象链表clone 将clone构造成一个空的双向循环链表 之后将header的下一个节点开始将逐个节点添加到clone中 最后返回克隆的clone对象       toArray()     public Object[] toArray() {     Object[] result = new Object[size];     int i = ;     for (Entry<E> e = header next; e != header; e = e next)         result[i++] = e element;     return result; }       创建大小和LinkedList相等的数组result 遍历链表 将每个节点的元素element复制到数组中 返回数组       toArray(T[] a)       public <T> T[] toArray(T[] a) {       if (a length < size)           a = (T[])java lang reflect Array newInstance(                                   a getClass() getComponentType() size);       int i = ;       Object[] result = a;       for (Entry<E> e = header next; e != header; e = e next)           result[i++] = e element;       if (a length > size)         a[size] = null;     return a; }       先判断出入的数组a的大小是否足够 若大小不够则拓展 这里用到了发射的方法 重新实例化了一个大小为size的数组 之后将数组a赋值给数组result 遍历链表向result中添加的元素 最后判断数组a的长度是否大于size 若大于则将size位置的内容设置为null 返回a       从代码中可以看出 数组a的length小于等于size时 a中所有元素被覆蓋 被拓展来的空间存储的内容都是null 若数组a的length的length大于size 则 至size 位置的内容被覆蓋 size位置的元素被设置为null size之后的元素不变       为什么不直接对数组a进行操作 要将a赋值给result数组之后对result数组进行操作？    

      LinkedList的Iterator       除了Entry LinkedList还有一个内部类 ListItr       ListItr实现了ListIterator接口 可知它是一个迭代器 通过它可以遍历修改LinkedList       在LinkedList中提供了获取ListItr对象的方法 listIterator(int index)   public ListIterator<E> listIterator(int index) {     return new ListItr(index); }     该方法只是简单的返回了一个ListItr对象       LinkedList中还有通过集成获得的listIterator()方法 该方法只是调用了listIterator(int index)并且传入       下面详细分析ListItr       private class ListItr implements ListIterator<E> {   // 最近一次返回的节点 也是当前持有的节点       private Entry<E> lastReturned = header;       // 对下一个元素的引用       private Entry<E> next;       // 下一个节点的index       private int nextIndex;       private int expectedModCount = modCount;       // 构造方法 接收一个index参数 返回一个ListItr对象       ListItr(int index) {           // 如果index小于 或大于size 抛出IndexOutOfBoundsException异常           if (index < || index > size)           throw new IndexOutOfBoundsException( Index: +index+                               Size: +size);           // 判断遍历方向           if (index < (size >> )) {           // next赋值为第一个节点           next = header next;           // 获取指定位置的节点           for (nextIndex= ; nextIndex<index; nextIndex++)               next = next next;           } else {   // else中的处理和if块中的处理一致 只是遍历方向不同           next = header;           for (nextIndex=size; nextIndex>index; nextIndex )               next = next previous;           }       }       // 根据nextIndex是否等于size判断时候还有下一个节点（也可以理解为是否遍历完了LinkedList）       public boolean hasNext() {           return nextIndex != size;       }       // 获取下一个元素       public E next() {           checkForComodification();           // 如果nextIndex==size 则已经遍历完链表 即没有下一个节点了（实际上是有的 因为是循环链表 任何一个节点都会有上一个和下一个节点 这里的没有下一个节点只是说所有节点都已经遍历完了）           if (nextIndex == size)           throw new NoSuchElementException();           // 设置最近一次返回的节点为next节点           lastReturned = next;           // 将next 向后移动一位           next = next next;           // index计数加           nextIndex++;           // 返回lastReturned的元素           return lastReturned element;       }           public boolean hasPrevious() {           return nextIndex != ;       }       // 返回上一个节点 和next()方法相似       public E previous() {           if (nextIndex == )           throw new NoSuchElementException();               lastReturned = next = next previous;           nextIndex ;           checkForComodification();           return lastReturned element;       }           public int nextIndex() {           return nextIndex;       }           public int previousIndex() {           return nextIndex ;       }       // 移除当前Iterator持有的节点       public void remove() {               checkForComodification();               Entry<E> lastNext = lastReturned next;               try {                   LinkedList this remove(lastReturned);               } catch (NoSuchElementException e) {                   throw new IllegalStateException();               }           if (next==lastReturned)                   next = lastNext;               else           nextIndex ;           lastReturned = header;           expectedModCount++;       }       // 修改当前节点的内容       public void set(E e) {           if (lastReturned == header)           throw new IllegalStateException();           checkForComodification();           lastReturned element = e;       }       // 在当前持有节点后面插入新节点       public void add(E e) {           checkForComodification();           // 将最近一次返回节点修改为header           lastReturned = header;           addBefore(e next);           nextIndex++;         expectedModCount++;     }     // 判断expectedModCount和modCount是否一致 以确保通过ListItr的修改操作正确的反映在LinkedList中     final void checkForComodification() {         if (modCount != expectedModCount)         throw new ConcurrentModificationException();     } }       下面是一个ListItr的使用实例       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());           }         try {             System out println(itr next());// throw Exception         } catch (Exception e) {             // TODO: handle exception         }         itr = list listIterator();         System out println(list);         System out println(itr next());         itr add( new node );         System out println(list);         itr add( new node );         System out println(list);         System out println(itr next());         itr set( modify node );         System out println(list);         itr remove();         System out println(list);       结果   [First Second Thrid]   First   Second   Thrid   [First Second Thrid]   First   [First new node Second Thrid]   [First new node new node Second Thrid] Second [First new node new node modify node Thrid] [First new node new node Thrid]       LinkedList还有一个提供Iterator的方法 descendingIterator() 该方法返回一个DescendingIterator对象 DescendingIterator是LinkedList的一个内部类   public Iterator<E> descendingIterator() {     return new DescendingIterator(); }     下面分析详细分析DescendingIterator类       private class DescendingIterator implements Iterator {       // 获取ListItr对象   final ListItr itr = new ListItr(size());   // hasNext其实是调用了itr的hasPrevious方法       public boolean hasNext() {           return itr hasPrevious();       }   // next()其实是调用了itr的previous方法       public E next() {         return itr previous();     }     public void remove() {         itr remove();     } }       从类名和上面的代码可以看出这是一个反向的Iterator 代码很简单 都是调用的ListItr类中的方法   lishixinzhi/Article/program/Java/hx/201311/26953