1 /* LinkedList.java -- Linked list implementation of the List interface
2 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005 Free Software Foundation, Inc.
4 This file is part of GNU Classpath.
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)
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.
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., 59 Temple Place, Suite 330, Boston, MA
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
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. */
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
;
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>
53 * LinkedList is not synchronized, so if you need multi-threaded access,
55 * <code>List l = Collections.synchronizedList(new LinkedList(...));</code>
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.
64 * @author Original author unknown
65 * @author Bryce McKinlay
66 * @author Eric Blake (ebb9@email.byu.edu)
70 * @see Collections#synchronizedList(List)
72 * @status missing javadoc, but complete to 1.4
74 public class LinkedList
extends AbstractSequentialList
75 implements List
, Cloneable
, Serializable
78 * Compatible with JDK 1.2.
80 private static final long serialVersionUID
= 876323262645176354L;
83 * The first element in the list.
85 transient Entry first
;
88 * The last element in the list.
93 * The current length of the list.
95 transient int size
= 0;
98 * Class to represent an entry in the list. Holds a single element.
100 private static final class Entry
102 /** The element in the list. */
105 /** The next list entry, null if this is last. */
108 /** The previous list entry, null if this is first. */
112 * Construct an entry.
113 * @param data the list element
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
127 * For speed and flexibility, range checking is not done in this method:
128 * Incorrect values will be returned if (n < 0) or (n >= size).
130 * @param n the number of the entry to get
131 * @return the entry at position n
133 // Package visible for use in nested classes.
134 Entry
getEntry(int n
)
140 // n less than size/2, iterate from start
147 // n greater than size/2, iterate from end
155 * Remove an entry from the list. This will adjust size and deal with
156 * `first' and `last' appropriatly.
158 * @param e the entry to remove
160 // Package visible for use in nested classes.
161 void removeEntry(Entry e
)
172 e
.next
.previous
= null;
177 e
.previous
.next
= null;
181 e
.next
.previous
= e
.previous
;
182 e
.previous
.next
= e
.next
;
188 * Checks that the index is in the range of possible elements (inclusive).
190 * @param index the index to check
191 * @throws IndexOutOfBoundsException if index < 0 || index > size
193 private void checkBoundsInclusive(int index
)
195 if (index
< 0 || index
> size
)
196 throw new IndexOutOfBoundsException("Index: " + index
+ ", Size:"
201 * Checks that the index is in the range of existing elements (exclusive).
203 * @param index the index to check
204 * @throws IndexOutOfBoundsException if index < 0 || index >= size
206 private void checkBoundsExclusive(int index
)
208 if (index
< 0 || index
>= size
)
209 throw new IndexOutOfBoundsException("Index: " + index
+ ", Size:"
214 * Create an empty linked list.
221 * Create a linked list containing the elements, in order, of a given
224 * @param c the collection to populate this list from
225 * @throws NullPointerException if c is null
227 public LinkedList(Collection c
)
233 * Returns the first element in the list.
235 * @return the first list element
236 * @throws NoSuchElementException if the list is empty
238 public Object
getFirst()
241 throw new NoSuchElementException();
246 * Returns the last element in the list.
248 * @return the last list element
249 * @throws NoSuchElementException if the list is empty
251 public Object
getLast()
254 throw new NoSuchElementException();
259 * Remove and return the first element in the list.
261 * @return the former first element in the list
262 * @throws NoSuchElementException if the list is empty
264 public Object
removeFirst()
267 throw new NoSuchElementException();
270 Object r
= first
.data
;
272 if (first
.next
!= null)
273 first
.next
.previous
= null;
283 * Remove and return the last element in the list.
285 * @return the former last element in the list
286 * @throws NoSuchElementException if the list is empty
288 public Object
removeLast()
291 throw new NoSuchElementException();
294 Object r
= last
.data
;
296 if (last
.previous
!= null)
297 last
.previous
.next
= null;
301 last
= last
.previous
;
307 * Insert an element at the first of the list.
309 * @param o the element to insert
311 public void addFirst(Object o
)
313 Entry e
= new Entry(o
);
328 * Insert an element at the last of the list.
330 * @param o the element to insert
332 public void addLast(Object o
)
334 addLastEntry(new Entry(o
));
338 * Inserts an element at the end of the list.
340 * @param e the entry to add
342 private void addLastEntry(Entry e
)
357 * Returns true if the list contains the given object. Comparison is done by
358 * <code>o == null ? e = null : o.equals(e)</code>.
360 * @param o the element to look for
361 * @return true if it is found
363 public boolean contains(Object o
)
368 if (equals(o
, e
.data
))
376 * Returns the size of the list.
378 * @return the list size
386 * Adds an element to the end of the list.
388 * @param e the entry to add
389 * @return true, as it always succeeds
391 public boolean add(Object o
)
393 addLastEntry(new Entry(o
));
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>.
401 * @param o the object to remove
402 * @return true if an instance of the object was removed
404 public boolean remove(Object o
)
409 if (equals(o
, e
.data
))
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.
424 * @param c the collection to append
425 * @return true if the list was modified
426 * @throws NullPointerException if c is null
428 public boolean addAll(Collection c
)
430 return addAll(size
, c
);
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.
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 < 0 || index > size()
443 public boolean addAll(int index
, Collection c
)
445 checkBoundsInclusive(index
);
446 int csize
= c
.size();
451 Iterator itr
= c
.iterator();
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.
460 after
= getEntry(index
);
461 before
= after
.previous
;
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());
475 // Create and link all the remaining entries.
476 for (int pos
= 1; pos
< csize
; pos
++)
478 e
= new Entry(itr
.next());
484 // Link the new chain of entries into the list.
494 before
.next
= firstNew
;
501 * Remove all elements from this list.
515 * Return the element at index.
517 * @param index the place to look
518 * @return the element at index
519 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
521 public Object
get(int index
)
523 checkBoundsExclusive(index
);
524 return getEntry(index
).data
;
528 * Replace the element at the given location in the list.
530 * @param index which index to change
531 * @param o the new element
532 * @return the prior element
533 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
535 public Object
set(int index
, Object o
)
537 checkBoundsExclusive(index
);
538 Entry e
= getEntry(index
);
545 * Inserts an element in the given position in the list.
547 * @param index where to insert the element
548 * @param o the element to insert
549 * @throws IndexOutOfBoundsException if index < 0 || index > size()
551 public void add(int index
, Object o
)
553 checkBoundsInclusive(index
);
554 Entry e
= new Entry(o
);
559 Entry after
= getEntry(index
);
561 e
.previous
= after
.previous
;
562 if (after
.previous
== null)
565 after
.previous
.next
= e
;
574 * Removes the element at the given position from the list.
576 * @param index the location of the element to remove
577 * @return the removed element
578 * @throws IndexOutOfBoundsException if index < 0 || index > size()
580 public Object
remove(int index
)
582 checkBoundsExclusive(index
);
583 Entry e
= getEntry(index
);
589 * Returns the first index where the element is located in the list, or -1.
591 * @param o the element to look for
592 * @return its position, or -1 if not found
594 public int indexOf(Object o
)
600 if (equals(o
, e
.data
))
609 * Returns the last index where the element is located in the list, or -1.
611 * @param o the element to look for
612 * @return its position, or -1 if not found
614 public int lastIndexOf(Object o
)
616 int index
= size
- 1;
620 if (equals(o
, e
.data
))
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
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 < 0 || index > size()
637 public ListIterator
listIterator(int index
)
639 checkBoundsInclusive(index
);
640 return new LinkedListItr(index
);
644 * Create a shallow copy of this LinkedList (the elements are not cloned).
646 * @return an object of the same class as this object, containing the
647 * same elements in the same order
649 public Object
clone()
651 LinkedList copy
= null;
654 copy
= (LinkedList
) super.clone();
656 catch (CloneNotSupportedException ex
)
665 * Returns an array which contains the elements of the list in order.
667 * @return an array containing the list elements
669 public Object
[] toArray()
671 Object
[] array
= new Object
[size
];
673 for (int i
= 0; i
< size
; i
++)
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.
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
695 public Object
[] toArray(Object
[] a
)
698 a
= (Object
[]) Array
.newInstance(a
.getClass().getComponentType(), size
);
699 else if (a
.length
> size
)
702 for (int i
= 0; i
< size
; i
++)
711 * Serializes this object to the given stream.
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
718 private void writeObject(ObjectOutputStream s
) throws IOException
720 s
.defaultWriteObject();
725 s
.writeObject(e
.data
);
731 * Deserializes this object from the given stream.
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
739 private void readObject(ObjectInputStream s
)
740 throws IOException
, ClassNotFoundException
742 s
.defaultReadObject();
745 addLastEntry(new Entry(s
.readObject()));
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.
752 * @author Original author unknown
753 * @author Eric Blake (ebb9@email.byu.edu)
755 private final class LinkedListItr
implements ListIterator
757 /** Number of modifications we know about. */
758 private int knownMod
= modCount
;
760 /** Entry that will be returned by next(). */
763 /** Entry that will be returned by previous(). */
764 private Entry previous
;
766 /** Entry that will be affected by remove() or set(). */
767 private Entry lastReturned
;
769 /** Index of `next'. */
770 private int position
;
773 * Initialize the iterator.
775 * @param index the initial index
777 LinkedListItr(int index
)
786 next
= getEntry(index
);
787 previous
= next
.previous
;
793 * Checks for iterator consistency.
795 * @throws ConcurrentModificationException if the list was modified
797 private void checkMod()
799 if (knownMod
!= modCount
)
800 throw new ConcurrentModificationException();
804 * Returns the index of the next element.
806 * @return the next index
807 * @throws ConcurrentModificationException if the list was modified
809 public int nextIndex()
816 * Returns the index of the previous element.
818 * @return the previous index
819 * @throws ConcurrentModificationException if the list was modified
821 public int previousIndex()
828 * Returns true if more elements exist via next.
830 * @return true if next will succeed
831 * @throws ConcurrentModificationException if the list was modified
833 public boolean hasNext()
836 return (next
!= null);
840 * Returns true if more elements exist via previous.
842 * @return true if previous will succeed
843 * @throws ConcurrentModificationException if the list was modified
845 public boolean hasPrevious()
848 return (previous
!= null);
852 * Returns the next element.
854 * @return the next element
855 * @throws ConcurrentModificationException if the list was modified
856 * @throws NoSuchElementException if there is no next
862 throw new NoSuchElementException();
864 lastReturned
= previous
= next
;
865 next
= lastReturned
.next
;
866 return lastReturned
.data
;
870 * Returns the previous element.
872 * @return the previous element
873 * @throws ConcurrentModificationException if the list was modified
874 * @throws NoSuchElementException if there is no previous
876 public Object
previous()
879 if (previous
== null)
880 throw new NoSuchElementException();
882 lastReturned
= next
= previous
;
883 previous
= lastReturned
.previous
;
884 return lastReturned
.data
;
888 * Remove the most recently returned element from the list.
890 * @throws ConcurrentModificationException if the list was modified
891 * @throws IllegalStateException if there was no last element
896 if (lastReturned
== null)
897 throw new IllegalStateException();
899 // Adjust the position to before the removed element, if the element
900 // being removed is behind the cursor.
901 if (lastReturned
== previous
)
904 next
= lastReturned
.next
;
905 previous
= lastReturned
.previous
;
906 removeEntry(lastReturned
);
913 * Adds an element between the previous and next, and advance to the next.
915 * @param o the element to add
916 * @throws ConcurrentModificationException if the list was modified
918 public void add(Object o
)
925 Entry e
= new Entry(o
);
926 e
.previous
= previous
;
929 if (previous
!= null)
944 * Changes the contents of the element most recently returned.
946 * @param o the new element
947 * @throws ConcurrentModificationException if the list was modified
948 * @throws IllegalStateException if there was no last element
950 public void set(Object o
)
953 if (lastReturned
== null)
954 throw new IllegalStateException();
955 lastReturned
.data
= o
;
957 } // class LinkedListItr