Java Coder

   1 package java.util;
   2 
   3 public class LinkedList<E> extends AbstractSequentialList<E> implements
   4         List<E>, Deque<E>, Cloneable, java.io.Serializable {
   5     /**
   6      * header是链表的头节点，但不用来存放实际的数据。
   7      * header.next是链表的第一个元素，header.previous是最后一个元素，参见方法getFirst()和getLast()
   8      */
   9     private transient Entry<E> header = new Entry<E>(null, null, null);
  10     /**
  11      * size保存链表的长度
  12      */
  13     private transient int size = 0;
  14 
  15     /**
  16      * Constructs an empty list.
  17      */
  18     public LinkedList() {
  19         // 初始化头节点
  20         header.next = header.previous = header;
  21     }
  22 
  23     /**
  24      * Constructs a list containing the elements of the specified collection, in
  25      * the order they are returned by the collection's iterator.
  26      * 
  27      * @param c
  28      *            the collection whose elements are to be placed into this list
  29      * @throws NullPointerException
  30      *             if the specified collection is null
  31      */
  32     public LinkedList(Collection<? extends E> c) {
  33         // 先调用默认构造方法，再向链表中插入指定的元素
  34         this();
  35         addAll(c);
  36     }
  37 
  38     /**
  39      * Returns the first element in this list.
  40      * 
  41      * @return the first element in this list
  42      * @throws NoSuchElementException
  43      *             if this list is empty
  44      */
  45     public E getFirst() {
  46         if (size == 0)
  47             throw new NoSuchElementException();
  48 
  49         // 返回头指针后继元素的对象
  50         return header.next.element;
  51     }
  52 
  53     /**
  54      * Returns the last element in this list.
  55      * 
  56      * @return the last element in this list
  57      * @throws NoSuchElementException
  58      *             if this list is empty
  59      */
  60     public E getLast() {
  61         if (size == 0)
  62             throw new NoSuchElementException();
  63 
  64         // 返回头指针前驱元素的对象
  65         return header.previous.element;
  66     }
  67 
  68     /**
  69      * Removes and returns the first element from this list.
  70      * 
  71      * @return the first element from this list
  72      * @throws NoSuchElementException
  73      *             if this list is empty
  74      */
  75     public E removeFirst() {
  76         return remove(header.next);
  77     }
  78 
  79     /**
  80      * Removes and returns the last element from this list.
  81      * 
  82      * @return the last element from this list
  83      * @throws NoSuchElementException
  84      *             if this list is empty
  85      */
  86     public E removeLast() {
  87         return remove(header.previous);
  88     }
  89 
  90     /**
  91      * Inserts the specified element at the beginning of this list.
  92      * 
  93      * @param e
  94      *            the element to add
  95      */
  96     public void addFirst(E e) {
  97         // 插入在第一个元素之前
  98         addBefore(e, header.next);
  99     }
 100 
 101     /**
 102      * Appends the specified element to the end of this list.
 103      * 
 104      * <p>
 105      * This method is equivalent to {@link #add}.
 106      * 
 107      * @param e
 108      *            the element to add
 109      */
 110     public void addLast(E e) {
 111         // 插入在头节点之前，即末尾元素之后
 112         addBefore(e, header);
 113     }
 114 
 115     /**
 116      * Returns <tt>true</tt> if this list contains the specified element. More
 117      * formally, returns <tt>true</tt> if and only if this list contains at
 118      * least one element <tt>e</tt> such that
 119      * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
 120      * 
 121      * @param o
 122      *            element whose presence in this list is to be tested
 123      * @return <tt>true</tt> if this list contains the specified element
 124      */
 125     public boolean contains(Object o) {
 126         return indexOf(o) != -1;
 127     }
 128 
 129     /**
 130      * Returns the number of elements in this list.
 131      * 
 132      * @return the number of elements in this list
 133      */
 134     public int size() {
 135         return size;
 136     }
 137 
 138     /**
 139      * Appends the specified element to the end of this list.
 140      * 
 141      * <p>
 142      * This method is equivalent to {@link #addLast}.
 143      * 
 144      * @param e
 145      *            element to be appended to this list
 146      * @return <tt>true</tt> (as specified by {@link Collection#add})
 147      */
 148     public boolean add(E e) {
 149         addBefore(e, header);
 150         return true;
 151     }
 152 
 153     /**
 154      * Removes the first occurrence of the specified element from this list, if
 155      * it is present. If this list does not contain the element, it is
 156      * unchanged. More formally, removes the element with the lowest index
 157      * <tt>i</tt> such that
 158      * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
 159      * (if such an element exists). Returns <tt>true</tt> if this list contained
 160      * the specified element (or equivalently, if this list changed as a result
 161      * of the call).
 162      * 
 163      * @param o
 164      *            element to be removed from this list, if present
 165      * @return <tt>true</tt> if this list contained the specified element
 166      */
 167     public boolean remove(Object o) {
 168         if (o == null) {
 169             // 从链表第一个元素开始遍历
 170             for (Entry<E> e = header.next; e != header; e = e.next) {
 171                 if (e.element == null) {
 172                     remove(e);
 173                     return true;
 174                 }
 175             }
 176         } else {
 177             for (Entry<E> e = header.next; e != header; e = e.next) {
 178                 // 使用equals方法进行比较
 179                 if (o.equals(e.element)) {
 180                     remove(e);
 181                     return true;
 182                 }
 183             }
 184         }
 185         return false;
 186     }
 187 
 188     /**
 189      * Appends all of the elements in the specified collection to the end of
 190      * this list, in the order that they are returned by the specified
 191      * collection's iterator. The behavior of this operation is #ff0000 if the
 192      * specified collection is modified while the operation is in progress.
 193      * (Note that this will occur if the specified collection is this list, and
 194      * it's nonempty.)
 195      * 
 196      * @param c
 197      *            collection containing elements to be added to this list
 198      * @return <tt>true</tt> if this list changed as a result of the call
 199      * @throws NullPointerException
 200      *             if the specified collection is null
 201      */
 202     public boolean addAll(Collection<? extends E> c) {
 203         return addAll(size, c);
 204     }
 205 
 206     /**
 207      * Inserts all of the elements in the specified collection into this list,
 208      * starting at the specified position. Shifts the element currently at that
 209      * position (if any) and any subsequent elements to the right (increases
 210      * their indices). The new elements will appear in the list in the order
 211      * that they are returned by the specified collection's iterator.
 212      * 
 213      * @param index
 214      *            index at which to insert the first element from the specified
 215      *            collection
 216      * @param c
 217      *            collection containing elements to be added to this list
 218      * @return <tt>true</tt> if this list changed as a result of the call
 219      * @throws IndexOutOfBoundsException
 220      *             {@inheritDoc}
 221      * @throws NullPointerException
 222      *             if the specified collection is null
 223      */
 224     public boolean addAll(int index, Collection<? extends E> c) {
 225         if (index < 0 || index > size)
 226             throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
 227                     + size);
 228         Object[] a = c.toArray();
 229         int numNew = a.length;
 230         if (numNew == 0)
 231             return false;
 232         modCount++;
 233 
 234         // index==size, 插在链表的末尾，即头指针header之前；否则，插在指定元素之前
 235         Entry<E> successor = (index == size ? header : entry(index));
 236         Entry<E> predecessor = successor.previous;
 237         for (int i = 0; i < numNew; i++) {
 238             // 插入新元素
 239             Entry<E> e = new Entry<E>((E) a[i], successor, predecessor);
 240             // 修改前一元素的next指针
 241             predecessor.next = e;
 242             // 修改变量，准备下一次插入
 243             predecessor = e;
 244         }
 245         // 修改插入位置元素的previous指针
 246         successor.previous = predecessor;
 247 
 248         size += numNew;
 249         return true;
 250     }
 251 
 252     /**
 253      * Removes all of the elements from this list.
 254      */
 255     public void clear() {
 256         // 取链表第一个元素
 257         Entry<E> e = header.next;
 258         while (e != header) {
 259             Entry<E> next = e.next;
 260             // 删除指针和元素
 261             e.next = e.previous = null;
 262             e.element = null;
 263             // 修改循环变量
 264             e = next;
 265         }
 266         // 恢复头节点
 267         header.next = header.previous = header;
 268         size = 0;
 269         modCount++;
 270     }
 271 
 272     // Positional Access Operations
 273 
 274     /**
 275      * Returns the element at the specified position in this list.
 276      * 
 277      * @param index
 278      *            index of the element to return
 279      * @return the element at the specified position in this list
 280      * @throws IndexOutOfBoundsException
 281      *             {@inheritDoc}
 282      */
 283     public E get(int index) {
 284         return entry(index).element;
 285     }
 286 
 287     /**
 288      * Replaces the element at the specified position in this list with the
 289      * specified element.
 290      * 
 291      * @param index
 292      *            index of the element to replace
 293      * @param element
 294      *            element to be stored at the specified position
 295      * @return the element previously at the specified position
 296      * @throws IndexOutOfBoundsException
 297      *             {@inheritDoc}
 298      */
 299     public E set(int index, E element) {
 300         Entry<E> e = entry(index);
 301         E oldVal = e.element;
 302         e.element = element;
 303         return oldVal;
 304     }
 305 
 306     /**
 307      * Inserts the specified element at the specified position in this list.
 308      * Shifts the element currently at that position (if any) and any subsequent
 309      * elements to the right (adds one to their indices).
 310      * 
 311      * @param index
 312      *            index at which the specified element is to be inserted
 313      * @param element
 314      *            element to be inserted
 315      * @throws IndexOutOfBoundsException
 316      *             {@inheritDoc}
 317      */
 318     public void add(int index, E element) {
 319         // 插入指定位置之前
 320         addBefore(element, (index == size ? header : entry(index)));
 321     }
 322 
 323     /**
 324      * Removes the element at the specified position in this list. Shifts any
 325      * subsequent elements to the left (subtracts one from their indices).
 326      * Returns the element that was removed from the list.
 327      * 
 328      * @param index
 329      *            the index of the element to be removed
 330      * @return the element previously at the specified position
 331      * @throws IndexOutOfBoundsException
 332      *             {@inheritDoc}
 333      */
 334     public E remove(int index) {
 335         return remove(entry(index));
 336     }
 337 
 338     /**
 339      * Returns the indexed entry.
 340      */
 341     private Entry<E> entry(int index) {
 342         if (index < 0 || index >= size)
 343             throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
 344                     + size);
 345         Entry<E> e = header;
 346         // index小于size的一半，从首部开始遍历
 347         if (index < (size >> 1)) {
 348             // index >= 0
 349             for (int i = 0; i <= index; i++)
 350                 e = e.next;
 351         }
 352         // 否则，从尾部开始遍历
 353         else {
 354             // index <= size-1
 355             for (int i = size; i > index; i--)
 356                 e = e.previous;
 357         }
 358         return e;
 359     }
 360 
 361     // Search Operations
 362 
 363     /**
 364      * Returns the index of the first occurrence of the specified element in
 365      * this list, or -1 if this list does not contain the element. More
 366      * formally, returns the lowest index <tt>i</tt> such that
 367      * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
 368      * or -1 if there is no such index.
 369      * 
 370      * @param o
 371      *            element to search for
 372      * @return the index of the first occurrence of the specified element in
 373      *         this list, or -1 if this list does not contain the element
 374      */
 375     // 参见函数 remove(Object o)
 376     public int indexOf(Object o) {
 377         int index = 0;
 378         if (o == null) {
 379             for (Entry e = header.next; e != header; e = e.next) {
 380                 if (e.element == null)
 381                     return index;
 382                 index++;
 383             }
 384         } else {
 385             for (Entry e = header.next; e != header; e = e.next) {
 386                 if (o.equals(e.element))
 387                     return index;
 388                 index++;
 389             }
 390         }
 391         return -1;
 392     }
 393 
 394     /**
 395      * Returns the index of the last occurrence of the specified element in this
 396      * list, or -1 if this list does not contain the element. More formally,
 397      * returns the highest index <tt>i</tt> such that
 398      * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
 399      * or -1 if there is no such index.
 400      * 
 401      * @param o
 402      *            element to search for
 403      * @return the index of the last occurrence of the specified element in this
 404      *         list, or -1 if this list does not contain the element
 405      */
 406     public int lastIndexOf(Object o) {
 407         int index = size;
 408         if (o == null) {
 409             // 从链表的末尾开始遍历
 410             for (Entry e = header.previous; e != header; e = e.previous) {
 411                 index--;
 412                 if (e.element == null)
 413                     return index;
 414             }
 415         } else {
 416             for (Entry e = header.previous; e != header; e = e.previous) {
 417                 index--;
 418                 if (o.equals(e.element))
 419                     return index;
 420             }
 421         }
 422         return -1;
 423     }
 424 
 425     // Queue operations.
 426 
 427     /**
 428      * Retrieves, but does not remove, the head (first element) of this list.
 429      * 
 430      * @return the head of this list, or <tt>null</tt> if this list is empty
 431      * @since 1.5
 432      */
 433     public E peek() {
 434         if (size == 0)
 435             return null;
 436         return getFirst();
 437     }
 438 
 439     /**
 440      * Retrieves, but does not remove, the head (first element) of this list.
 441      * 
 442      * @return the head of this list
 443      * @throws NoSuchElementException
 444      *             if this list is empty
 445      * @since 1.5
 446      */
 447     public E element() {
 448         return getFirst();
 449     }
 450 
 451     /**
 452      * Retrieves and removes the head (first element) of this list
 453      * 
 454      * @return the head of this list, or <tt>null</tt> if this list is empty
 455      * @since 1.5
 456      */
 457     public E poll() {
 458         if (size == 0)
 459             return null;
 460         return removeFirst();
 461     }
 462 
 463     /**
 464      * Retrieves and removes the head (first element) of this list.
 465      * 
 466      * @return the head of this list
 467      * @throws NoSuchElementException
 468      *             if this list is empty
 469      * @since 1.5
 470      */
 471     public E remove() {
 472         return removeFirst();
 473     }
 474 
 475     /**
 476      * Adds the specified element as the tail (last element) of this list.
 477      * 
 478      * @param e
 479      *            the element to add
 480      * @return <tt>true</tt> (as specified by {@link Queue#offer})
 481      * @since 1.5
 482      */
 483     public boolean offer(E e) {
 484         return add(e);
 485     }
 486 
 487     // Deque operations
 488     /**
 489      * Inserts the specified element at the front of this list.
 490      * 
 491      * @param e
 492      *            the element to insert
 493      * @return <tt>true</tt> (as specified by {@link Deque#offerFirst})
 494      * @since 1.6
 495      */
 496     public boolean offerFirst(E e) {
 497         addFirst(e);
 498         return true;
 499     }
 500 
 501     /**
 502      * Inserts the specified element at the end of this list.
 503      * 
 504      * @param e
 505      *            the element to insert
 506      * @return <tt>true</tt> (as specified by {@link Deque#offerLast})
 507      * @since 1.6
 508      */
 509     public boolean offerLast(E e) {
 510         addLast(e);
 511         return true;
 512     }
 513 
 514     /**
 515      * Retrieves, but does not remove, the first element of this list, or
 516      * returns <tt>null</tt> if this list is empty.
 517      * 
 518      * @return the first element of this list, or <tt>null</tt> if this list is
 519      *         empty
 520      * @since 1.6
 521      */
 522     public E peekFirst() {
 523         if (size == 0)
 524             return null;
 525         return getFirst();
 526     }
 527 
 528     /**
 529      * Retrieves, but does not remove, the last element of this list, or returns
 530      * <tt>null</tt> if this list is empty.
 531      * 
 532      * @return the last element of this list, or <tt>null</tt> if this list is
 533      *         empty
 534      * @since 1.6
 535      */
 536     public E peekLast() {
 537         if (size == 0)
 538             return null;
 539         return getLast();
 540     }
 541 
 542     /**
 543      * Retrieves and removes the first element of this list, or returns
 544      * <tt>null</tt> if this list is empty.
 545      * 
 546      * @return the first element of this list, or <tt>null</tt> if this list is
 547      *         empty
 548      * @since 1.6
 549      */
 550     public E pollFirst() {
 551         if (size == 0)
 552             return null;
 553         return removeFirst();
 554     }
 555 
 556     /**
 557      * Retrieves and removes the last element of this list, or returns
 558      * <tt>null</tt> if this list is empty.
 559      * 
 560      * @return the last element of this list, or <tt>null</tt> if this list is
 561      *         empty
 562      * @since 1.6
 563      */
 564     public E pollLast() {
 565         if (size == 0)
 566             return null;
 567         return removeLast();
 568     }
 569 
 570     /**
 571      * Pushes an element onto the stack represented by this list. In other
 572      * words, inserts the element at the front of this list.
 573      * 
 574      * <p>
 575      * This method is equivalent to {@link #addFirst}.
 576      * 
 577      * @param e
 578      *            the element to push
 579      * @since 1.6
 580      */
 581     public void push(E e) {
 582         addFirst(e);
 583     }
 584 
 585     /**
 586      * Pops an element from the stack represented by this list. In other words,
 587      * removes and returns the first element of this list.
 588      * 
 589      * <p>
 590      * This method is equivalent to {@link #removeFirst()}.
 591      * 
 592      * @return the element at the front of this list (which is the top of the
 593      *         stack represented by this list)
 594      * @throws NoSuchElementException
 595      *             if this list is empty
 596      * @since 1.6
 597      */
 598     public E pop() {
 599         return removeFirst();
 600     }
 601 
 602     /**
 603      * Removes the first occurrence of the specified element in this list (when
 604      * traversing the list from head to tail). If the list does not contain the
 605      * element, it is unchanged.
 606      * 
 607      * @param o
 608      *            element to be removed from this list, if present
 609      * @return <tt>true</tt> if the list contained the specified element
 610      * @since 1.6
 611      */
 612     public boolean removeFirstOccurrence(Object o) {
 613         return remove(o);
 614     }
 615 
 616     /**
 617      * Removes the last occurrence of the specified element in this list (when
 618      * traversing the list from head to tail). If the list does not contain the
 619      * element, it is unchanged.
 620      * 
 621      * @param o
 622      *            element to be removed from this list, if present
 623      * @return <tt>true</tt> if the list contained the specified element
 624      * @since 1.6
 625      */
 626     public boolean removeLastOccurrence(Object o) {
 627         if (o == null) {
 628             for (Entry<E> e = header.previous; e != header; e = e.previous) {
 629                 if (e.element == null) {
 630                     remove(e);
 631                     return true;
 632                 }
 633             }
 634         } else {
 635             for (Entry<E> e = header.previous; e != header; e = e.previous) {
 636                 if (o.equals(e.element)) {
 637                     remove(e);
 638                     return true;
 639                 }
 640             }
 641         }
 642         return false;
 643     }
 644 
 645     /**
 646      * Returns a list-iterator of the elements in this list (in proper
 647      * sequence), starting at the specified position in the list. Obeys the
 648      * general contract of <tt>List.listIterator(int)</tt>.
 649      * <p>
 650      * 
 651      * The list-iterator is <i>fail-fast</i>: if the list is structurally
 652      * modified at any time after the Iterator is created, in any way except
 653      * through the list-iterator's own <tt>remove</tt> or <tt>add</tt> methods,
 654      * the list-iterator will throw a <tt>ConcurrentModificationException</tt>.
 655      * Thus, in the face of concurrent modification, the iterator fails quickly
 656      * and cleanly, rather than risking arbitrary, non-deterministic behavior at
 657      * an undetermined time in the future.
 658      * 
 659      * @param index
 660      *            index of the first element to be returned from the
 661      *            list-iterator (by a call to <tt>next</tt>)
 662      * @return a ListIterator of the elements in this list (in proper sequence),
 663      *         starting at the specified position in the list
 664      * @throws IndexOutOfBoundsException
 665      *             {@inheritDoc}
 666      * @see List#listIterator(int)
 667      */
 668     public ListIterator<E> listIterator(int index) {
 669         return new ListItr(index);
 670     }
 671 
 672     // 内部类实现ListIterator接口
 673     private class ListItr implements ListIterator<E> {
 674         private Entry<E> lastReturned = header;
 675         private Entry<E> next;
 676         private int nextIndex;
 677         private int expectedModCount = modCount;
 678 
 679         // index是第一个被next()返回的元素
 680         ListItr(int index) {
 681             if (index < 0 || index > size)
 682                 throw new IndexOutOfBoundsException("Index: " + index
 683                         + ", Size: " + size);
 684             if (index < (size >> 1)) {
 685                 // next指向第0个元素
 686                 next = header.next;
 687                 // next指向第index个元素,nextIndex=index
 688                 for (nextIndex = 0; nextIndex < index; nextIndex++)
 689                     next = next.next;
 690             } else {
 691                 // 指向头节点
 692                 next = header;
 693                 for (nextIndex = size; nextIndex > index; nextIndex--)
 694                     next = next.previous;
 695             }
 696         }
 697 
 698         public boolean hasNext() {
 699             return nextIndex != size;
 700         }
 701 
 702         public E next() {
 703             // 链表状态是否一致？
 704             checkForComodification();
 705             if (nextIndex == size)
 706                 throw new NoSuchElementException();
 707 
 708             // 记录next元素，并准备返回
 709             lastReturned = next;
 710             next = next.next;
 711             nextIndex++;
 712             return lastReturned.element;
 713         }
 714 
 715         public boolean hasPrevious() {
 716             return nextIndex != 0;
 717         }
 718 
 719         public E previous() {
 720             if (nextIndex == 0)
 721                 throw new NoSuchElementException();
 722 
 723             lastReturned = next = next.previous;
 724             nextIndex--;
 725             checkForComodification();
 726             return lastReturned.element;
 727         }
 728 
 729         public int nextIndex() {
 730             // 最大为size,当指向链表末尾的时候
 731             return nextIndex;
 732         }
 733 
 734         public int previousIndex() {
 735             // 最小为-1,当指向链表首部的时候
 736             return nextIndex - 1;
 737         }
 738 
 739         public void remove() {
 740             checkForComodification();
 741             Entry<E> lastNext = lastReturned.next;
 742             try {
 743                 // 删除lastReturned元素
 744                 LinkedList.this.remove(lastReturned);
 745             } catch (NoSuchElementException e) {
 746                 throw new IllegalStateException();
 747             }
 748             // 之前调用了 previous()方法
 749             if (next == lastReturned)
 750                 next = lastNext;
 751             else
 752                 // 之前调用了next()方法
 753                 nextIndex--;
 754             // 修改lastReturned，保证只能remove一次
 755             lastReturned = header;
 756             expectedModCount++;
 757         }
 758 
 759         public void set(E e) {
 760             if (lastReturned == header)
 761                 throw new IllegalStateException();
 762             checkForComodification();
 763             lastReturned.element = e;
 764         }
 765 
 766         // 插入在next()元素之前
 767         public void add(E e) {
 768             checkForComodification();
 769             // 修改lastReturned，保证只能add一次
 770             lastReturned = header;
 771             addBefore(e, next);
 772             // next()不会取得新加入的元素
 773             nextIndex++;
 774             expectedModCount++;
 775         }
 776 
 777         final void checkForComodification() {
 778             if (modCount != expectedModCount)
 779                 throw new ConcurrentModificationException();
 780         }
 781     }
 782 
 783     // 类似struct结构体，链表中的数据元素都是一个Entry对象
 784     private static class Entry<E> {
 785         E element;
 786         Entry<E> next;
 787         Entry<E> previous;
 788 
 789         Entry(E element, Entry<E> next, Entry<E> previous) {
 790             this.element = element;
 791             this.next = next;
 792             this.previous = previous;
 793         }
 794     }
 795 
 796     // 私有辅助方法，添加元素到链表指定元素之前
 797     private Entry<E> addBefore(E e, Entry<E> entry) {
 798         Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
 799         newEntry.previous.next = newEntry;
 800         newEntry.next.previous = newEntry;
 801         size++;
 802         modCount++;
 803         return newEntry;
 804     }
 805 
 806     // 私有辅助方法，删除一个链表元素
 807     private E remove(Entry<E> e) {
 808         if (e == header)
 809             throw new NoSuchElementException();
 810 
 811         E result = e.element;
 812         // 修改前后元素的指针
 813         e.previous.next = e.next;
 814         e.next.previous = e.previous;
 815         // 删除当前元素
 816         e.next = e.previous = null;
 817         e.element = null;
 818         size--;
 819         modCount++;
 820         return result;
 821     }
 822 
 823     /**
 824      * @since 1.6
 825      */
 826     public Iterator<E> descendingIterator() {
 827         return new DescendingIterator();
 828     }
 829 
 830     /** Adapter to provide descending iterators via ListItr.previous */
 831     // Iterator接口的实现类，提供对链表的反向遍历
 832     private class DescendingIterator implements Iterator {
 833         final ListItr itr = new ListItr(size());
 834 
 835         public boolean hasNext() {
 836             return itr.hasPrevious();
 837         }
 838 
 839         public E next() {
 840             return itr.previous();
 841         }
 842 
 843         public void remove() {
 844             itr.remove();
 845         }
 846     }
 847 
 848     /**
 849      * Returns a shallow copy of this <tt>LinkedList</tt>. (The elements
 850      * themselves are not cloned.)
 851      * 
 852      * @return a shallow copy of this <tt>LinkedList</tt> instance
 853      */
 854     public Object clone() {
 855         LinkedList<E> clone = null;
 856         try {
 857             clone = (LinkedList<E>) super.clone();
 858         } catch (CloneNotSupportedException e) {
 859             throw new InternalError();
 860         }
 861 
 862         // Put clone into "virgin" state
 863         // 初始化clone对象
 864         clone.header = new Entry<E>(null, null, null);
 865         clone.header.next = clone.header.previous = clone.header;
 866         clone.size = 0;
 867         clone.modCount = 0;
 868 
 869         // Initialize clone with our elements
 870         for (Entry<E> e = header.next; e != header; e = e.next)
 871             clone.add(e.element);
 872 
 873         // 返回的clone对象包括所有元素对象的引用
 874         return clone;
 875     }
 876 
 877     /**
 878      * Returns an array containing all of the elements in this list in proper
 879      * sequence (from first to last element).
 880      * 
 881      * <p>
 882      * The returned array will be "safe" in that no references to it are
 883      * maintained by this list. (In other words, this method must allocate a new
 884      * array). The caller is thus free to modify the returned array.
 885      * 
 886      * <p>
 887      * This method acts as bridge between array-based and collection-based APIs.
 888      * 
 889      * @return an array containing all of the elements in this list in proper
 890      *         sequence
 891      */
 892     public Object[] toArray() {
 893         Object[] result = new Object[size];
 894         int i = 0;
 895         for (Entry<E> e = header.next; e != header; e = e.next)
 896             result[i++] = e.element;
 897         return result;
 898     }
 899 
 900     /**
 901      * Returns an array containing all of the elements in this list in proper
 902      * sequence (from first to last element); the runtime type of the returned
 903      * array is that of the specified array. If the list fits in the specified
 904      * array, it is returned therein. Otherwise, a new array is allocated with
 905      * the runtime type of the specified array and the size of this list.
 906      * 
 907      * <p>
 908      * If the list fits in the specified array with room to spare (i.e., the
 909      * array has more elements than the list), the element in the array
 910      * immediately following the end of the list is set to <tt>null</tt>. (This
 911      * is useful in determining the length of the list <i>only</i> if the caller
 912      * knows that the list does not contain any null elements.)
 913      * 
 914      * <p>
 915      * Like the {@link #toArray()} method, this method acts as bridge between
 916      * array-based and collection-based APIs. Further, this method allows
 917      * precise control over the runtime type of the output array, and may, under
 918      * certain circumstances, be used to save allocation costs.
 919      * 
 920      * <p>
 921      * Suppose <tt>x</tt> is a list known to contain only strings. The following
 922      * code can be used to dump the list into a newly allocated array of
 923      * <tt>String</tt>:
 924      * 
 925      * <pre>
 926      * String[] y = x.toArray(new String[0]);
 927      * </pre>
 928      * 
 929      * Note that <tt>toArray(new Object[0])</tt> is identical in function to
 930      * <tt>toArray()</tt>.
 931      * 
 932      * @param a
 933      *            the array into which the elements of the list are to be
 934      *            stored, if it is big enough; otherwise, a new array of the
 935      *            same runtime type is allocated for this purpose.
 936      * @return an array containing the elements of the list
 937      * @throws ArrayStoreException
 938      *             if the runtime type of the specified array is not a supertype
 939      *             of the runtime type of every element in this list
 940      * @throws NullPointerException
 941      *             if the specified array is null
 942      */
 943     public <T> T[] toArray(T[] a) {
 944         // 若指定的数组容量小于链表长度，新建数组
 945         if (a.length < size)
 946             a = (T[]) java.lang.reflect.Array.newInstance(a.getClass()
 947                     .getComponentType(), size);
 948         int i = 0;
 949         Object[] result = a;
 950         for (Entry<E> e = header.next; e != header; e = e.next)
 951             result[i++] = e.element;
 952 
 953         // 将数组中第一个无效元素置为null
 954         if (a.length > size)
 955             a[size] = null;
 956 
 957         return a;
 958     }
 959 
 960     private static final long serialVersionUID = 876323262645176354L;
 961 
 962     /**
 963      * Save the state of this <tt>LinkedList</tt> instance to a stream (that is,
 964      * serialize it).
 965      * 
 966      * @serialData The size of the list (the number of elements it contains) is
 967      *             emitted (int), followed by all of its elements (each an
 968      *             Object) in the proper order.
 969      */
 970     private void writeObject(java.io.ObjectOutputStream s)
 971             throws java.io.IOException {
 972         // Write out any hidden serialization magic
 973         s.defaultWriteObject();
 974 
 975         // Write out size
 976         s.writeInt(size);
 977 
 978         // Write out all elements in the proper order.
 979         for (Entry e = header.next; e != header; e = e.next)
 980             s.writeObject(e.element);
 981     }
 982 
 983     /**
 984      * Reconstitute this <tt>LinkedList</tt> instance from a stream (that is
 985      * deserialize it).
 986      */
 987     private void readObject(java.io.ObjectInputStream s)
 988             throws java.io.IOException, ClassNotFoundException {
 989         // Read in any hidden serialization magic
 990         s.defaultReadObject();
 991 
 992         // Read in size
 993         int size = s.readInt();
 994 
 995         // Initialize header
 996         header = new Entry<E>(null, null, null);
 997         header.next = header.previous = header;
 998 
 999         // Read in all elements in the proper order.
1000         for (int i = 0; i < size; i++)
1001             addBefore((E) s.readObject(), header);
1002     }
1003 }
1004