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  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:  * @see List
  68:  * @see ArrayList
  69:  * @see Vector
  70:  * @see Collections#synchronizedList(List)
  71:  * @since 1.2
  72:  * @status missing javadoc, but complete to 1.4
  73:  */
  74: public class LinkedList extends AbstractSequentialList
  75:   implements List, Cloneable, Serializable
  76: {
  77:   /**
  78:    * Compatible with JDK 1.2.
  79:    */
  80:   private static final long serialVersionUID = 876323262645176354L;
  81: 
  82:   /**
  83:    * The first element in the list.
  84:    */
  85:   transient Entry first;
  86: 
  87:   /**
  88:    * The last element in the list.
  89:    */
  90:   transient Entry last;
  91: 
  92:   /**
  93:    * The current length of the list.
  94:    */
  95:   transient int size = 0;
  96: 
  97:   /**
  98:    * Class to represent an entry in the list. Holds a single element.
  99:    */
 100:   private static final class Entry
 101:   {
 102:     /** The element in the list. */
 103:     Object data;
 104: 
 105:     /** The next list entry, null if this is last. */
 106:     Entry next;
 107: 
 108:     /** The previous list entry, null if this is first. */
 109:     Entry previous;
 110: 
 111:     /**
 112:      * Construct an entry.
 113:      * @param data the list element
 114:      */
 115:     Entry(Object data)
 116:     {
 117:       this.data = data;
 118:     }
 119:   } // class Entry
 120: 
 121:   /**
 122:    * Obtain the Entry at a given position in a list. This method of course
 123:    * takes linear time, but it is intelligent enough to take the shorter of the
 124:    * paths to get to the Entry required. This implies that the first or last
 125:    * entry in the list is obtained in constant time, which is a very desirable
 126:    * property.
 127:    * For speed and flexibility, range checking is not done in this method:
 128:    * Incorrect values will be returned if (n &lt; 0) or (n &gt;= size).
 129:    *
 130:    * @param n the number of the entry to get
 131:    * @return the entry at position n
 132:    */
 133:   // Package visible for use in nested classes.
 134:   Entry getEntry(int n)
 135:   {
 136:     Entry e;
 137:     if (n < size / 2)
 138:       {
 139:         e = first;
 140:         // n less than size/2, iterate from start
 141:         while (n-- > 0)
 142:           e = e.next;
 143:       }
 144:     else
 145:       {
 146:         e = last;
 147:         // n greater than size/2, iterate from end
 148:         while (++n < size)
 149:           e = e.previous;
 150:       }
 151:     return e;
 152:   }
 153: 
 154:   /**
 155:    * Remove an entry from the list. This will adjust size and deal with
 156:    *  `first' and  `last' appropriatly.
 157:    *
 158:    * @param e the entry to remove
 159:    */
 160:   // Package visible for use in nested classes.
 161:   void removeEntry(Entry e)
 162:   {
 163:     modCount++;
 164:     size--;
 165:     if (size == 0)
 166:       first = last = null;
 167:     else
 168:       {
 169:         if (e == first)
 170:           {
 171:             first = e.next;
 172:             e.next.previous = null;
 173:           }
 174:         else if (e == last)
 175:           {
 176:             last = e.previous;
 177:             e.previous.next = null;
 178:           }
 179:         else
 180:           {
 181:             e.next.previous = e.previous;
 182:             e.previous.next = e.next;
 183:           }
 184:       }
 185:   }
 186: 
 187:   /**
 188:    * Checks that the index is in the range of possible elements (inclusive).
 189:    *
 190:    * @param index the index to check
 191:    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size
 192:    */
 193:   private void checkBoundsInclusive(int index)
 194:   {
 195:     if (index < 0 || index > size)
 196:       throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
 197:                                           + size);
 198:   }
 199: 
 200:   /**
 201:    * Checks that the index is in the range of existing elements (exclusive).
 202:    *
 203:    * @param index the index to check
 204:    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size
 205:    */
 206:   private void checkBoundsExclusive(int index)
 207:   {
 208:     if (index < 0 || index >= size)
 209:       throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
 210:                                           + size);
 211:   }
 212: 
 213:   /**
 214:    * Create an empty linked list.
 215:    */
 216:   public LinkedList()
 217:   {
 218:   }
 219: 
 220:   /**
 221:    * Create a linked list containing the elements, in order, of a given
 222:    * collection.
 223:    *
 224:    * @param c the collection to populate this list from
 225:    * @throws NullPointerException if c is null
 226:    */
 227:   public LinkedList(Collection c)
 228:   {
 229:     addAll(c);
 230:   }
 231: 
 232:   /**
 233:    * Returns the first element in the list.
 234:    *
 235:    * @return the first list element
 236:    * @throws NoSuchElementException if the list is empty
 237:    */
 238:   public Object getFirst()
 239:   {
 240:     if (size == 0)
 241:       throw new NoSuchElementException();
 242:     return first.data;
 243:   }
 244: 
 245:   /**
 246:    * Returns the last element in the list.
 247:    *
 248:    * @return the last list element
 249:    * @throws NoSuchElementException if the list is empty
 250:    */
 251:   public Object getLast()
 252:   {
 253:     if (size == 0)
 254:       throw new NoSuchElementException();
 255:     return last.data;
 256:   }
 257: 
 258:   /**
 259:    * Remove and return the first element in the list.
 260:    *
 261:    * @return the former first element in the list
 262:    * @throws NoSuchElementException if the list is empty
 263:    */
 264:   public Object removeFirst()
 265:   {
 266:     if (size == 0)
 267:       throw new NoSuchElementException();
 268:     modCount++;
 269:     size--;
 270:     Object r = first.data;
 271: 
 272:     if (first.next != null)
 273:       first.next.previous = null;
 274:     else
 275:       last = null;
 276: 
 277:     first = first.next;
 278: 
 279:     return r;
 280:   }
 281: 
 282:   /**
 283:    * Remove and return the last element in the list.
 284:    *
 285:    * @return the former last element in the list
 286:    * @throws NoSuchElementException if the list is empty
 287:    */
 288:   public Object removeLast()
 289:   {
 290:     if (size == 0)
 291:       throw new NoSuchElementException();
 292:     modCount++;
 293:     size--;
 294:     Object r = last.data;
 295: 
 296:     if (last.previous != null)
 297:       last.previous.next = null;
 298:     else
 299:       first = null;
 300: 
 301:     last = last.previous;
 302: 
 303:     return r;
 304:   }
 305: 
 306:   /**
 307:    * Insert an element at the first of the list.
 308:    *
 309:    * @param o the element to insert
 310:    */
 311:   public void addFirst(Object o)
 312:   {
 313:     Entry e = new Entry(o);
 314: 
 315:     modCount++;
 316:     if (size == 0)
 317:       first = last = e;
 318:     else
 319:       {
 320:         e.next = first;
 321:         first.previous = e;
 322:         first = e;
 323:       }
 324:     size++;
 325:   }
 326: 
 327:   /**
 328:    * Insert an element at the last of the list.
 329:    *
 330:    * @param o the element to insert
 331:    */
 332:   public void addLast(Object o)
 333:   {
 334:     addLastEntry(new Entry(o));
 335:   }
 336: 
 337:   /**
 338:    * Inserts an element at the end of the list.
 339:    *
 340:    * @param e the entry to add
 341:    */
 342:   private void addLastEntry(Entry e)
 343:   {
 344:     modCount++;
 345:     if (size == 0)
 346:       first = last = e;
 347:     else
 348:       {
 349:         e.previous = last;
 350:         last.next = e;
 351:         last = e;
 352:       }
 353:     size++;
 354:   }
 355: 
 356:   /**
 357:    * Returns true if the list contains the given object. Comparison is done by
 358:    * <code>o == null ? e = null : o.equals(e)</code>.
 359:    *
 360:    * @param o the element to look for
 361:    * @return true if it is found
 362:    */
 363:   public boolean contains(Object o)
 364:   {
 365:     Entry e = first;
 366:     while (e != null)
 367:       {
 368:         if (equals(o, e.data))
 369:           return true;
 370:         e = e.next;
 371:       }
 372:     return false;
 373:   }
 374: 
 375:   /**
 376:    * Returns the size of the list.
 377:    *
 378:    * @return the list size
 379:    */
 380:   public int size()
 381:   {
 382:     return size;
 383:   }
 384: 
 385:   /**
 386:    * Adds an element to the end of the list.
 387:    *
 388:    * @param o the entry to add
 389:    * @return true, as it always succeeds
 390:    */
 391:   public boolean add(Object o)
 392:   {
 393:     addLastEntry(new Entry(o));
 394:     return true;
 395:   }
 396: 
 397:   /**
 398:    * Removes the entry at the lowest index in the list that matches the given
 399:    * object, comparing by <code>o == null ? e = null : o.equals(e)</code>.
 400:    *
 401:    * @param o the object to remove
 402:    * @return true if an instance of the object was removed
 403:    */
 404:   public boolean remove(Object o)
 405:   {
 406:     Entry e = first;
 407:     while (e != null)
 408:       {
 409:         if (equals(o, e.data))
 410:           {
 411:             removeEntry(e);
 412:             return true;
 413:           }
 414:         e = e.next;
 415:       }
 416:     return false;
 417:   }
 418: 
 419:   /**
 420:    * Append the elements of the collection in iteration order to the end of
 421:    * this list. If this list is modified externally (for example, if this
 422:    * list is the collection), behavior is unspecified.
 423:    *
 424:    * @param c the collection to append
 425:    * @return true if the list was modified
 426:    * @throws NullPointerException if c is null
 427:    */
 428:   public boolean addAll(Collection c)
 429:   {
 430:     return addAll(size, c);
 431:   }
 432: 
 433:   /**
 434:    * Insert the elements of the collection in iteration order at the given
 435:    * index of this list. If this list is modified externally (for example,
 436:    * if this list is the collection), behavior is unspecified.
 437:    *
 438:    * @param c the collection to append
 439:    * @return true if the list was modified
 440:    * @throws NullPointerException if c is null
 441:    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
 442:    */
 443:   public boolean addAll(int index, Collection c)
 444:   {
 445:     checkBoundsInclusive(index);
 446:     int csize = c.size();
 447: 
 448:     if (csize == 0)
 449:       return false;
 450: 
 451:     Iterator itr = c.iterator();
 452: 
 453:     // Get the entries just before and after index. If index is at the start
 454:     // of the list, BEFORE is null. If index is at the end of the list, AFTER
 455:     // is null. If the list is empty, both are null.
 456:     Entry after = null;
 457:     Entry before = null;
 458:     if (index != size)
 459:       {
 460:         after = getEntry(index);
 461:         before = after.previous;
 462:       }
 463:     else
 464:       before = last;
 465: 
 466:     // Create the first new entry. We do not yet set the link from `before'
 467:     // to the first entry, in order to deal with the case where (c == this).
 468:     // [Actually, we don't have to handle this case to fufill the
 469:     // contract for addAll(), but Sun's implementation appears to.]
 470:     Entry e = new Entry(itr.next());
 471:     e.previous = before;
 472:     Entry prev = e;
 473:     Entry firstNew = e;
 474: 
 475:     // Create and link all the remaining entries.
 476:     for (int pos = 1; pos < csize; pos++)
 477:       {
 478:         e = new Entry(itr.next());
 479:         e.previous = prev;
 480:         prev.next = e;
 481:         prev = e;
 482:       }
 483: 
 484:     // Link the new chain of entries into the list.
 485:     modCount++;
 486:     size += csize;
 487:     prev.next = after;
 488:     if (after != null)
 489:       after.previous = e;
 490:     else
 491:       last = e;
 492: 
 493:     if (before != null)
 494:       before.next = firstNew;
 495:     else
 496:       first = firstNew;
 497:     return true;
 498:   }
 499: 
 500:   /**
 501:    * Remove all elements from this list.
 502:    */
 503:   public void clear()
 504:   {
 505:     if (size > 0)
 506:       {
 507:         modCount++;
 508:         first = null;
 509:         last = null;
 510:         size = 0;
 511:       }
 512:   }
 513: 
 514:   /**
 515:    * Return the element at index.
 516:    *
 517:    * @param index the place to look
 518:    * @return the element at index
 519:    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
 520:    */
 521:   public Object get(int index)
 522:   {
 523:     checkBoundsExclusive(index);
 524:     return getEntry(index).data;
 525:   }
 526: 
 527:   /**
 528:    * Replace the element at the given location in the list.
 529:    *
 530:    * @param index which index to change
 531:    * @param o the new element
 532:    * @return the prior element
 533:    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
 534:    */
 535:   public Object set(int index, Object o)
 536:   {
 537:     checkBoundsExclusive(index);
 538:     Entry e = getEntry(index);
 539:     Object old = e.data;
 540:     e.data = o;
 541:     return old;
 542:   }
 543: 
 544:   /**
 545:    * Inserts an element in the given position in the list.
 546:    *
 547:    * @param index where to insert the element
 548:    * @param o the element to insert
 549:    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
 550:    */
 551:   public void add(int index, Object o)
 552:   {
 553:     checkBoundsInclusive(index);
 554:     Entry e = new Entry(o);
 555: 
 556:     if (index < size)
 557:       {
 558:         modCount++;
 559:         Entry after = getEntry(index);
 560:         e.next = after;
 561:         e.previous = after.previous;
 562:         if (after.previous == null)
 563:           first = e;
 564:         else
 565:           after.previous.next = e;
 566:         after.previous = e;
 567:         size++;
 568:       }
 569:     else
 570:       addLastEntry(e);
 571:   }
 572: 
 573:   /**
 574:    * Removes the element at the given position from the list.
 575:    *
 576:    * @param index the location of the element to remove
 577:    * @return the removed element
 578:    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
 579:    */
 580:   public Object remove(int index)
 581:   {
 582:     checkBoundsExclusive(index);
 583:     Entry e = getEntry(index);
 584:     removeEntry(e);
 585:     return e.data;
 586:   }
 587: 
 588:   /**
 589:    * Returns the first index where the element is located in the list, or -1.
 590:    *
 591:    * @param o the element to look for
 592:    * @return its position, or -1 if not found
 593:    */
 594:   public int indexOf(Object o)
 595:   {
 596:     int index = 0;
 597:     Entry e = first;
 598:     while (e != null)
 599:       {
 600:         if (equals(o, e.data))
 601:           return index;
 602:         index++;
 603:         e = e.next;
 604:       }
 605:     return -1;
 606:   }
 607: 
 608:   /**
 609:    * Returns the last index where the element is located in the list, or -1.
 610:    *
 611:    * @param o the element to look for
 612:    * @return its position, or -1 if not found
 613:    */
 614:   public int lastIndexOf(Object o)
 615:   {
 616:     int index = size - 1;
 617:     Entry e = last;
 618:     while (e != null)
 619:       {
 620:         if (equals(o, e.data))
 621:           return index;
 622:         index--;
 623:         e = e.previous;
 624:       }
 625:     return -1;
 626:   }
 627: 
 628:   /**
 629:    * Obtain a ListIterator over this list, starting at a given index. The
 630:    * ListIterator returned by this method supports the add, remove and set
 631:    * methods.
 632:    *
 633:    * @param index the index of the element to be returned by the first call to
 634:    *        next(), or size() to be initially positioned at the end of the list
 635:    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
 636:    */
 637:   public ListIterator listIterator(int index)
 638:   {
 639:     checkBoundsInclusive(index);
 640:     return new LinkedListItr(index);
 641:   }
 642: 
 643:   /**
 644:    * Create a shallow copy of this LinkedList (the elements are not cloned).
 645:    *
 646:    * @return an object of the same class as this object, containing the
 647:    *         same elements in the same order
 648:    */
 649:   public Object clone()
 650:   {
 651:     LinkedList copy = null;
 652:     try
 653:       {
 654:         copy = (LinkedList) super.clone();
 655:       }
 656:     catch (CloneNotSupportedException ex)
 657:       {
 658:       }
 659:     copy.clear();
 660:     copy.addAll(this);
 661:     return copy;
 662:   }
 663: 
 664:   /**
 665:    * Returns an array which contains the elements of the list in order.
 666:    *
 667:    * @return an array containing the list elements
 668:    */
 669:   public Object[] toArray()
 670:   {
 671:     Object[] array = new Object[size];
 672:     Entry e = first;
 673:     for (int i = 0; i < size; i++)
 674:       {
 675:         array[i] = e.data;
 676:         e = e.next;
 677:       }
 678:     return array;
 679:   }
 680: 
 681:   /**
 682:    * Returns an Array whose component type is the runtime component type of
 683:    * the passed-in Array.  The returned Array is populated with all of the
 684:    * elements in this LinkedList.  If the passed-in Array is not large enough
 685:    * to store all of the elements in this List, a new Array will be created 
 686:    * and returned; if the passed-in Array is <i>larger</i> than the size
 687:    * of this List, then size() index will be set to null.
 688:    *
 689:    * @param a the passed-in Array
 690:    * @return an array representation of this list
 691:    * @throws ArrayStoreException if the runtime type of a does not allow
 692:    *         an element in this list
 693:    * @throws NullPointerException if a is null
 694:    */
 695:   public Object[] toArray(Object[] a)
 696:   {
 697:     if (a.length < size)
 698:       a = (Object[]) Array.newInstance(a.getClass().getComponentType(), size);
 699:     else if (a.length > size)
 700:       a[size] = null;
 701:     Entry e = first;
 702:     for (int i = 0; i < size; i++)
 703:       {
 704:         a[i] = e.data;
 705:         e = e.next;
 706:       }
 707:     return a;
 708:   }
 709: 
 710:   /**
 711:    * Serializes this object to the given stream.
 712:    *
 713:    * @param s the stream to write to
 714:    * @throws IOException if the underlying stream fails
 715:    * @serialData the size of the list (int), followed by all the elements
 716:    *             (Object) in proper order
 717:    */
 718:   private void writeObject(ObjectOutputStream s) throws IOException
 719:   {
 720:     s.defaultWriteObject();
 721:     s.writeInt(size);
 722:     Entry e = first;
 723:     while (e != null)
 724:       {
 725:         s.writeObject(e.data);
 726:         e = e.next;
 727:       }
 728:   }
 729: 
 730:   /**
 731:    * Deserializes this object from the given stream.
 732:    *
 733:    * @param s the stream to read from
 734:    * @throws ClassNotFoundException if the underlying stream fails
 735:    * @throws IOException if the underlying stream fails
 736:    * @serialData the size of the list (int), followed by all the elements
 737:    *             (Object) in proper order
 738:    */
 739:   private void readObject(ObjectInputStream s)
 740:     throws IOException, ClassNotFoundException
 741:   {
 742:     s.defaultReadObject();
 743:     int i = s.readInt();
 744:     while (--i >= 0)
 745:       addLastEntry(new Entry(s.readObject()));
 746:   }
 747: 
 748:   /**
 749:    * A ListIterator over the list. This class keeps track of its
 750:    * position in the list and the two list entries it is between.
 751:    *
 752:    * @author Original author unknown
 753:    * @author Eric Blake (ebb9@email.byu.edu)
 754:    */
 755:   private final class LinkedListItr implements ListIterator
 756:   {
 757:     /** Number of modifications we know about. */
 758:     private int knownMod = modCount;
 759: 
 760:     /** Entry that will be returned by next(). */
 761:     private Entry next;
 762: 
 763:     /** Entry that will be returned by previous(). */
 764:     private Entry previous;
 765: 
 766:     /** Entry that will be affected by remove() or set(). */
 767:     private Entry lastReturned;
 768: 
 769:     /** Index of `next'. */
 770:     private int position;
 771: 
 772:     /**
 773:      * Initialize the iterator.
 774:      *
 775:      * @param index the initial index
 776:      */
 777:     LinkedListItr(int index)
 778:     {
 779:       if (index == size)
 780:         {
 781:           next = null;
 782:           previous = last;
 783:         }
 784:       else
 785:         {
 786:           next = getEntry(index);
 787:           previous = next.previous;
 788:         }
 789:       position = index;
 790:     }
 791: 
 792:     /**
 793:      * Checks for iterator consistency.
 794:      *
 795:      * @throws ConcurrentModificationException if the list was modified
 796:      */
 797:     private void checkMod()
 798:     {
 799:       if (knownMod != modCount)
 800:         throw new ConcurrentModificationException();
 801:     }
 802: 
 803:     /**
 804:      * Returns the index of the next element.
 805:      *
 806:      * @return the next index
 807:      * @throws ConcurrentModificationException if the list was modified
 808:      */
 809:     public int nextIndex()
 810:     {
 811:       checkMod();
 812:       return position;
 813:     }
 814: 
 815:     /**
 816:      * Returns the index of the previous element.
 817:      *
 818:      * @return the previous index
 819:      * @throws ConcurrentModificationException if the list was modified
 820:      */
 821:     public int previousIndex()
 822:     {
 823:       checkMod();
 824:       return position - 1;
 825:     }
 826: 
 827:     /**
 828:      * Returns true if more elements exist via next.
 829:      *
 830:      * @return true if next will succeed
 831:      * @throws ConcurrentModificationException if the list was modified
 832:      */
 833:     public boolean hasNext()
 834:     {
 835:       checkMod();
 836:       return (next != null);
 837:     }
 838: 
 839:     /**
 840:      * Returns true if more elements exist via previous.
 841:      *
 842:      * @return true if previous will succeed
 843:      * @throws ConcurrentModificationException if the list was modified
 844:      */
 845:     public boolean hasPrevious()
 846:     {
 847:       checkMod();
 848:       return (previous != null);
 849:     }
 850: 
 851:     /**
 852:      * Returns the next element.
 853:      *
 854:      * @return the next element
 855:      * @throws ConcurrentModificationException if the list was modified
 856:      * @throws NoSuchElementException if there is no next
 857:      */
 858:     public Object next()
 859:     {
 860:       checkMod();
 861:       if (next == null)
 862:         throw new NoSuchElementException();
 863:       position++;
 864:       lastReturned = previous = next;
 865:       next = lastReturned.next;
 866:       return lastReturned.data;
 867:     }
 868: 
 869:     /**
 870:      * Returns the previous element.
 871:      *
 872:      * @return the previous element
 873:      * @throws ConcurrentModificationException if the list was modified
 874:      * @throws NoSuchElementException if there is no previous
 875:      */
 876:     public Object previous()
 877:     {
 878:       checkMod();
 879:       if (previous == null)
 880:         throw new NoSuchElementException();
 881:       position--;
 882:       lastReturned = next = previous;
 883:       previous = lastReturned.previous;
 884:       return lastReturned.data;
 885:     }
 886: 
 887:     /**
 888:      * Remove the most recently returned element from the list.
 889:      *
 890:      * @throws ConcurrentModificationException if the list was modified
 891:      * @throws IllegalStateException if there was no last element
 892:      */
 893:     public void remove()
 894:     {
 895:       checkMod();
 896:       if (lastReturned == null)
 897:         throw new IllegalStateException();
 898: 
 899:       // Adjust the position to before the removed element, if the element
 900:       // being removed is behind the cursor.
 901:       if (lastReturned == previous)
 902:         position--;
 903: 
 904:       next = lastReturned.next;
 905:       previous = lastReturned.previous;
 906:       removeEntry(lastReturned);
 907:       knownMod++;
 908: 
 909:       lastReturned = null;
 910:     }
 911: 
 912:     /**
 913:      * Adds an element between the previous and next, and advance to the next.
 914:      *
 915:      * @param o the element to add
 916:      * @throws ConcurrentModificationException if the list was modified
 917:      */
 918:     public void add(Object o)
 919:     {
 920:       checkMod();
 921:       modCount++;
 922:       knownMod++;
 923:       size++;
 924:       position++;
 925:       Entry e = new Entry(o);
 926:       e.previous = previous;
 927:       e.next = next;
 928: 
 929:       if (previous != null)
 930:         previous.next = e;
 931:       else
 932:         first = e;
 933: 
 934:       if (next != null)
 935:         next.previous = e;
 936:       else
 937:         last = e;
 938: 
 939:       previous = e;
 940:       lastReturned = null;
 941:     }
 942: 
 943:     /**
 944:      * Changes the contents of the element most recently returned.
 945:      *
 946:      * @param o the new element
 947:      * @throws ConcurrentModificationException if the list was modified
 948:      * @throws IllegalStateException if there was no last element
 949:      */
 950:     public void set(Object o)
 951:     {
 952:       checkMod();
 953:       if (lastReturned == null)
 954:         throw new IllegalStateException();
 955:       lastReturned.data = o;
 956:     }
 957:   } // class LinkedListItr
 958: }