3909N/A * Copyright (c) 1997, 2011, Oracle and/or its affiliates. All rights reserved. 0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 0N/A * This code is free software; you can redistribute it and/or modify it 0N/A * under the terms of the GNU General Public License version 2 only, as 2362N/A * published by the Free Software Foundation. Oracle designates this 0N/A * particular file as subject to the "Classpath" exception as provided 2362N/A * by Oracle in the LICENSE file that accompanied this code. 0N/A * This code is distributed in the hope that it will be useful, but WITHOUT 0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 0N/A * version 2 for more details (a copy is included in the LICENSE file that 0N/A * accompanied this code). 0N/A * You should have received a copy of the GNU General Public License version 0N/A * 2 along with this work; if not, write to the Free Software Foundation, 0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 2362N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 2362N/A * or visit www.oracle.com if you need additional information or have any 3387N/A * Doubly-linked list implementation of the {@code List} and {@code Deque} 3387N/A * interfaces. Implements all optional list operations, and permits all 3387N/A * elements (including {@code null}). 1818N/A * <p>All of the operations perform as could be expected for a doubly-linked 0N/A * list. Operations that index into the list will traverse the list from 1818N/A * the beginning or the end, whichever is closer to the specified index. 0N/A * <p><strong>Note that this implementation is not synchronized.</strong> 0N/A * If multiple threads access a linked list concurrently, and at least 0N/A * one of the threads modifies the list structurally, it <i>must</i> be 0N/A * synchronized externally. (A structural modification is any operation 0N/A * that adds or deletes one or more elements; merely setting the value of 0N/A * an element is not a structural modification.) This is typically 0N/A * accomplished by synchronizing on some object that naturally 0N/A * encapsulates the list. 0N/A * If no such object exists, the list should be "wrapped" using the 0N/A * {@link Collections#synchronizedList Collections.synchronizedList} 0N/A * method. This is best done at creation time, to prevent accidental 0N/A * unsynchronized access to the list:<pre> 0N/A * List list = Collections.synchronizedList(new LinkedList(...));</pre> 1818N/A * <p>The iterators returned by this class's {@code iterator} and 1818N/A * {@code listIterator} methods are <i>fail-fast</i>: if the list is 0N/A * structurally modified at any time after the iterator is created, in 1818N/A * any way except through the Iterator's own {@code remove} or 1818N/A * {@code add} methods, the iterator will throw a {@link 0N/A * ConcurrentModificationException}. Thus, in the face of concurrent 0N/A * modification, the iterator fails quickly and cleanly, rather than 0N/A * risking arbitrary, non-deterministic behavior at an undetermined 0N/A * time in the future. 0N/A * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed 0N/A * as it is, generally speaking, impossible to make any hard guarantees in the 0N/A * presence of unsynchronized concurrent modification. Fail-fast iterators 1818N/A * throw {@code ConcurrentModificationException} on a best-effort basis. 0N/A * Therefore, it would be wrong to write a program that depended on this 0N/A * exception for its correctness: <i>the fail-fast behavior of iterators 0N/A * should be used only to detect bugs.</i> 0N/A * <p>This class is a member of the 0N/A * Java Collections Framework</a>. 0N/A * @author Josh Bloch 0N/A * @param <E> the type of elements held in this collection 1818N/A * Invariant: (first == null && last == null) || 1818N/A * (first.prev == null && first.item != null) 1818N/A * Invariant: (first == null && last == null) || 1818N/A * (last.next == null && last.item != null) 0N/A * Constructs an empty list. 0N/A * Constructs a list containing the elements of the specified 0N/A * collection, in the order they are returned by the collection's 0N/A * @param c the collection whose elements are to be placed into this list 0N/A * @throws NullPointerException if the specified collection is null 1818N/A * Links e as first element. 1818N/A * Inserts element e before non-null Node succ. 1818N/A * Unlinks non-null first node f. 1818N/A // assert f == first && f != null; 1818N/A * Unlinks non-null last node l. 1818N/A // assert l == last && l != null; 0N/A * Returns the first element in this list. 0N/A * @return the first element in this list 0N/A * @throws NoSuchElementException if this list is empty 0N/A * Returns the last element in this list. 0N/A * @return the last element in this list 0N/A * @throws NoSuchElementException if this list is empty 0N/A * Removes and returns the first element from this list. 0N/A * @return the first element from this list 0N/A * @throws NoSuchElementException if this list is empty 0N/A * Removes and returns the last element from this list. 0N/A * @return the last element from this list 0N/A * @throws NoSuchElementException if this list is empty 0N/A * Inserts the specified element at the beginning of this list. 0N/A * @param e the element to add 0N/A * Appends the specified element to the end of this list. 0N/A * <p>This method is equivalent to {@link #add}. 0N/A * @param e the element to add 1818N/A * Returns {@code true} if this list contains the specified element. 1818N/A * More formally, returns {@code true} if and only if this list contains 1818N/A * at least one element {@code e} such that 0N/A * <tt>(o==null ? e==null : o.equals(e))</tt>. 0N/A * @param o element whose presence in this list is to be tested 1818N/A * @return {@code true} if this list contains the specified element 0N/A * Returns the number of elements in this list. 0N/A * @return the number of elements in this list 0N/A * Appends the specified element to the end of this list. 0N/A * <p>This method is equivalent to {@link #addLast}. 0N/A * @param e element to be appended to this list 1818N/A * @return {@code true} (as specified by {@link Collection#add}) 0N/A * Removes the first occurrence of the specified element from this list, 0N/A * if it is present. If this list does not contain the element, it is 0N/A * unchanged. More formally, removes the element with the lowest index 0N/A * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> 1818N/A * (if such an element exists). Returns {@code true} if this list 0N/A * contained the specified element (or equivalently, if this list 0N/A * changed as a result of the call). 0N/A * @param o element to be removed from this list, if present 1818N/A * @return {@code true} if this list contained the specified element 0N/A * Appends all of the elements in the specified collection to the end of 0N/A * this list, in the order that they are returned by the specified 0N/A * collection's iterator. The behavior of this operation is undefined if 0N/A * the specified collection is modified while the operation is in 0N/A * progress. (Note that this will occur if the specified collection is 0N/A * this list, and it's nonempty.) 0N/A * @param c collection containing elements to be added to this list 1818N/A * @return {@code true} if this list changed as a result of the call 0N/A * @throws NullPointerException if the specified collection is null 0N/A * Inserts all of the elements in the specified collection into this 0N/A * list, starting at the specified position. Shifts the element 0N/A * currently at that position (if any) and any subsequent elements to 0N/A * the right (increases their indices). The new elements will appear 0N/A * in the list in the order that they are returned by the 0N/A * specified collection's iterator. 0N/A * @param index index at which to insert the first element 0N/A * from the specified collection 0N/A * @param c collection containing elements to be added to this list 1818N/A * @return {@code true} if this list changed as a result of the call 0N/A * @throws IndexOutOfBoundsException {@inheritDoc} 0N/A * @throws NullPointerException if the specified collection is null 0N/A * Removes all of the elements from this list. 1818N/A * The list will be empty after this call returns. 1818N/A // Clearing all of the links between nodes is "unnecessary", but: 1818N/A // - helps a generational GC if the discarded nodes inhabit 1818N/A // more than one generation 1818N/A // - is sure to free memory even if there is a reachable Iterator 0N/A // Positional Access Operations 0N/A * Returns the element at the specified position in this list. 0N/A * @param index index of the element to return 0N/A * @return the element at the specified position in this list 0N/A * @throws IndexOutOfBoundsException {@inheritDoc} 0N/A * Replaces the element at the specified position in this list with the 0N/A * specified element. 0N/A * @param index index of the element to replace 0N/A * @param element element to be stored at the specified position 0N/A * @return the element previously at the specified position 0N/A * @throws IndexOutOfBoundsException {@inheritDoc} 0N/A * Inserts the specified element at the specified position in this list. 0N/A * Shifts the element currently at that position (if any) and any 0N/A * subsequent elements to the right (adds one to their indices). 0N/A * @param index index at which the specified element is to be inserted 0N/A * @param element element to be inserted 0N/A * @throws IndexOutOfBoundsException {@inheritDoc} 0N/A * Removes the element at the specified position in this list. Shifts any 0N/A * subsequent elements to the left (subtracts one from their indices). 0N/A * Returns the element that was removed from the list. 0N/A * @param index the index of the element to be removed 0N/A * @return the element previously at the specified position 0N/A * @throws IndexOutOfBoundsException {@inheritDoc} 1818N/A * Tells if the argument is the index of an existing element. 1818N/A * Tells if the argument is the index of a valid position for an 1818N/A * iterator or an add operation. 1818N/A * Constructs an IndexOutOfBoundsException detail message. 1818N/A * Of the many possible refactorings of the error handling code, 1818N/A * this "outlining" performs best with both server and client VMs. 1818N/A * Returns the (non-null) Node at the specified element index. 1818N/A // assert isElementIndex(index); 0N/A // Search Operations 0N/A * Returns the index of the first occurrence of the specified element 0N/A * in this list, or -1 if this list does not contain the element. 1818N/A * More formally, returns the lowest index {@code i} such that 0N/A * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, 0N/A * or -1 if there is no such index. 0N/A * @param o element to search for 0N/A * @return the index of the first occurrence of the specified element in 0N/A * this list, or -1 if this list does not contain the element 0N/A * Returns the index of the last occurrence of the specified element 0N/A * in this list, or -1 if this list does not contain the element. 1818N/A * More formally, returns the highest index {@code i} such that 0N/A * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, 0N/A * or -1 if there is no such index. 0N/A * @param o element to search for 0N/A * @return the index of the last occurrence of the specified element in 0N/A * this list, or -1 if this list does not contain the element 0N/A // Queue operations. 0N/A * Retrieves, but does not remove, the head (first element) of this list. 1818N/A * @return the head of this list, or {@code null} if this list is empty 0N/A * Retrieves, but does not remove, the head (first element) of this list. 0N/A * @return the head of this list 0N/A * @throws NoSuchElementException if this list is empty 1818N/A * Retrieves and removes the head (first element) of this list. 1818N/A * @return the head of this list, or {@code null} if this list is empty 0N/A * Retrieves and removes the head (first element) of this list. 0N/A * @return the head of this list 0N/A * @throws NoSuchElementException if this list is empty 0N/A * Adds the specified element as the tail (last element) of this list. 0N/A * @param e the element to add 1818N/A * @return {@code true} (as specified by {@link Queue#offer}) 0N/A * Inserts the specified element at the front of this list. 0N/A * @param e the element to insert 1818N/A * @return {@code true} (as specified by {@link Deque#offerFirst}) 0N/A * Inserts the specified element at the end of this list. 0N/A * @param e the element to insert 1818N/A * @return {@code true} (as specified by {@link Deque#offerLast}) 0N/A * Retrieves, but does not remove, the first element of this list, 1818N/A * or returns {@code null} if this list is empty. 1818N/A * @return the first element of this list, or {@code null} 0N/A * if this list is empty 0N/A * Retrieves, but does not remove, the last element of this list, 1818N/A * or returns {@code null} if this list is empty. 1818N/A * @return the last element of this list, or {@code null} 0N/A * if this list is empty 0N/A * Retrieves and removes the first element of this list, 1818N/A * or returns {@code null} if this list is empty. 1818N/A * @return the first element of this list, or {@code null} if 0N/A * this list is empty 0N/A * Retrieves and removes the last element of this list, 1818N/A * or returns {@code null} if this list is empty. 1818N/A * @return the last element of this list, or {@code null} if 0N/A * this list is empty 0N/A * Pushes an element onto the stack represented by this list. In other 0N/A * words, inserts the element at the front of this list. 0N/A * <p>This method is equivalent to {@link #addFirst}. 0N/A * @param e the element to push 0N/A * Pops an element from the stack represented by this list. In other 0N/A * words, removes and returns the first element of this list. 0N/A * <p>This method is equivalent to {@link #removeFirst()}. 0N/A * @return the element at the front of this list (which is the top 0N/A * of the stack represented by this list) 0N/A * @throws NoSuchElementException if this list is empty 0N/A * Removes the first occurrence of the specified element in this 0N/A * list (when traversing the list from head to tail). If the list 0N/A * does not contain the element, it is unchanged. 0N/A * @param o element to be removed from this list, if present 1818N/A * @return {@code true} if the list contained the specified element 0N/A * Removes the last occurrence of the specified element in this 0N/A * list (when traversing the list from head to tail). If the list 0N/A * does not contain the element, it is unchanged. 0N/A * @param o element to be removed from this list, if present 1818N/A * @return {@code true} if the list contained the specified element 0N/A * Returns a list-iterator of the elements in this list (in proper 0N/A * sequence), starting at the specified position in the list. 1818N/A * Obeys the general contract of {@code List.listIterator(int)}.<p> 0N/A * The list-iterator is <i>fail-fast</i>: if the list is structurally 0N/A * modified at any time after the Iterator is created, in any way except 1818N/A * through the list-iterator's own {@code remove} or {@code add} 0N/A * methods, the list-iterator will throw a 1818N/A * {@code ConcurrentModificationException}. Thus, in the face of 0N/A * concurrent modification, the iterator fails quickly and cleanly, rather 0N/A * than risking arbitrary, non-deterministic behavior at an undetermined 0N/A * time in the future. 0N/A * @param index index of the first element to be returned from the 1818N/A * list-iterator (by a call to {@code next}) 0N/A * @return a ListIterator of the elements in this list (in proper 0N/A * sequence), starting at the specified position in the list 0N/A * @throws IndexOutOfBoundsException {@inheritDoc} 0N/A * @see List#listIterator(int) 1818N/A // assert isPositionIndex(index); 1818N/A * Adapter to provide descending iterators via ListItr.previous 1818N/A * Returns a shallow copy of this {@code LinkedList}. (The elements 1818N/A * themselves are not cloned.) 1818N/A * @return a shallow copy of this {@code LinkedList} instance 0N/A // Put clone into "virgin" state 0N/A // Initialize clone with our elements 0N/A * Returns an array containing all of the elements in this list 0N/A * in proper sequence (from first to last element). 0N/A * <p>The returned array will be "safe" in that no references to it are 0N/A * maintained by this list. (In other words, this method must allocate 0N/A * a new array). The caller is thus free to modify the returned array. 0N/A * <p>This method acts as bridge between array-based and collection-based 0N/A * @return an array containing all of the elements in this list 0N/A * in proper sequence 0N/A * Returns an array containing all of the elements in this list in 0N/A * proper sequence (from first to last element); the runtime type of 0N/A * the returned array is that of the specified array. If the list fits 0N/A * in the specified array, it is returned therein. Otherwise, a new 0N/A * array is allocated with the runtime type of the specified array and 0N/A * the size of this list. 0N/A * <p>If the list fits in the specified array with room to spare (i.e., 0N/A * the array has more elements than the list), the element in the array 1818N/A * immediately following the end of the list is set to {@code null}. 0N/A * (This is useful in determining the length of the list <i>only</i> if 0N/A * the caller knows that the list does not contain any null elements.) 0N/A * <p>Like the {@link #toArray()} method, this method acts as bridge between 0N/A * array-based and collection-based APIs. Further, this method allows 0N/A * precise control over the runtime type of the output array, and may, 0N/A * under certain circumstances, be used to save allocation costs. 1818N/A * <p>Suppose {@code x} is a list known to contain only strings. 0N/A * The following code can be used to dump the list into a newly 1818N/A * allocated array of {@code String}: 0N/A * String[] y = x.toArray(new String[0]);</pre> 1818N/A * Note that {@code toArray(new Object[0])} is identical in function to 0N/A * @param a the array into which the elements of the list are to 0N/A * be stored, if it is big enough; otherwise, a new array of the 0N/A * same runtime type is allocated for this purpose. 0N/A * @return an array containing the elements of the list 0N/A * @throws ArrayStoreException if the runtime type of the specified array 0N/A * is not a supertype of the runtime type of every element in 0N/A * @throws NullPointerException if the specified array is null 1818N/A * Saves the state of this {@code LinkedList} instance to a stream 1818N/A * (that is, serializes it). 0N/A * @serialData The size of the list (the number of elements it 0N/A * contains) is emitted (int), followed by all of its 0N/A * elements (each an Object) in the proper order. 0N/A // Write out any hidden serialization magic 0N/A // Write out all elements in the proper order. 1818N/A * Reconstitutes this {@code LinkedList} instance from a stream 1818N/A * (that is, deserializes it). 0N/A // Read in any hidden serialization magic 0N/A // Read in all elements in the proper order.