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    
004    This file is part of GNU Classpath.
005    
006    GNU Classpath is free software; you can redistribute it and/or modify
007    it under the terms of the GNU General Public License as published by
008    the Free Software Foundation; either version 2, or (at your option)
009    any later version.
010    
011    GNU Classpath is distributed in the hope that it will be useful, but
012    WITHOUT ANY WARRANTY; without even the implied warranty of
013    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014    General Public License for more details.
015    
016    You should have received a copy of the GNU General Public License
017    along with GNU Classpath; see the file COPYING.  If not, write to the
018    Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
019    02110-1301 USA.
020    
021    Linking this library statically or dynamically with other modules is
022    making a combined work based on this library.  Thus, the terms and
023    conditions of the GNU General Public License cover the whole
024    combination.
025    
026    As a special exception, the copyright holders of this library give you
027    permission to link this library with independent modules to produce an
028    executable, regardless of the license terms of these independent
029    modules, and to copy and distribute the resulting executable under
030    terms of your choice, provided that you also meet, for each linked
031    independent module, the terms and conditions of the license of that
032    module.  An independent module is a module which is not derived from
033    or based on this library.  If you modify this library, you may extend
034    this exception to your version of the library, but you are not
035    obligated to do so.  If you do not wish to do so, delete this
036    exception statement from your version. */
037    
038    
039    package java.util;
040    import java.io.IOException;
041    import java.io.ObjectInputStream;
042    import java.io.ObjectOutputStream;
043    import java.io.Serializable;
044    import 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     */
076    public 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    }