001/* LinkedList.java -- Linked list implementation of the List interface
002   Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005, 2006  Free Software Foundation, Inc.
003
004This file is part of GNU Classpath.
005
006GNU Classpath is free software; you can redistribute it and/or modify
007it under the terms of the GNU General Public License as published by
008the Free Software Foundation; either version 2, or (at your option)
009any later version.
010
011GNU Classpath is distributed in the hope that it will be useful, but
012WITHOUT ANY WARRANTY; without even the implied warranty of
013MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014General Public License for more details.
015
016You should have received a copy of the GNU General Public License
017along with GNU Classpath; see the file COPYING.  If not, write to the
018Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
01902110-1301 USA.
020
021Linking this library statically or dynamically with other modules is
022making a combined work based on this library.  Thus, the terms and
023conditions of the GNU General Public License cover the whole
024combination.
025
026As a special exception, the copyright holders of this library give you
027permission to link this library with independent modules to produce an
028executable, regardless of the license terms of these independent
029modules, and to copy and distribute the resulting executable under
030terms of your choice, provided that you also meet, for each linked
031independent module, the terms and conditions of the license of that
032module.  An independent module is a module which is not derived from
033or based on this library.  If you modify this library, you may extend
034this exception to your version of the library, but you are not
035obligated to do so.  If you do not wish to do so, delete this
036exception statement from your version. */
037
038
039package java.util;
040import java.io.IOException;
041import java.io.ObjectInputStream;
042import java.io.ObjectOutputStream;
043import java.io.Serializable;
044import java.lang.reflect.Array;
045
046/**
047 * Linked list implementation of the List interface. In addition to the
048 * methods of the List interface, this class provides access to the first
049 * and last list elements in O(1) time for easy stack, queue, or double-ended
050 * queue (deque) creation. The list is doubly-linked, with traversal to a
051 * given index starting from the end closest to the element.<p>
052 *
053 * LinkedList is not synchronized, so if you need multi-threaded access,
054 * consider using:<br>
055 * <code>List l = Collections.synchronizedList(new LinkedList(...));</code>
056 * <p>
057 *
058 * The iterators are <i>fail-fast</i>, meaning that any structural
059 * modification, except for <code>remove()</code> called on the iterator
060 * itself, cause the iterator to throw a
061 * {@link ConcurrentModificationException} rather than exhibit
062 * non-deterministic behavior.
063 *
064 * @author Original author unknown
065 * @author Bryce McKinlay
066 * @author Eric Blake (ebb9@email.byu.edu)
067 * @author Tom Tromey (tromey@redhat.com)
068 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
069 * @see List
070 * @see ArrayList
071 * @see Vector
072 * @see Collections#synchronizedList(List)
073 * @since 1.2
074 * @status Complete to 1.6
075 */
076public class LinkedList<T> extends AbstractSequentialList<T>
077  implements List<T>, Deque<T>, Cloneable, Serializable
078{
079  /**
080   * Compatible with JDK 1.2.
081   */
082  private static final long serialVersionUID = 876323262645176354L;
083
084  /**
085   * The first element in the list.
086   */
087  transient Entry<T> first;
088
089  /**
090   * The last element in the list.
091   */
092  transient Entry<T> last;
093
094  /**
095   * The current length of the list.
096   */
097  transient int size = 0;
098
099  /**
100   * Class to represent an entry in the list. Holds a single element.
101   */
102  private static final class Entry<T>
103  {
104    /** The element in the list. */
105    T data;
106
107    /** The next list entry, null if this is last. */
108    Entry<T> next;
109
110    /** The previous list entry, null if this is first. */
111    Entry<T> previous;
112
113    /**
114     * Construct an entry.
115     * @param data the list element
116     */
117    Entry(T data)
118    {
119      this.data = data;
120    }
121  } // class Entry
122
123  /**
124   * Obtain the Entry at a given position in a list. This method of course
125   * takes linear time, but it is intelligent enough to take the shorter of the
126   * paths to get to the Entry required. This implies that the first or last
127   * entry in the list is obtained in constant time, which is a very desirable
128   * property.
129   * For speed and flexibility, range checking is not done in this method:
130   * Incorrect values will be returned if (n &lt; 0) or (n &gt;= size).
131   *
132   * @param n the number of the entry to get
133   * @return the entry at position n
134   */
135  // Package visible for use in nested classes.
136  Entry<T> getEntry(int n)
137  {
138    Entry<T> e;
139    if (n < size / 2)
140      {
141        e = first;
142        // n less than size/2, iterate from start
143        while (n-- > 0)
144          e = e.next;
145      }
146    else
147      {
148        e = last;
149        // n greater than size/2, iterate from end
150        while (++n < size)
151          e = e.previous;
152      }
153    return e;
154  }
155
156  /**
157   * Remove an entry from the list. This will adjust size and deal with
158   *  `first' and  `last' appropriatly.
159   *
160   * @param e the entry to remove
161   */
162  // Package visible for use in nested classes.
163  void removeEntry(Entry<T> e)
164  {
165    modCount++;
166    size--;
167    if (size == 0)
168      first = last = null;
169    else
170      {
171        if (e == first)
172          {
173            first = e.next;
174            e.next.previous = null;
175          }
176        else if (e == last)
177          {
178            last = e.previous;
179            e.previous.next = null;
180          }
181        else
182          {
183            e.next.previous = e.previous;
184            e.previous.next = e.next;
185          }
186      }
187  }
188
189  /**
190   * Checks that the index is in the range of possible elements (inclusive).
191   *
192   * @param index the index to check
193   * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size
194   */
195  private void checkBoundsInclusive(int index)
196  {
197    if (index < 0 || index > size)
198      throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
199                                          + size);
200  }
201
202  /**
203   * Checks that the index is in the range of existing elements (exclusive).
204   *
205   * @param index the index to check
206   * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size
207   */
208  private void checkBoundsExclusive(int index)
209  {
210    if (index < 0 || index >= size)
211      throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
212                                          + size);
213  }
214
215  /**
216   * Create an empty linked list.
217   */
218  public LinkedList()
219  {
220  }
221
222  /**
223   * Create a linked list containing the elements, in order, of a given
224   * collection.
225   *
226   * @param c the collection to populate this list from
227   * @throws NullPointerException if c is null
228   */
229  public LinkedList(Collection<? extends T> c)
230  {
231    addAll(c);
232  }
233
234  /**
235   * Returns the first element in the list.
236   *
237   * @return the first list element
238   * @throws NoSuchElementException if the list is empty
239   */
240  public T getFirst()
241  {
242    if (size == 0)
243      throw new NoSuchElementException();
244    return first.data;
245  }
246
247  /**
248   * Returns the last element in the list.
249   *
250   * @return the last list element
251   * @throws NoSuchElementException if the list is empty
252   */
253  public T getLast()
254  {
255    if (size == 0)
256      throw new NoSuchElementException();
257    return last.data;
258  }
259
260  /**
261   * Remove and return the first element in the list.
262   *
263   * @return the former first element in the list
264   * @throws NoSuchElementException if the list is empty
265   */
266  public T removeFirst()
267  {
268    if (size == 0)
269      throw new NoSuchElementException();
270    modCount++;
271    size--;
272    T r = first.data;
273
274    if (first.next != null)
275      first.next.previous = null;
276    else
277      last = null;
278
279    first = first.next;
280
281    return r;
282  }
283
284  /**
285   * Remove and return the last element in the list.
286   *
287   * @return the former last element in the list
288   * @throws NoSuchElementException if the list is empty
289   */
290  public T removeLast()
291  {
292    if (size == 0)
293      throw new NoSuchElementException();
294    modCount++;
295    size--;
296    T r = last.data;
297
298    if (last.previous != null)
299      last.previous.next = null;
300    else
301      first = null;
302
303    last = last.previous;
304
305    return r;
306  }
307
308  /**
309   * Insert an element at the first of the list.
310   *
311   * @param o the element to insert
312   */
313  public void addFirst(T o)
314  {
315    Entry<T> e = new Entry(o);
316
317    modCount++;
318    if (size == 0)
319      first = last = e;
320    else
321      {
322        e.next = first;
323        first.previous = e;
324        first = e;
325      }
326    size++;
327  }
328
329  /**
330   * Insert an element at the last of the list.
331   *
332   * @param o the element to insert
333   */
334  public void addLast(T o)
335  {
336    addLastEntry(new Entry<T>(o));
337  }
338
339  /**
340   * Inserts an element at the end of the list.
341   *
342   * @param e the entry to add
343   */
344  private void addLastEntry(Entry<T> e)
345  {
346    modCount++;
347    if (size == 0)
348      first = last = e;
349    else
350      {
351        e.previous = last;
352        last.next = e;
353        last = e;
354      }
355    size++;
356  }
357
358  /**
359   * Returns true if the list contains the given object. Comparison is done by
360   * <code>o == null ? e = null : o.equals(e)</code>.
361   *
362   * @param o the element to look for
363   * @return true if it is found
364   */
365  public boolean contains(Object o)
366  {
367    Entry<T> e = first;
368    while (e != null)
369      {
370        if (equals(o, e.data))
371          return true;
372        e = e.next;
373      }
374    return false;
375  }
376
377  /**
378   * Returns the size of the list.
379   *
380   * @return the list size
381   */
382  public int size()
383  {
384    return size;
385  }
386
387  /**
388   * Adds an element to the end of the list.
389   *
390   * @param o the entry to add
391   * @return true, as it always succeeds
392   */
393  public boolean add(T o)
394  {
395    addLastEntry(new Entry<T>(o));
396    return true;
397  }
398
399  /**
400   * Removes the entry at the lowest index in the list that matches the given
401   * object, comparing by <code>o == null ? e = null : o.equals(e)</code>.
402   *
403   * @param o the object to remove
404   * @return true if an instance of the object was removed
405   */
406  public boolean remove(Object o)
407  {
408    Entry<T> e = first;
409    while (e != null)
410      {
411        if (equals(o, e.data))
412          {
413            removeEntry(e);
414            return true;
415          }
416        e = e.next;
417      }
418    return false;
419  }
420
421  /**
422   * Append the elements of the collection in iteration order to the end of
423   * this list. If this list is modified externally (for example, if this
424   * list is the collection), behavior is unspecified.
425   *
426   * @param c the collection to append
427   * @return true if the list was modified
428   * @throws NullPointerException if c is null
429   */
430  public boolean addAll(Collection<? extends T> c)
431  {
432    return addAll(size, c);
433  }
434
435  /**
436   * Insert the elements of the collection in iteration order at the given
437   * index of this list. If this list is modified externally (for example,
438   * if this list is the collection), behavior is unspecified.
439   *
440   * @param c the collection to append
441   * @return true if the list was modified
442   * @throws NullPointerException if c is null
443   * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
444   */
445  public boolean addAll(int index, Collection<? extends T> c)
446  {
447    checkBoundsInclusive(index);
448    int csize = c.size();
449
450    if (csize == 0)
451      return false;
452
453    Iterator<? extends T> itr = c.iterator();
454
455    // Get the entries just before and after index. If index is at the start
456    // of the list, BEFORE is null. If index is at the end of the list, AFTER
457    // is null. If the list is empty, both are null.
458    Entry<T> after = null;
459    Entry<T> before = null;
460    if (index != size)
461      {
462        after = getEntry(index);
463        before = after.previous;
464      }
465    else
466      before = last;
467
468    // Create the first new entry. We do not yet set the link from `before'
469    // to the first entry, in order to deal with the case where (c == this).
470    // [Actually, we don't have to handle this case to fufill the
471    // contract for addAll(), but Sun's implementation appears to.]
472    Entry<T> e = new Entry<T>(itr.next());
473    e.previous = before;
474    Entry<T> prev = e;
475    Entry<T> firstNew = e;
476
477    // Create and link all the remaining entries.
478    for (int pos = 1; pos < csize; pos++)
479      {
480        e = new Entry<T>(itr.next());
481        e.previous = prev;
482        prev.next = e;
483        prev = e;
484      }
485
486    // Link the new chain of entries into the list.
487    modCount++;
488    size += csize;
489    prev.next = after;
490    if (after != null)
491      after.previous = e;
492    else
493      last = e;
494
495    if (before != null)
496      before.next = firstNew;
497    else
498      first = firstNew;
499    return true;
500  }
501
502  /**
503   * Remove all elements from this list.
504   */
505  public void clear()
506  {
507    if (size > 0)
508      {
509        modCount++;
510        first = null;
511        last = null;
512        size = 0;
513      }
514  }
515
516  /**
517   * Return the element at index.
518   *
519   * @param index the place to look
520   * @return the element at index
521   * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
522   */
523  public T get(int index)
524  {
525    checkBoundsExclusive(index);
526    return getEntry(index).data;
527  }
528
529  /**
530   * Replace the element at the given location in the list.
531   *
532   * @param index which index to change
533   * @param o the new element
534   * @return the prior element
535   * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
536   */
537  public T set(int index, T o)
538  {
539    checkBoundsExclusive(index);
540    Entry<T> e = getEntry(index);
541    T old = e.data;
542    e.data = o;
543    return old;
544  }
545
546  /**
547   * Inserts an element in the given position in the list.
548   *
549   * @param index where to insert the element
550   * @param o the element to insert
551   * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
552   */
553  public void add(int index, T o)
554  {
555    checkBoundsInclusive(index);
556    Entry<T> e = new Entry<T>(o);
557
558    if (index < size)
559      {
560        modCount++;
561        Entry<T> after = getEntry(index);
562        e.next = after;
563        e.previous = after.previous;
564        if (after.previous == null)
565          first = e;
566        else
567          after.previous.next = e;
568        after.previous = e;
569        size++;
570      }
571    else
572      addLastEntry(e);
573  }
574
575  /**
576   * Removes the element at the given position from the list.
577   *
578   * @param index the location of the element to remove
579   * @return the removed element
580   * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
581   */
582  public T remove(int index)
583  {
584    checkBoundsExclusive(index);
585    Entry<T> e = getEntry(index);
586    removeEntry(e);
587    return e.data;
588  }
589
590  /**
591   * Returns the first index where the element is located in the list, or -1.
592   *
593   * @param o the element to look for
594   * @return its position, or -1 if not found
595   */
596  public int indexOf(Object o)
597  {
598    int index = 0;
599    Entry<T> e = first;
600    while (e != null)
601      {
602        if (equals(o, e.data))
603          return index;
604        index++;
605        e = e.next;
606      }
607    return -1;
608  }
609
610  /**
611   * Returns the last index where the element is located in the list, or -1.
612   *
613   * @param o the element to look for
614   * @return its position, or -1 if not found
615   */
616  public int lastIndexOf(Object o)
617  {
618    int index = size - 1;
619    Entry<T> e = last;
620    while (e != null)
621      {
622        if (equals(o, e.data))
623          return index;
624        index--;
625        e = e.previous;
626      }
627    return -1;
628  }
629
630  /**
631   * Obtain a ListIterator over this list, starting at a given index. The
632   * ListIterator returned by this method supports the add, remove and set
633   * methods.
634   *
635   * @param index the index of the element to be returned by the first call to
636   *        next(), or size() to be initially positioned at the end of the list
637   * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
638   */
639  public ListIterator<T> listIterator(int index)
640  {
641    checkBoundsInclusive(index);
642    return new LinkedListItr<T>(index);
643  }
644
645  /**
646   * Create a shallow copy of this LinkedList (the elements are not cloned).
647   *
648   * @return an object of the same class as this object, containing the
649   *         same elements in the same order
650   */
651  public Object clone()
652  {
653    LinkedList<T> copy = null;
654    try
655      {
656        copy = (LinkedList<T>) super.clone();
657      }
658    catch (CloneNotSupportedException ex)
659      {
660      }
661    copy.clear();
662    copy.addAll(this);
663    return copy;
664  }
665
666  /**
667   * Returns an array which contains the elements of the list in order.
668   *
669   * @return an array containing the list elements
670   */
671  public Object[] toArray()
672  {
673    Object[] array = new Object[size];
674    Entry<T> e = first;
675    for (int i = 0; i < size; i++)
676      {
677        array[i] = e.data;
678        e = e.next;
679      }
680    return array;
681  }
682
683  /**
684   * Returns an Array whose component type is the runtime component type of
685   * the passed-in Array.  The returned Array is populated with all of the
686   * elements in this LinkedList.  If the passed-in Array is not large enough
687   * to store all of the elements in this List, a new Array will be created 
688   * and returned; if the passed-in Array is <i>larger</i> than the size
689   * of this List, then size() index will be set to null.
690   *
691   * @param a the passed-in Array
692   * @return an array representation of this list
693   * @throws ArrayStoreException if the runtime type of a does not allow
694   *         an element in this list
695   * @throws NullPointerException if a is null
696   */
697  public <S> S[] toArray(S[] a)
698  {
699    if (a.length < size)
700      a = (S[]) Array.newInstance(a.getClass().getComponentType(), size);
701    else if (a.length > size)
702      a[size] = null;
703    Entry<T> e = first;
704    for (int i = 0; i < size; i++)
705      {
706        a[i] = (S) e.data;
707        e = e.next;
708      }
709    return a;
710  }
711
712  /**
713   * Adds the specified element to the end of the list.
714   *
715   * @param value the value to add.
716   * @return true.
717   * @since 1.5
718   */
719  public boolean offer(T value)
720  {
721    return add(value);
722  }
723
724  /**
725   * Returns the first element of the list without removing
726   * it.
727   *
728   * @return the first element of the list.
729   * @throws NoSuchElementException if the list is empty.
730   * @since 1.5
731   */
732  public T element()
733  {
734    return getFirst();
735  }
736
737  /**
738   * Returns the first element of the list without removing
739   * it.
740   *
741   * @return the first element of the list, or <code>null</code>
742   *         if the list is empty.
743   * @since 1.5
744   */
745  public T peek()
746  {
747    if (size == 0)
748      return null;
749    return getFirst();
750  }
751
752  /**
753   * Removes and returns the first element of the list.
754   *
755   * @return the first element of the list, or <code>null</code>
756   *         if the list is empty.
757   * @since 1.5
758   */
759  public T poll()
760  {
761    if (size == 0)
762      return null;
763    return removeFirst();
764  }
765
766  /**
767   * Removes and returns the first element of the list.
768   *
769   * @return the first element of the list.
770   * @throws NoSuchElementException if the list is empty.
771   * @since 1.5
772   */
773  public T remove()
774  {
775    return removeFirst();
776  }
777
778  /**
779   * Serializes this object to the given stream.
780   *
781   * @param s the stream to write to
782   * @throws IOException if the underlying stream fails
783   * @serialData the size of the list (int), followed by all the elements
784   *             (Object) in proper order
785   */
786  private void writeObject(ObjectOutputStream s) throws IOException
787  {
788    s.defaultWriteObject();
789    s.writeInt(size);
790    Entry<T> e = first;
791    while (e != null)
792      {
793        s.writeObject(e.data);
794        e = e.next;
795      }
796  }
797
798  /**
799   * Deserializes this object from the given stream.
800   *
801   * @param s the stream to read from
802   * @throws ClassNotFoundException if the underlying stream fails
803   * @throws IOException if the underlying stream fails
804   * @serialData the size of the list (int), followed by all the elements
805   *             (Object) in proper order
806   */
807  private void readObject(ObjectInputStream s)
808    throws IOException, ClassNotFoundException
809  {
810    s.defaultReadObject();
811    int i = s.readInt();
812    while (--i >= 0)
813      addLastEntry(new Entry<T>((T) s.readObject()));
814  }
815
816  /**
817   * A ListIterator over the list. This class keeps track of its
818   * position in the list and the two list entries it is between.
819   *
820   * @author Original author unknown
821   * @author Eric Blake (ebb9@email.byu.edu)
822   */
823  private final class LinkedListItr<I>
824    implements ListIterator<I>
825  {
826    /** Number of modifications we know about. */
827    private int knownMod = modCount;
828
829    /** Entry that will be returned by next(). */
830    private Entry<I> next;
831
832    /** Entry that will be returned by previous(). */
833    private Entry<I> previous;
834
835    /** Entry that will be affected by remove() or set(). */
836    private Entry<I> lastReturned;
837
838    /** Index of `next'. */
839    private int position;
840
841    /**
842     * Initialize the iterator.
843     *
844     * @param index the initial index
845     */
846    LinkedListItr(int index)
847    {
848      if (index == size)
849        {
850          next = null;
851          previous = (Entry<I>) last;
852        }
853      else
854        {
855          next = (Entry<I>) getEntry(index);
856          previous = next.previous;
857        }
858      position = index;
859    }
860
861    /**
862     * Checks for iterator consistency.
863     *
864     * @throws ConcurrentModificationException if the list was modified
865     */
866    private void checkMod()
867    {
868      if (knownMod != modCount)
869        throw new ConcurrentModificationException();
870    }
871
872    /**
873     * Returns the index of the next element.
874     *
875     * @return the next index
876     */
877    public int nextIndex()
878    {
879      return position;
880    }
881
882    /**
883     * Returns the index of the previous element.
884     *
885     * @return the previous index
886     */
887    public int previousIndex()
888    {
889      return position - 1;
890    }
891
892    /**
893     * Returns true if more elements exist via next.
894     *
895     * @return true if next will succeed
896     */
897    public boolean hasNext()
898    {
899      return (next != null);
900    }
901
902    /**
903     * Returns true if more elements exist via previous.
904     *
905     * @return true if previous will succeed
906     */
907    public boolean hasPrevious()
908    {
909      return (previous != null);
910    }
911
912    /**
913     * Returns the next element.
914     *
915     * @return the next element
916     * @throws ConcurrentModificationException if the list was modified
917     * @throws NoSuchElementException if there is no next
918     */
919    public I next()
920    {
921      checkMod();
922      if (next == null)
923        throw new NoSuchElementException();
924      position++;
925      lastReturned = previous = next;
926      next = lastReturned.next;
927      return lastReturned.data;
928    }
929
930    /**
931     * Returns the previous element.
932     *
933     * @return the previous element
934     * @throws ConcurrentModificationException if the list was modified
935     * @throws NoSuchElementException if there is no previous
936     */
937    public I previous()
938    {
939      checkMod();
940      if (previous == null)
941        throw new NoSuchElementException();
942      position--;
943      lastReturned = next = previous;
944      previous = lastReturned.previous;
945      return lastReturned.data;
946    }
947
948    /**
949     * Remove the most recently returned element from the list.
950     *
951     * @throws ConcurrentModificationException if the list was modified
952     * @throws IllegalStateException if there was no last element
953     */
954    public void remove()
955    {
956      checkMod();
957      if (lastReturned == null)
958        throw new IllegalStateException();
959
960      // Adjust the position to before the removed element, if the element
961      // being removed is behind the cursor.
962      if (lastReturned == previous)
963        position--;
964
965      next = lastReturned.next;
966      previous = lastReturned.previous;
967      removeEntry((Entry<T>) lastReturned);
968      knownMod++;
969
970      lastReturned = null;
971    }
972
973    /**
974     * Adds an element between the previous and next, and advance to the next.
975     *
976     * @param o the element to add
977     * @throws ConcurrentModificationException if the list was modified
978     */
979    public void add(I o)
980    {
981      checkMod();
982      modCount++;
983      knownMod++;
984      size++;
985      position++;
986      Entry<I> e = new Entry<I>(o);
987      e.previous = previous;
988      e.next = next;
989
990      if (previous != null)
991        previous.next = e;
992      else
993        first = (Entry<T>) e;
994
995      if (next != null)
996        next.previous = e;
997      else
998        last = (Entry<T>) e;
999
1000      previous = e;
1001      lastReturned = null;
1002    }
1003
1004    /**
1005     * Changes the contents of the element most recently returned.
1006     *
1007     * @param o the new element
1008     * @throws ConcurrentModificationException if the list was modified
1009     * @throws IllegalStateException if there was no last element
1010     */
1011    public void set(I o)
1012    {
1013      checkMod();
1014      if (lastReturned == null)
1015        throw new IllegalStateException();
1016      lastReturned.data = o;
1017    }
1018  } // class LinkedListItr
1019
1020  /**
1021   * Obtain an Iterator over this list in reverse sequential order.
1022   *
1023   * @return an Iterator over the elements of the list in
1024   *         reverse order.
1025   * @since 1.6
1026   */
1027  public Iterator<T> descendingIterator()
1028  {
1029    return new Iterator<T>()
1030    {
1031      /** Number of modifications we know about. */
1032      private int knownMod = modCount;
1033
1034      /** Entry that will be returned by next(). */
1035      private Entry<T> next = last;
1036
1037      /** Entry that will be affected by remove() or set(). */
1038      private Entry<T> lastReturned;
1039
1040      /** Index of `next'. */
1041      private int position = size() - 1;
1042
1043      // This will get inlined, since it is private.
1044      /**
1045       * Checks for modifications made to the list from
1046       * elsewhere while iteration is in progress.
1047       *
1048       * @throws ConcurrentModificationException if the
1049       *         list has been modified elsewhere.
1050       */
1051      private void checkMod()
1052      {
1053        if (knownMod != modCount)
1054          throw new ConcurrentModificationException();
1055      }
1056
1057      /**
1058       * Tests to see if there are any more objects to
1059       * return.
1060       *
1061       * @return true if the start of the list has not yet been
1062       *         reached.
1063       */
1064      public boolean hasNext()
1065      {
1066        return next != null;
1067      }
1068
1069      /**
1070       * Retrieves the next object from the list.
1071       *
1072       * @return The next object.
1073       * @throws NoSuchElementException if there are
1074       *         no more objects to retrieve.
1075       * @throws ConcurrentModificationException if the
1076       *         list has been modified elsewhere.
1077       */
1078      public T next()
1079      {
1080        checkMod();
1081        if (next == null)
1082          throw new NoSuchElementException();
1083        --position;
1084        lastReturned = next;
1085        next = lastReturned.previous;
1086        return lastReturned.data;
1087      }
1088
1089      /**
1090       * Removes the last object retrieved by <code>next()</code>
1091       * from the list, if the list supports object removal.
1092       *
1093       * @throws ConcurrentModificationException if the list
1094       *         has been modified elsewhere.
1095       * @throws IllegalStateException if the iterator is positioned
1096       *         before the start of the list or the last object has already
1097       *         been removed.
1098       */
1099      public void remove()
1100      {
1101        checkMod();
1102        if (lastReturned == null)
1103          throw new IllegalStateException();
1104        removeEntry(lastReturned);
1105        lastReturned = null;
1106        ++knownMod;
1107      }
1108    };
1109  }
1110
1111  /**
1112   * Inserts the specified element at the front of the list.
1113   *
1114   * @param value the element to insert.
1115   * @return true.
1116   * @since 1.6
1117   */
1118  public boolean offerFirst(T value)
1119  {
1120    addFirst(value);
1121    return true;
1122  }
1123
1124  /**
1125   * Inserts the specified element at the end of the list.
1126   *
1127   * @param value the element to insert.
1128   * @return true.
1129   * @since 1.6
1130   */
1131  public boolean offerLast(T value)
1132  {
1133    return add(value);
1134  }
1135
1136  /**
1137   * Returns the first element of the list without removing
1138   * it.
1139   *
1140   * @return the first element of the list, or <code>null</code>
1141   *         if the list is empty.
1142   * @since 1.6
1143   */
1144  public T peekFirst()
1145  {
1146    return peek();
1147  }
1148
1149  /**
1150   * Returns the last element of the list without removing
1151   * it.
1152   *
1153   * @return the last element of the list, or <code>null</code>
1154   *         if the list is empty.
1155   * @since 1.6
1156   */
1157  public T peekLast()
1158  {
1159    if (size == 0)
1160      return null;
1161    return getLast();
1162  }
1163
1164  /**
1165   * Removes and returns the first element of the list.
1166   *
1167   * @return the first element of the list, or <code>null</code>
1168   *         if the list is empty.
1169   * @since 1.6
1170   */
1171  public T pollFirst()
1172  {
1173    return poll();
1174  }
1175
1176  /**
1177   * Removes and returns the last element of the list.
1178   *
1179   * @return the last element of the list, or <code>null</code>
1180   *         if the list is empty.
1181   * @since 1.6
1182   */
1183  public T pollLast()
1184  {
1185    if (size == 0)
1186      return null;
1187    return removeLast();
1188  }
1189
1190  /**
1191   * Pops an element from the stack by removing and returning
1192   * the first element in the list.  This is equivalent to
1193   * calling {@link #removeFirst()}.
1194   *
1195   * @return the top of the stack, which is the first element
1196   *         of the list.
1197   * @throws NoSuchElementException if the list is empty.
1198   * @since 1.6
1199   * @see #removeFirst()
1200   */
1201  public T pop()
1202  {
1203    return removeFirst();
1204  }
1205
1206  /**
1207   * Pushes an element on to the stack by adding it to the
1208   * front of the list.  This is equivalent to calling
1209   * {@link #addFirst(T)}.
1210   *
1211   * @param value the element to push on to the stack.
1212   * @throws NoSuchElementException if the list is empty.
1213   * @since 1.6
1214   * @see #addFirst(T)
1215   */
1216  public void push(T value)
1217  {
1218    addFirst(value);
1219  }
1220  
1221  /**
1222   * Removes the first occurrence of the specified element
1223   * from the list, when traversing the list from head to
1224   * tail.  The list is unchanged if the element is not found.
1225   * This is equivalent to calling {@link #remove(Object)}.
1226   *
1227   * @param o the element to remove.
1228   * @return true if an instance of the object was removed.
1229   * @since 1.6
1230   */
1231  public boolean removeFirstOccurrence(Object o)
1232  {
1233    return remove(o);
1234  }
1235
1236  /**
1237   * Removes the last occurrence of the specified element
1238   * from the list, when traversing the list from head to
1239   * tail.  The list is unchanged if the element is not found.
1240   *
1241   * @param o the element to remove.
1242   * @return true if an instance of the object was removed.
1243   * @since 1.6
1244   */
1245  public boolean removeLastOccurrence(Object o)
1246  {
1247    Entry<T> e = last;
1248    while (e != null)
1249      {
1250        if (equals(o, e.data))
1251          {
1252            removeEntry(e);
1253            return true;
1254          }
1255        e = e.previous;
1256      }
1257    return false;
1258  }
1259
1260}