libjava/classpath/java/util/LinkedList.java

   1 /* LinkedList.java -- Linked list implementation of the List interface
   2    Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005, 2006  Free Software Foundation, Inc.
   3
   4 This file is part of GNU Classpath.
   5
   6 GNU Classpath is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU Classpath is distributed in the hope that it will be useful, but
  12 WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU Classpath; see the file COPYING.  If not, write to the
  18 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  19 02110-1301 USA.
  20
  21 Linking this library statically or dynamically with other modules is
  22 making a combined work based on this library.  Thus, the terms and
  23 conditions of the GNU General Public License cover the whole
  24 combination.
  25
  26 As a special exception, the copyright holders of this library give you
  27 permission to link this library with independent modules to produce an
  28 executable, regardless of the license terms of these independent
  29 modules, and to copy and distribute the resulting executable under
  30 terms of your choice, provided that you also meet, for each linked
  31 independent module, the terms and conditions of the license of that
  32 module.  An independent module is a module which is not derived from
  33 or based on this library.  If you modify this library, you may extend
  34 this exception to your version of the library, but you are not
  35 obligated to do so.  If you do not wish to do so, delete this
  36 exception statement from your version. */
  37
  38
  39 package java.util;
  40 import java.io.IOException;
  41 import java.io.ObjectInputStream;
  42 import java.io.ObjectOutputStream;
  43 import java.io.Serializable;
  44 import java.lang.reflect.Array;
  45
  46 /**
  47  * Linked list implementation of the List interface. In addition to the
  48  * methods of the List interface, this class provides access to the first
  49  * and last list elements in O(1) time for easy stack, queue, or double-ended
  50  * queue (deque) creation. The list is doubly-linked, with traversal to a
  51  * given index starting from the end closest to the element.<p>
  52  *
  53  * LinkedList is not synchronized, so if you need multi-threaded access,
  54  * consider using:<br>
  55  * <code>List l = Collections.synchronizedList(new LinkedList(...));</code>
  56  * <p>
  57  *
  58  * The iterators are <i>fail-fast</i>, meaning that any structural
  59  * modification, except for <code>remove()</code> called on the iterator
  60  * itself, cause the iterator to throw a
  61  * {@link ConcurrentModificationException} rather than exhibit
  62  * non-deterministic behavior.
  63  *
  64  * @author Original author unknown
  65  * @author Bryce McKinlay
  66  * @author Eric Blake (ebb9@email.byu.edu)
  67  * @author Tom Tromey (tromey@redhat.com)
  68  * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
  69  * @see List
  70  * @see ArrayList
  71  * @see Vector
  72  * @see Collections#synchronizedList(List)
  73  * @since 1.2
  74  * @status Complete to 1.6
  75  */
  76 public class LinkedList<T> extends AbstractSequentialList<T>
  77   implements List<T>, Deque<T>, Cloneable, Serializable
  78 {
  79   /**
  80    * Compatible with JDK 1.2.
  81    */
  82   private static final long serialVersionUID = 876323262645176354L;
  83
  84   /**
  85    * The first element in the list.
  86    */
  87   transient Entry<T> first;
  88
  89   /**
  90    * The last element in the list.
  91    */
  92   transient Entry<T> last;
  93
  94   /**
  95    * The current length of the list.
  96    */
  97   transient int size = 0;
  98
  99   /**
 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 }