/* * %W% %E% * * Copyright 2004 Sun Microsystems, Inc. All rights reserved. * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. */ package java.util; /** * Linked list implementation of the List interface. Implements all * optional list operations, and permits all elements (including * null). In addition to implementing the List interface, * the LinkedList class provides uniformly named methods to * get, remove and insert an element at the * beginning and end of the list. These operations allow linked lists to be * used as a stack, {@linkplain Queue queue}, or {@linkplain Deque * double-ended queue}.

* * The class implements the Deque interface, providing * first-in-first-out queue operations for add, * poll, along with other stack and deque operations.

* * All of the operations perform as could be expected for a doubly-linked * list. Operations that index into the list will traverse the list from * the beginning or the end, whichever is closer to the specified index.

* * Note that this implementation is not synchronized. If multiple * threads access a list concurrently, and at least one of the threads * modifies the list structurally, it must be synchronized * externally. (A structural modification is any operation that adds or * deletes one or more elements; merely setting the value of an element is not * a structural modification.) This is typically accomplished by * synchronizing on some object that naturally encapsulates the list. If no * such object exists, the list should be "wrapped" using the * Collections.synchronizedList method. This is best done at creation time, * to prevent accidental unsynchronized access to the list: 

 *     List list = Collections.synchronizedList(new LinkedList(...));
 *

* * The iterators returned by the this class's iterator and * listIterator methods are fail-fast: if the list is * structurally modified at any time after the iterator is created, in any way * except through the Iterator's own remove or add methods, * the iterator will throw a ConcurrentModificationException. Thus, * in the face of concurrent modification, the iterator fails quickly and * cleanly, rather than risking arbitrary, non-deterministic behavior at an * undetermined time in the future. * *

Note that the fail-fast behavior of an iterator cannot be guaranteed * as it is, generally speaking, impossible to make any hard guarantees in the * presence of unsynchronized concurrent modification. Fail-fast iterators * throw ConcurrentModificationException on a best-effort basis. * Therefore, it would be wrong to write a program that depended on this * exception for its correctness: the fail-fast behavior of iterators * should be used only to detect bugs.

* * This class is a member of the * * Java Collections Framework. * * @author Josh Bloch * @version %I%, %G% * @see List * @see ArrayList * @see Vector * @see Collections#synchronizedList(List) * @since 1.2 * @param the type of elements held in this collection */ public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable { private transient Entry header = new Entry(null, null, null); private transient int size = 0; /** * Constructs an empty list. */ public LinkedList() { header.next = header.previous = header; } /** * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collection's * iterator. * * @param c the collection whose elements are to be placed into this list. * @throws NullPointerException if the specified collection is null. */ public LinkedList(Collection c) { this(); addAll(c); } /** * Returns the first element in this list. * * @return the first element in this list. * @throws NoSuchElementException if this list is empty. */ public E getFirst() { if (size==0) throw new NoSuchElementException(); return header.next.element; } /** * Returns the last element in this list. * * @return the last element in this list. * @throws NoSuchElementException if this list is empty. */ public E getLast() { if (size==0) throw new NoSuchElementException(); return header.previous.element; } /** * Removes and returns the first element from this list. * * @return the first element from this list. * @throws NoSuchElementException if this list is empty. */ public E removeFirst() { return remove(header.next); } /** * Removes and returns the last element from this list. * * @return the last element from this list. * @throws NoSuchElementException if this list is empty. */ public E removeLast() { return remove(header.previous); } /** * Inserts the given element at the beginning of this list. * * @param o the element to be inserted at the beginning of this list. */ public void addFirst(E o) { addBefore(o, header.next); } /** * Appends the given element to the end of this list. (Identical in * function to the add method; included only for consistency.) * * @param o the element to be inserted at the end of this list. */ public void addLast(E o) { addBefore(o, header); } /** * Returns true if this list contains the specified element. * More formally, returns true if and only if this list contains * at least one element e such that (o==null ? e==null * : o.equals(e)). * * @param o element whose presence in this list is to be tested. * @return true if this list contains the specified element. */ public boolean contains(Object o) { return indexOf(o) != -1; } /** * Returns the number of elements in this list. * * @return the number of elements in this list. */ public int size() { return size; } /** * Appends the specified element to the end of this list. * * @param o element to be appended to this list. * @return true (as per the general contract of * Collection.add). */ public boolean add(E o) { addBefore(o, header); return true; } /** * Removes the first occurrence of the specified element in this list. If * the list does not contain the element, it is unchanged. More formally, * removes the element with the lowest index i such that * (o==null ? get(i)==null : o.equals(get(i))) (if such an * element exists). * * @param o element to be removed from this list, if present. * @return true if the list contained the specified element. */ public boolean remove(Object o) { if (o==null) { for (Entry e = header.next; e != header; e = e.next) { if (e.element==null) { remove(e); return true; } } } else { for (Entry e = header.next; e != header; e = e.next) { if (o.equals(e.element)) { remove(e); return true; } } } return false; } /** * Appends all of the elements in the specified collection to the end of * this list, in the order that they are returned by the specified * collection's iterator. The behavior of this operation is undefined if * the specified collection is modified while the operation is in * progress. (This implies that the behavior of this call is undefined if * the specified Collection is this list, and this list is nonempty.) * * @param c the elements to be inserted into this list. * @return true if this list changed as a result of the call. * @throws NullPointerException if the specified collection is null. */ public boolean addAll(Collection c) { return addAll(size, c); } /** * Inserts all of the elements in the specified collection into this * list, starting at the specified position. Shifts the element * currently at that position (if any) and any subsequent elements to * the right (increases their indices). The new elements will appear * in the list in the order that they are returned by the * specified collection's iterator. * * @param index index at which to insert first element * from the specified collection. * @param c elements to be inserted into this list. * @return true if this list changed as a result of the call. * @throws IndexOutOfBoundsException if the specified index is out of * range (index < 0 || index > size()). * @throws NullPointerException if the specified collection is null. */ public boolean addAll(int index, Collection c) { if (index < 0 || index > size) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); Object[] a = c.toArray(); int numNew = a.length; if (numNew==0) return false; modCount++; Entry successor = (index==size ? header : entry(index)); Entry predecessor = successor.previous; for (int i=0; i e = new Entry((E)a[i], successor, predecessor); predecessor.next = e; predecessor = e; } successor.previous = predecessor; size += numNew; return true; } /** * Removes all of the elements from this list. */ public void clear() { Entry e = header.next; while (e != header) { Entry next = e.next; e.next = e.previous = null; e.element = null; e = next; } header.next = header.previous = header; size = 0; modCount++; } // Positional Access Operations /** * Returns the element at the specified position in this list. * * @param index index of element to return. * @return the element at the specified position in this list. * * @throws IndexOutOfBoundsException if the specified index is out of * range (index < 0 || index >= size()). */ public E get(int index) { return entry(index).element; } /** * Replaces the element at the specified position in this list with the * specified element. * * @param index index of element to replace. * @param element element to be stored at the specified position. * @return the element previously at the specified position. * @throws IndexOutOfBoundsException if the specified index is out of * range (index < 0 || index >= size()). */ public E set(int index, E element) { Entry e = entry(index); E oldVal = e.element; e.element = element; return oldVal; } /** * Inserts the specified element at the specified position in this list. * Shifts the element currently at that position (if any) and any * subsequent elements to the right (adds one to their indices). * * @param index index at which the specified element is to be inserted. * @param element element to be inserted. * * @throws IndexOutOfBoundsException if the specified index is out of * range (index < 0 || index > size()). */ public void add(int index, E element) { addBefore(element, (index==size ? header : entry(index))); } /** * Removes the element at the specified position in this list. Shifts any * subsequent elements to the left (subtracts one from their indices). * Returns the element that was removed from the list. * * @param index the index of the element to removed. * @return the element previously at the specified position. * * @throws IndexOutOfBoundsException if the specified index is out of * range (index < 0 || index >= size()). */ public E remove(int index) { return remove(entry(index)); } /** * Return the indexed entry. */ private Entry entry(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); Entry e = header; if (index < (size >> 1)) { for (int i = 0; i <= index; i++) e = e.next; } else { for (int i = size; i > index; i--) e = e.previous; } return e; } // Search Operations /** * Returns the index in this list of the first occurrence of the * specified element, or -1 if the List does not contain this * element. More formally, returns the lowest index i such that * (o==null ? get(i)==null : o.equals(get(i))), or -1 if * there is no such index. * * @param o element to search for. * @return the index in this list of the first occurrence of the * specified element, or -1 if the list does not contain this * element. */ public int indexOf(Object o) { int index = 0; if (o==null) { for (Entry e = header.next; e != header; e = e.next) { if (e.element==null) return index; index++; } } else { for (Entry e = header.next; e != header; e = e.next) { if (o.equals(e.element)) return index; index++; } } return -1; } /** * Returns the index in this list of the last occurrence of the * specified element, or -1 if the list does not contain this * element. More formally, returns the highest index i such that * (o==null ? get(i)==null : o.equals(get(i))), or -1 if * there is no such index. * * @param o element to search for. * @return the index in this list of the last occurrence of the * specified element, or -1 if the list does not contain this * element. */ public int lastIndexOf(Object o) { int index = size; if (o==null) { for (Entry e = header.previous; e != header; e = e.previous) { index--; if (e.element==null) return index; } } else { for (Entry e = header.previous; e != header; e = e.previous) { index--; if (o.equals(e.element)) return index; } } return -1; } // Queue operations. /** * Retrieves, but does not remove, the head (first element) of this list. * @return the head of this list, or null if this list is empty. * @since 1.5 */ public E peek() { if (size==0) return null; return getFirst(); } /** * Retrieves, but does not remove, the head (first element) of this list. * @return the head of this list. * @throws NoSuchElementException if this list is empty. * @since 1.5 */ public E element() { return getFirst(); } /** * Retrieves and removes the head (first element) of this list. * @return the head of this list, or null if this list is empty. * @since 1.5 */ public E poll() { if (size==0) return null; return removeFirst(); } /** * Retrieves and removes the head (first element) of this list. * @return the head of this list. * @throws NoSuchElementException if this list is empty. * @since 1.5 */ public E remove() { return removeFirst(); } /** * Adds the specified element as the tail (last element) of this list. * * @param o the element to add. * @return true (as per the general contract of * Queue.offer) * @since 1.5 */ public boolean offer(E o) { return add(o); } // Deque operations /** * Inserts the specified element to the front of this list. * * @param o the element to insert * @return true (as per the spec for {@link Deque#offerFirst}) * @since 1.6 */ public boolean offerFirst(E o) { addFirst(o); return true; } /** * Inserts the specified element to the end of this list. * * @param o the element to insert * @return true (as per the spec for {@link Deque#offerLast}) * @since 1.6 */ public boolean offerLast(E o) { addLast(o); return true; } /** * Retrieves, but does not remove, the first element of this list, * returning null if this list is empty. * * @return the first element of this list, or null if * this list is empty * @since 1.6 */ public E peekFirst() { if (size==0) return null; return getFirst(); } /** * Retrieves, but does not remove, the last element of this list, * returning null if this list is empty. * * @return the last element of this list, or null if this list * is empty * @since 1.6 */ public E peekLast() { if (size==0) return null; return getLast(); } /** * Retrieves and removes the first element of this list, or * null if this list is empty. * * @return the first element of this list, or null if * this list is empty * @since 1.6 */ public E pollFirst() { if (size==0) return null; return removeFirst(); } /** * Retrieves and removes the last element of this list, or * null if this list is empty. * * @return the last element of this list, or null if * this list is empty * @since 1.6 */ public E pollLast() { if (size==0) return null; return removeLast(); } /** * Pushes an element onto the stack represented by this list. In other * words, inserts the element to the front of this list. * *

This method is equivalent to {@link #addFirst}. * * @param o the element to push * @since 1.6 */ public void push(E o) { addFirst(o); } /** * Pops an element from the stack represented by this list. In other * words, removes and returns the first element of this list. * *

This method is equivalent to {@link #removeFirst()}. * * @return the element at the front of this list (which is the top * of the stack represented by this list) * @throws NoSuchElementException if this list is empty * @since 1.6 */ public E pop() { return removeFirst(); } /** * Removes the first occurrence of the specified element in this * list (when traversing the list from head to tail). If the list * does not contain the element, it is unchanged. * * @param o element to be removed from this list, if present * @return true if the list contained the specified element * @since 1.6 */ public boolean removeFirstOccurrence(Object o) { return remove(o); } /** * Removes the last occurrence of the specified element in this * list (when traversing the list from head to tail). If the list * does not contain the element, it is unchanged. * * @param o element to be removed from this list, if present * @return true if the list contained the specified element * @since 1.6 */ public boolean removeLastOccurrence(Object o) { if (o==null) { for (Entry e = header.previous; e != header; e = e.previous) { if (e.element==null) { remove(e); return true; } } } else { for (Entry e = header.previous; e != header; e = e.previous) { if (o.equals(e.element)) { remove(e); return true; } } } return false; } /** * Returns a list-iterator of the elements in this list (in proper * sequence), starting at the specified position in the list. * Obeys the general contract of List.listIterator(int).

* * The list-iterator is fail-fast: if the list is structurally * modified at any time after the Iterator is created, in any way except * through the list-iterator's own remove or add * methods, the list-iterator will throw a * ConcurrentModificationException. Thus, in the face of * concurrent modification, the iterator fails quickly and cleanly, rather * than risking arbitrary, non-deterministic behavior at an undetermined * time in the future. * * @param index index of first element to be returned from the * list-iterator (by a call to next). * @return a ListIterator of the elements in this list (in proper * sequence), starting at the specified position in the list. * @throws IndexOutOfBoundsException if index is out of range * (index < 0 || index > size()). * @see List#listIterator(int) */ public ListIterator listIterator(int index) { return new ListItr(index); } private class ListItr implements ListIterator { private Entry lastReturned = header; private Entry next; private int nextIndex; private int expectedModCount = modCount; ListItr(int index) { if (index < 0 || index > size) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); if (index < (size >> 1)) { next = header.next; for (nextIndex=0; nextIndexindex; nextIndex--) next = next.previous; } } public boolean hasNext() { return nextIndex != size; } public E next() { checkForComodification(); if (nextIndex == size) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; return lastReturned.element; } public boolean hasPrevious() { return nextIndex != 0; } public E previous() { if (nextIndex == 0) throw new NoSuchElementException(); lastReturned = next = next.previous; nextIndex--; checkForComodification(); return lastReturned.element; } public int nextIndex() { return nextIndex; } public int previousIndex() { return nextIndex-1; } public void remove() { checkForComodification(); Entry lastNext = lastReturned.next; try { LinkedList.this.remove(lastReturned); } catch (NoSuchElementException e) { throw new IllegalStateException(); } if (next==lastReturned) next = lastNext; else nextIndex--; lastReturned = header; expectedModCount++; } public void set(E o) { if (lastReturned == header) throw new IllegalStateException(); checkForComodification(); lastReturned.element = o; } public void add(E o) { checkForComodification(); lastReturned = header; addBefore(o, next); nextIndex++; expectedModCount++; } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } } private static class Entry { E element; Entry next; Entry previous; Entry(E element, Entry next, Entry previous) { this.element = element; this.next = next; this.previous = previous; } } private Entry addBefore(E o, Entry e) { Entry newEntry = new Entry(o, e, e.previous); newEntry.previous.next = newEntry; newEntry.next.previous = newEntry; size++; modCount++; return newEntry; } private E remove(Entry e) { if (e == header) throw new NoSuchElementException(); E result = e.element; e.previous.next = e.next; e.next.previous = e.previous; e.next = e.previous = null; e.element = null; size--; modCount++; return result; } /** * Returns a shallow copy of this LinkedList. (The elements * themselves are not cloned.) * * @return a shallow copy of this LinkedList instance. */ public Object clone() { LinkedList clone = null; try { clone = (LinkedList) super.clone(); } catch (CloneNotSupportedException e) { throw new InternalError(); } // Put clone into "virgin" state clone.header = new Entry(null, null, null); clone.header.next = clone.header.previous = clone.header; clone.size = 0; clone.modCount = 0; // Initialize clone with our elements for (Entry e = header.next; e != header; e = e.next) clone.add(e.element); return clone; } /** * Returns an array containing all of the elements in this list * in the correct order. * * @return an array containing all of the elements in this list * in the correct order. */ public Object[] toArray() { Object[] result = new Object[size]; int i = 0; for (Entry e = header.next; e != header; e = e.next) result[i++] = e.element; return result; } /** * Returns an array containing all of the elements in this list in * the correct order; the runtime type of the returned array is that of * the specified array. If the list fits in the specified array, it * is returned therein. Otherwise, a new array is allocated with the * runtime type of the specified array and the size of this list.

* * If the list fits in the specified array with room to spare * (i.e., the array has more elements than the list), * the element in the array immediately following the end of the * collection is set to null. This is useful in determining the length * of the list only if the caller knows that the list * does not contain any null elements. * * @param a the array into which the elements of the list are to * be stored, if it is big enough; otherwise, a new array of the * same runtime type is allocated for this purpose. * @return an array containing the elements of the list. * @throws ArrayStoreException if the runtime type of a is not a * supertype of the runtime type of every element in this list. * @throws NullPointerException if the specified array is null. */ public T[] toArray(T[] a) { if (a.length < size) a = (T[])java.lang.reflect.Array.newInstance( a.getClass().getComponentType(), size); int i = 0; Object[] result = a; for (Entry e = header.next; e != header; e = e.next) result[i++] = e.element; if (a.length > size) a[size] = null; return a; } private static final long serialVersionUID = 876323262645176354L; /** * Save the state of this LinkedList instance to a stream (that * is, serialize it). * * @serialData The size of the list (the number of elements it * contains) is emitted (int), followed by all of its * elements (each an Object) in the proper order. */ private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { // Write out any hidden serialization magic s.defaultWriteObject(); // Write out size s.writeInt(size); // Write out all elements in the proper order. for (Entry e = header.next; e != header; e = e.next) s.writeObject(e.element); } /** * Reconstitute this LinkedList instance from a stream (that is * deserialize it). */ private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { // Read in any hidden serialization magic s.defaultReadObject(); // Read in size int size = s.readInt(); // Initialize header header = new Entry(null, null, null); header.next = header.previous = header; // Read in all elements in the proper order. for (int i=0; i