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 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 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

 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 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     /**

  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

 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     /**