001 /* LinkedList.java -- Linked list implementation of the List interface
002 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005, 2006 Free Software Foundation, Inc.
003
004 This file is part of GNU Classpath.
005
006 GNU Classpath is free software; you can redistribute it and/or modify
007 it under the terms of the GNU General Public License as published by
008 the Free Software Foundation; either version 2, or (at your option)
009 any later version.
010
011 GNU Classpath is distributed in the hope that it will be useful, but
012 WITHOUT ANY WARRANTY; without even the implied warranty of
013 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014 General Public License for more details.
015
016 You should have received a copy of the GNU General Public License
017 along with GNU Classpath; see the file COPYING. If not, write to the
018 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
019 02110-1301 USA.
020
021 Linking this library statically or dynamically with other modules is
022 making a combined work based on this library. Thus, the terms and
023 conditions of the GNU General Public License cover the whole
024 combination.
025
026 As a special exception, the copyright holders of this library give you
027 permission to link this library with independent modules to produce an
028 executable, regardless of the license terms of these independent
029 modules, and to copy and distribute the resulting executable under
030 terms of your choice, provided that you also meet, for each linked
031 independent module, the terms and conditions of the license of that
032 module. An independent module is a module which is not derived from
033 or based on this library. If you modify this library, you may extend
034 this exception to your version of the library, but you are not
035 obligated to do so. If you do not wish to do so, delete this
036 exception statement from your version. */
037
038
039 package java.util;
040 import java.io.IOException;
041 import java.io.ObjectInputStream;
042 import java.io.ObjectOutputStream;
043 import java.io.Serializable;
044 import java.lang.reflect.Array;
045
046 /**
047 * Linked list implementation of the List interface. In addition to the
048 * methods of the List interface, this class provides access to the first
049 * and last list elements in O(1) time for easy stack, queue, or double-ended
050 * queue (deque) creation. The list is doubly-linked, with traversal to a
051 * given index starting from the end closest to the element.<p>
052 *
053 * LinkedList is not synchronized, so if you need multi-threaded access,
054 * consider using:<br>
055 * <code>List l = Collections.synchronizedList(new LinkedList(...));</code>
056 * <p>
057 *
058 * The iterators are <i>fail-fast</i>, meaning that any structural
059 * modification, except for <code>remove()</code> called on the iterator
060 * itself, cause the iterator to throw a
061 * {@link ConcurrentModificationException} rather than exhibit
062 * non-deterministic behavior.
063 *
064 * @author Original author unknown
065 * @author Bryce McKinlay
066 * @author Eric Blake (ebb9@email.byu.edu)
067 * @author Tom Tromey (tromey@redhat.com)
068 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
069 * @see List
070 * @see ArrayList
071 * @see Vector
072 * @see Collections#synchronizedList(List)
073 * @since 1.2
074 * @status Complete to 1.6
075 */
076 public class LinkedList<T> extends AbstractSequentialList<T>
077 implements List<T>, Deque<T>, Cloneable, Serializable
078 {
079 /**
080 * Compatible with JDK 1.2.
081 */
082 private static final long serialVersionUID = 876323262645176354L;
083
084 /**
085 * The first element in the list.
086 */
087 transient Entry<T> first;
088
089 /**
090 * The last element in the list.
091 */
092 transient Entry<T> last;
093
094 /**
095 * The current length of the list.
096 */
097 transient int size = 0;
098
099 /**
100 * Class to represent an entry in the list. Holds a single element.
101 */
102 private static final class Entry<T>
103 {
104 /** The element in the list. */
105 T data;
106
107 /** The next list entry, null if this is last. */
108 Entry<T> next;
109
110 /** The previous list entry, null if this is first. */
111 Entry<T> previous;
112
113 /**
114 * Construct an entry.
115 * @param data the list element
116 */
117 Entry(T data)
118 {
119 this.data = data;
120 }
121 } // class Entry
122
123 /**
124 * Obtain the Entry at a given position in a list. This method of course
125 * takes linear time, but it is intelligent enough to take the shorter of the
126 * paths to get to the Entry required. This implies that the first or last
127 * entry in the list is obtained in constant time, which is a very desirable
128 * property.
129 * For speed and flexibility, range checking is not done in this method:
130 * Incorrect values will be returned if (n < 0) or (n >= 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 < 0 || index > 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 < 0 || index >= 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 < 0 || index > 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 < 0 || index >= 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 < 0 || index >= 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 < 0 || index > 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 < 0 || index > 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 < 0 || index > 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 }