Source for java.util.LinkedList

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