1 /*
   2  * Copyright (c) 2007, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package sun.awt.util;
  27 
  28 import java.util.AbstractSequentialList;
  29 import java.util.Collection;
  30 import java.util.ConcurrentModificationException;
  31 import java.util.Deque;
  32 import java.util.Iterator;
  33 import java.util.List;
  34 import java.util.ListIterator;
  35 import java.util.NoSuchElementException;
  36 
  37 /**
  38  * Linked list implementation of the <tt>List</tt> interface.  Implements all
  39  * optional list operations, and permits all elements (including
  40  * <tt>null</tt>).  In addition to implementing the <tt>List</tt> interface,
  41  * the <tt>IdentityLinkedList</tt> class provides uniformly named methods to
  42  * <tt>get</tt>, <tt>remove</tt> and <tt>insert</tt> an element at the
  43  * beginning and end of the list.  These operations allow linked lists to be
  44  * used as a stack, {@linkplain java.util.Queue queue}, or {@linkplain Deque
  45  * double-ended queue}. <p>
  46  *
  47  * The class implements the <tt>Deque</tt> interface, providing
  48  * first-in-first-out queue operations for <tt>add</tt>,
  49  * <tt>poll</tt>, along with other stack and deque operations.<p>
  50  *
  51  * All of the operations perform as could be expected for a doubly-linked
  52  * list.  Operations that index into the list will traverse the list from
  53  * the beginning or the end, whichever is closer to the specified index.<p>
  54  *
  55  * <p><strong>Note that this implementation is not synchronized.</strong>
  56  * If multiple threads access a linked list concurrently, and at least
  57  * one of the threads modifies the list structurally, it <i>must</i> be
  58  * synchronized externally.  (A structural modification is any operation
  59  * that adds or deletes one or more elements; merely setting the value of
  60  * an element is not a structural modification.)  This is typically
  61  * accomplished by synchronizing on some object that naturally
  62  * encapsulates the list.
  63  *
  64  * If no such object exists, the list should be "wrapped" using the
  65  * {@link java.util.Collections#synchronizedList Collections.synchronizedList}
  66  * method.  This is best done at creation time, to prevent accidental
  67  * unsynchronized access to the list:<pre>
  68  *   List list = Collections.synchronizedList(new IdentityLinkedList(...));</pre>
  69  *
  70  * <p>The iterators returned by this class's <tt>iterator</tt> and
  71  * <tt>listIterator</tt> methods are <i>fail-fast</i>: if the list is
  72  * structurally modified at any time after the iterator is created, in
  73  * any way except through the Iterator's own <tt>remove</tt> or
  74  * <tt>add</tt> methods, the iterator will throw a {@link
  75  * ConcurrentModificationException}.  Thus, in the face of concurrent
  76  * modification, the iterator fails quickly and cleanly, rather than
  77  * risking arbitrary, non-deterministic behavior at an undetermined
  78  * time in the future.
  79  *
  80  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
  81  * as it is, generally speaking, impossible to make any hard guarantees in the
  82  * presence of unsynchronized concurrent modification.  Fail-fast iterators
  83  * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
  84  * Therefore, it would be wrong to write a program that depended on this
  85  * exception for its correctness:   <i>the fail-fast behavior of iterators
  86  * should be used only to detect bugs.</i>
  87  */
  88 
  89 public class IdentityLinkedList<E>
  90     extends AbstractSequentialList<E>
  91     implements List<E>, Deque<E>
  92 {
  93     private transient Entry<E> header = new Entry<E>(null, null, null);
  94     private transient int size = 0;
  95 
  96     /**
  97      * Constructs an empty list.
  98      */
  99     public IdentityLinkedList() {
 100         header.next = header.previous = header;
 101     }
 102 
 103     /**
 104      * Constructs a list containing the elements of the specified
 105      * collection, in the order they are returned by the collection's
 106      * iterator.
 107      *
 108      * @param  c the collection whose elements are to be placed into this list
 109      * @throws NullPointerException if the specified collection is null
 110      */
 111     public IdentityLinkedList(Collection<? extends E> c) {
 112         this();
 113         addAll(c);
 114     }
 115 
 116     /**
 117      * Returns the first element in this list.
 118      *
 119      * @return the first element in this list
 120      * @throws NoSuchElementException if this list is empty
 121      */
 122     public E getFirst() {
 123         if (size==0)
 124             throw new NoSuchElementException();
 125 
 126         return header.next.element;
 127     }
 128 
 129     /**
 130      * Returns the last element in this list.
 131      *
 132      * @return the last element in this list
 133      * @throws NoSuchElementException if this list is empty
 134      */
 135     public E getLast()  {
 136         if (size==0)
 137             throw new NoSuchElementException();
 138 
 139         return header.previous.element;
 140     }
 141 
 142     /**
 143      * Removes and returns the first element from this list.
 144      *
 145      * @return the first element from this list
 146      * @throws NoSuchElementException if this list is empty
 147      */
 148     public E removeFirst() {
 149         return remove(header.next);
 150     }
 151 
 152     /**
 153      * Removes and returns the last element from this list.
 154      *
 155      * @return the last element from this list
 156      * @throws NoSuchElementException if this list is empty
 157      */
 158     public E removeLast() {
 159         return remove(header.previous);
 160     }
 161 
 162     /**
 163      * Inserts the specified element at the beginning of this list.
 164      *
 165      * @param e the element to add
 166      */
 167     public void addFirst(E e) {
 168         addBefore(e, header.next);
 169     }
 170 
 171     /**
 172      * Appends the specified element to the end of this list.
 173      *
 174      * <p>This method is equivalent to {@link #add}.
 175      *
 176      * @param e the element to add
 177      */
 178     public void addLast(E e) {
 179         addBefore(e, header);
 180     }
 181 
 182     /**
 183      * Returns <tt>true</tt> if this list contains the specified element.
 184      * More formally, returns <tt>true</tt> if and only if this list contains
 185      * at least one element <tt>e</tt> such that
 186      * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o == e)</tt>.
 187      *
 188      * @param o element whose presence in this list is to be tested
 189      * @return <tt>true</tt> if this list contains the specified element
 190      */
 191     public boolean contains(Object o) {
 192         return indexOf(o) != -1;
 193     }
 194 
 195     /**
 196      * Returns the number of elements in this list.
 197      *
 198      * @return the number of elements in this list
 199      */
 200     public int size() {
 201         return size;
 202     }
 203 
 204     /**
 205      * Appends the specified element to the end of this list.
 206      *
 207      * <p>This method is equivalent to {@link #addLast}.
 208      *
 209      * @param e element to be appended to this list
 210      * @return <tt>true</tt> (as specified by {@link Collection#add})
 211      */
 212     public boolean add(E e) {
 213         addBefore(e, header);
 214         return true;
 215     }
 216 
 217     /**
 218      * Removes the first occurrence of the specified element from this list,
 219      * if it is present.  If this list does not contain the element, it is
 220      * unchanged.  More formally, removes the element with the lowest index
 221      * <tt>i</tt> such that <tt>get(i)==o</tt>
 222      * (if such an element exists).  Returns <tt>true</tt> if this list
 223      * contained the specified element (or equivalently, if this list
 224      * changed as a result of the call).
 225      *
 226      * @param o element to be removed from this list, if present
 227      * @return <tt>true</tt> if this list contained the specified element
 228      */
 229     public boolean remove(Object o) {
 230         for (Entry<E> e = header.next; e != header; e = e.next) {
 231             if (o == e.element) {
 232                 remove(e);
 233                 return true;
 234             }
 235         }
 236         return false;
 237     }
 238 
 239     /**
 240      * Appends all of the elements in the specified collection to the end of
 241      * this list, in the order that they are returned by the specified
 242      * collection's iterator.  The behavior of this operation is undefined if
 243      * the specified collection is modified while the operation is in
 244      * progress.  (Note that this will occur if the specified collection is
 245      * this list, and it's nonempty.)
 246      *
 247      * @param c collection containing elements to be added to this list
 248      * @return <tt>true</tt> if this list changed as a result of the call
 249      * @throws NullPointerException if the specified collection is null
 250      */
 251     public boolean addAll(Collection<? extends E> c) {
 252         return addAll(size, c);
 253     }
 254 
 255     /**
 256      * Inserts all of the elements in the specified collection into this
 257      * list, starting at the specified position.  Shifts the element
 258      * currently at that position (if any) and any subsequent elements to
 259      * the right (increases their indices).  The new elements will appear
 260      * in the list in the order that they are returned by the
 261      * specified collection's iterator.
 262      *
 263      * @param index index at which to insert the first element
 264      *              from the specified collection
 265      * @param c collection containing elements to be added to this list
 266      * @return <tt>true</tt> if this list changed as a result of the call
 267      * @throws IndexOutOfBoundsException {@inheritDoc}
 268      * @throws NullPointerException if the specified collection is null
 269      */
 270     public boolean addAll(int index, Collection<? extends E> c) {
 271         if (index < 0 || index > size)
 272             throw new IndexOutOfBoundsException("Index: "+index+
 273                                                 ", Size: "+size);
 274         Object[] a = c.toArray();
 275         int numNew = a.length;
 276         if (numNew==0)
 277             return false;
 278         modCount++;
 279 
 280         Entry<E> successor = (index==size ? header : entry(index));
 281         Entry<E> predecessor = successor.previous;
 282         for (int i=0; i<numNew; i++) {
 283             @SuppressWarnings("unchecked")
 284             E tmp = (E) a[i];
 285             Entry<E> e = new Entry<E>(tmp, successor, predecessor);
 286             predecessor.next = e;
 287             predecessor = e;
 288         }
 289         successor.previous = predecessor;
 290 
 291         size += numNew;
 292         return true;
 293     }
 294 
 295     /**
 296      * Removes all of the elements from this list.
 297      */
 298     public void clear() {
 299         Entry<E> e = header.next;
 300         while (e != header) {
 301             Entry<E> next = e.next;
 302             e.next = e.previous = null;
 303             e.element = null;
 304             e = next;
 305         }
 306         header.next = header.previous = header;
 307         size = 0;
 308         modCount++;
 309     }
 310 
 311 
 312     // Positional Access Operations
 313 
 314     /**
 315      * Returns the element at the specified position in this list.
 316      *
 317      * @param index index of the element to return
 318      * @return the element at the specified position in this list
 319      * @throws IndexOutOfBoundsException {@inheritDoc}
 320      */
 321     public E get(int index) {
 322         return entry(index).element;
 323     }
 324 
 325     /**
 326      * Replaces the element at the specified position in this list with the
 327      * specified element.
 328      *
 329      * @param index index of the element to replace
 330      * @param element element to be stored at the specified position
 331      * @return the element previously at the specified position
 332      * @throws IndexOutOfBoundsException {@inheritDoc}
 333      */
 334     public E set(int index, E element) {
 335         Entry<E> e = entry(index);
 336         E oldVal = e.element;
 337         e.element = element;
 338         return oldVal;
 339     }
 340 
 341     /**
 342      * Inserts the specified element at the specified position in this list.
 343      * Shifts the element currently at that position (if any) and any
 344      * subsequent elements to the right (adds one to their indices).
 345      *
 346      * @param index index at which the specified element is to be inserted
 347      * @param element element to be inserted
 348      * @throws IndexOutOfBoundsException {@inheritDoc}
 349      */
 350     public void add(int index, E element) {
 351         addBefore(element, (index==size ? header : entry(index)));
 352     }
 353 
 354     /**
 355      * Removes the element at the specified position in this list.  Shifts any
 356      * subsequent elements to the left (subtracts one from their indices).
 357      * Returns the element that was removed from the list.
 358      *
 359      * @param index the index of the element to be removed
 360      * @return the element previously at the specified position
 361      * @throws IndexOutOfBoundsException {@inheritDoc}
 362      */
 363     public E remove(int index) {
 364         return remove(entry(index));
 365     }
 366 
 367     /**
 368      * Returns the indexed entry.
 369      */
 370     private Entry<E> entry(int index) {
 371         if (index < 0 || index >= size)
 372             throw new IndexOutOfBoundsException("Index: "+index+
 373                                                 ", Size: "+size);
 374         Entry<E> e = header;
 375         if (index < (size >> 1)) {
 376             for (int i = 0; i <= index; i++)
 377                 e = e.next;
 378         } else {
 379             for (int i = size; i > index; i--)
 380                 e = e.previous;
 381         }
 382         return e;
 383     }
 384 
 385 
 386     // Search Operations
 387 
 388     /**
 389      * Returns the index of the first occurrence of the specified element
 390      * in this list, or -1 if this list does not contain the element.
 391      * More formally, returns the lowest index <tt>i</tt> such that
 392      * <tt>get(i)==o</tt>,
 393      * or -1 if there is no such index.
 394      *
 395      * @param o element to search for
 396      * @return the index of the first occurrence of the specified element in
 397      *         this list, or -1 if this list does not contain the element
 398      */
 399     public int indexOf(Object o) {
 400         int index = 0;
 401         for (Entry<E> e = header.next; e != header; e = e.next) {
 402             if (o == e.element) {
 403                 return index;
 404             }
 405             index++;
 406         }
 407         return -1;
 408     }
 409 
 410     /**
 411      * Returns the index of the last occurrence of the specified element
 412      * in this list, or -1 if this list does not contain the element.
 413      * More formally, returns the highest index <tt>i</tt> such that
 414      * <tt>get(i)==o</tt>,
 415      * or -1 if there is no such index.
 416      *
 417      * @param o element to search for
 418      * @return the index of the last occurrence of the specified element in
 419      *         this list, or -1 if this list does not contain the element
 420      */
 421     public int lastIndexOf(Object o) {
 422         int index = size;
 423         for (Entry<E> e = header.previous; e != header; e = e.previous) {
 424             index--;
 425             if (o == e.element) {
 426                 return index;
 427             }
 428         }
 429         return -1;
 430     }
 431 
 432     // Queue operations.
 433 
 434     /**
 435      * Retrieves, but does not remove, the head (first element) of this list.
 436      * @return the head of this list, or <tt>null</tt> if this list is empty
 437      * @since 1.5
 438      */
 439     public E peek() {
 440         if (size==0)
 441             return null;
 442         return getFirst();
 443     }
 444 
 445     /**
 446      * Retrieves, but does not remove, the head (first element) of this list.
 447      * @return the head of this list
 448      * @throws NoSuchElementException if this list is empty
 449      * @since 1.5
 450      */
 451     public E element() {
 452         return getFirst();
 453     }
 454 
 455     /**
 456      * Retrieves and removes the head (first element) of this list
 457      * @return the head of this list, or <tt>null</tt> if this list is empty
 458      * @since 1.5
 459      */
 460     public E poll() {
 461         if (size==0)
 462             return null;
 463         return removeFirst();
 464     }
 465 
 466     /**
 467      * Retrieves and removes the head (first element) of this list.
 468      *
 469      * @return the head of this list
 470      * @throws NoSuchElementException if this list is empty
 471      * @since 1.5
 472      */
 473     public E remove() {
 474         return removeFirst();
 475     }
 476 
 477     /**
 478      * Adds the specified element as the tail (last element) of this list.
 479      *
 480      * @param e the element to add
 481      * @return <tt>true</tt> (as specified by {@link java.util.Queue#offer})
 482      * @since 1.5
 483      */
 484     public boolean offer(E e) {
 485         return add(e);
 486     }
 487 
 488     // Deque operations
 489     /**
 490      * Inserts the specified element at the front of this list.
 491      *
 492      * @param e 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 the element to insert
 505      * @return <tt>true</tt> (as specified by {@link Deque#offerLast})
 506      * @since 1.6
 507      */
 508     public boolean offerLast(E e) {
 509         addLast(e);
 510         return true;
 511     }
 512 
 513     /**
 514      * Retrieves, but does not remove, the first element of this list,
 515      * or returns <tt>null</tt> if this list is empty.
 516      *
 517      * @return the first element of this list, or <tt>null</tt>
 518      *         if this list is empty
 519      * @since 1.6
 520      */
 521     public E peekFirst() {
 522         if (size==0)
 523             return null;
 524         return getFirst();
 525     }
 526 
 527     /**
 528      * Retrieves, but does not remove, the last element of this list,
 529      * or returns <tt>null</tt> if this list is empty.
 530      *
 531      * @return the last element of this list, or <tt>null</tt>
 532      *         if this list is empty
 533      * @since 1.6
 534      */
 535     public E peekLast() {
 536         if (size==0)
 537             return null;
 538         return getLast();
 539     }
 540 
 541     /**
 542      * Retrieves and removes the first element of this list,
 543      * or returns <tt>null</tt> if this list is empty.
 544      *
 545      * @return the first element of this list, or <tt>null</tt> if
 546      *     this list is empty
 547      * @since 1.6
 548      */
 549     public E pollFirst() {
 550         if (size==0)
 551             return null;
 552         return removeFirst();
 553     }
 554 
 555     /**
 556      * Retrieves and removes the last element of this list,
 557      * or returns <tt>null</tt> if this list is empty.
 558      *
 559      * @return the last element of this list, or <tt>null</tt> if
 560      *     this list is empty
 561      * @since 1.6
 562      */
 563     public E pollLast() {
 564         if (size==0)
 565             return null;
 566         return removeLast();
 567     }
 568 
 569     /**
 570      * Pushes an element onto the stack represented by this list.  In other
 571      * words, inserts the element at the front of this list.
 572      *
 573      * <p>This method is equivalent to {@link #addFirst}.
 574      *
 575      * @param e the element to push
 576      * @since 1.6
 577      */
 578     public void push(E e) {
 579         addFirst(e);
 580     }
 581 
 582     /**
 583      * Pops an element from the stack represented by this list.  In other
 584      * words, removes and returns the first element of this list.
 585      *
 586      * <p>This method is equivalent to {@link #removeFirst()}.
 587      *
 588      * @return the element at the front of this list (which is the top
 589      *         of the stack represented by this list)
 590      * @throws NoSuchElementException if this list is empty
 591      * @since 1.6
 592      */
 593     public E pop() {
 594         return removeFirst();
 595     }
 596 
 597     /**
 598      * Removes the first occurrence of the specified element in this
 599      * list (when traversing the list from head to tail).  If the list
 600      * does not contain the element, it is unchanged.
 601      *
 602      * @param o element to be removed from this list, if present
 603      * @return <tt>true</tt> if the list contained the specified element
 604      * @since 1.6
 605      */
 606     public boolean removeFirstOccurrence(Object o) {
 607         return remove(o);
 608     }
 609 
 610     /**
 611      * Removes the last occurrence of the specified element in this
 612      * list (when traversing the list from head to tail).  If the list
 613      * does not contain the element, it is unchanged.
 614      *
 615      * @param o element to be removed from this list, if present
 616      * @return <tt>true</tt> if the list contained the specified element
 617      * @since 1.6
 618      */
 619     public boolean removeLastOccurrence(Object o) {
 620         for (Entry<E> e = header.previous; e != header; e = e.previous) {
 621             if (o == e.element) {
 622                 remove(e);
 623                 return true;
 624             }
 625         }
 626         return false;
 627     }
 628 
 629     /**
 630      * Returns a list-iterator of the elements in this list (in proper
 631      * sequence), starting at the specified position in the list.
 632      * Obeys the general contract of <tt>List.listIterator(int)</tt>.<p>
 633      *
 634      * The list-iterator is <i>fail-fast</i>: if the list is structurally
 635      * modified at any time after the Iterator is created, in any way except
 636      * through the list-iterator's own <tt>remove</tt> or <tt>add</tt>
 637      * methods, the list-iterator will throw a
 638      * <tt>ConcurrentModificationException</tt>.  Thus, in the face of
 639      * concurrent modification, the iterator fails quickly and cleanly, rather
 640      * than risking arbitrary, non-deterministic behavior at an undetermined
 641      * time in the future.
 642      *
 643      * @param index index of the first element to be returned from the
 644      *              list-iterator (by a call to <tt>next</tt>)
 645      * @return a ListIterator of the elements in this list (in proper
 646      *         sequence), starting at the specified position in the list
 647      * @throws IndexOutOfBoundsException {@inheritDoc}
 648      * @see List#listIterator(int)
 649      */
 650     public ListIterator<E> listIterator(int index) {
 651         return new ListItr(index);
 652     }
 653 
 654     private class ListItr implements ListIterator<E> {
 655         private Entry<E> lastReturned = header;
 656         private Entry<E> next;
 657         private int nextIndex;
 658         private int expectedModCount = modCount;
 659 
 660         ListItr(int index) {
 661             if (index < 0 || index > size)
 662                 throw new IndexOutOfBoundsException("Index: "+index+
 663                                                     ", Size: "+size);
 664             if (index < (size >> 1)) {
 665                 next = header.next;
 666                 for (nextIndex=0; nextIndex<index; nextIndex++)
 667                     next = next.next;
 668             } else {
 669                 next = header;
 670                 for (nextIndex=size; nextIndex>index; nextIndex--)
 671                     next = next.previous;
 672             }
 673         }
 674 
 675         public boolean hasNext() {
 676             return nextIndex != size;
 677         }
 678 
 679         public E next() {
 680             checkForComodification();
 681             if (nextIndex == size)
 682                 throw new NoSuchElementException();
 683 
 684             lastReturned = next;
 685             next = next.next;
 686             nextIndex++;
 687             return lastReturned.element;
 688         }
 689 
 690         public boolean hasPrevious() {
 691             return nextIndex != 0;
 692         }
 693 
 694         public E previous() {
 695             if (nextIndex == 0)
 696                 throw new NoSuchElementException();
 697 
 698             lastReturned = next = next.previous;
 699             nextIndex--;
 700             checkForComodification();
 701             return lastReturned.element;
 702         }
 703 
 704         public int nextIndex() {
 705             return nextIndex;
 706         }
 707 
 708         public int previousIndex() {
 709             return nextIndex-1;
 710         }
 711 
 712         public void remove() {
 713             checkForComodification();
 714             Entry<E> lastNext = lastReturned.next;
 715             try {
 716                 IdentityLinkedList.this.remove(lastReturned);
 717             } catch (NoSuchElementException e) {
 718                 throw new IllegalStateException();
 719             }
 720             if (next==lastReturned)
 721                 next = lastNext;
 722             else
 723                 nextIndex--;
 724             lastReturned = header;
 725             expectedModCount++;
 726         }
 727 
 728         public void set(E e) {
 729             if (lastReturned == header)
 730                 throw new IllegalStateException();
 731             checkForComodification();
 732             lastReturned.element = e;
 733         }
 734 
 735         public void add(E e) {
 736             checkForComodification();
 737             lastReturned = header;
 738             addBefore(e, next);
 739             nextIndex++;
 740             expectedModCount++;
 741         }
 742 
 743         final void checkForComodification() {
 744             if (modCount != expectedModCount)
 745                 throw new ConcurrentModificationException();
 746         }
 747     }
 748 
 749     private static class Entry<E> {
 750         E element;
 751         Entry<E> next;
 752         Entry<E> previous;
 753 
 754         Entry(E element, Entry<E> next, Entry<E> previous) {
 755             this.element = element;
 756             this.next = next;
 757             this.previous = previous;
 758         }
 759     }
 760 
 761     private Entry<E> addBefore(E e, Entry<E> entry) {
 762         Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
 763         newEntry.previous.next = newEntry;
 764         newEntry.next.previous = newEntry;
 765         size++;
 766         modCount++;
 767         return newEntry;
 768     }
 769 
 770     private E remove(Entry<E> e) {
 771         if (e == header)
 772             throw new NoSuchElementException();
 773 
 774         E result = e.element;
 775         e.previous.next = e.next;
 776         e.next.previous = e.previous;
 777         e.next = e.previous = null;
 778         e.element = null;
 779         size--;
 780         modCount++;
 781         return result;
 782     }
 783 
 784     /**
 785      * @since 1.6
 786      */
 787     public Iterator<E> descendingIterator() {
 788         return new DescendingIterator();
 789     }
 790 
 791     /** Adapter to provide descending iterators via ListItr.previous */
 792     private class DescendingIterator implements Iterator<E> {
 793         final ListItr itr = new ListItr(size());
 794         public boolean hasNext() {
 795             return itr.hasPrevious();
 796         }
 797         public E next() {
 798             return itr.previous();
 799         }
 800         public void remove() {
 801             itr.remove();
 802         }
 803     }
 804 
 805     /**
 806      * Returns an array containing all of the elements in this list
 807      * in proper sequence (from first to last element).
 808      *
 809      * <p>The returned array will be "safe" in that no references to it are
 810      * maintained by this list.  (In other words, this method must allocate
 811      * a new array).  The caller is thus free to modify the returned array.
 812      *
 813      * <p>This method acts as bridge between array-based and collection-based
 814      * APIs.
 815      *
 816      * @return an array containing all of the elements in this list
 817      *         in proper sequence
 818      */
 819     public Object[] toArray() {
 820         Object[] result = new Object[size];
 821         int i = 0;
 822         for (Entry<E> e = header.next; e != header; e = e.next)
 823             result[i++] = e.element;
 824         return result;
 825     }
 826 
 827     /**
 828      * Returns an array containing all of the elements in this list in
 829      * proper sequence (from first to last element); the runtime type of
 830      * the returned array is that of the specified array.  If the list fits
 831      * in the specified array, it is returned therein.  Otherwise, a new
 832      * array is allocated with the runtime type of the specified array and
 833      * the size of this list.
 834      *
 835      * <p>If the list fits in the specified array with room to spare (i.e.,
 836      * the array has more elements than the list), the element in the array
 837      * immediately following the end of the list is set to <tt>null</tt>.
 838      * (This is useful in determining the length of the list <i>only</i> if
 839      * the caller knows that the list does not contain any null elements.)
 840      *
 841      * <p>Like the {@link #toArray()} method, this method acts as bridge between
 842      * array-based and collection-based APIs.  Further, this method allows
 843      * precise control over the runtime type of the output array, and may,
 844      * under certain circumstances, be used to save allocation costs.
 845      *
 846      * <p>Suppose <tt>x</tt> is a list known to contain only strings.
 847      * The following code can be used to dump the list into a newly
 848      * allocated array of <tt>String</tt>:
 849      *
 850      * <pre>
 851      *     String[] y = x.toArray(new String[0]);</pre>
 852      *
 853      * Note that <tt>toArray(new Object[0])</tt> is identical in function to
 854      * <tt>toArray()</tt>.
 855      *
 856      * @param a the array into which the elements of the list are to
 857      *          be stored, if it is big enough; otherwise, a new array of the
 858      *          same runtime type is allocated for this purpose.
 859      * @return an array containing the elements of the list
 860      * @throws ArrayStoreException if the runtime type of the specified array
 861      *         is not a supertype of the runtime type of every element in
 862      *         this list
 863      * @throws NullPointerException if the specified array is null
 864      */
 865     @SuppressWarnings("unchecked")
 866     public <T> T[] toArray(T[] a) {
 867         if (a.length < size)
 868             a = (T[])java.lang.reflect.Array.newInstance(
 869                                 a.getClass().getComponentType(), size);
 870         int i = 0;
 871         Object[] result = a;
 872         for (Entry<E> e = header.next; e != header; e = e.next)
 873             result[i++] = e.element;
 874 
 875         if (a.length > size)
 876             a[size] = null;
 877 
 878         return a;
 879     }
 880 }