0N/A/*
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 *
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 *
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 *
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.
0N/A *
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
2362N/A * questions.
0N/A */
0N/A
0N/Apackage java.util;
0N/A
0N/A/**
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}).
0N/A *
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 *
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 *
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>
0N/A *
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 *
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 *
0N/A * <p>This class is a member of the
0N/A * <a href="{@docRoot}/../technotes/guides/collections/index.html">
0N/A * Java Collections Framework</a>.
0N/A *
0N/A * @author Josh Bloch
0N/A * @see List
0N/A * @see ArrayList
0N/A * @since 1.2
0N/A * @param <E> the type of elements held in this collection
0N/A */
0N/A
0N/Apublic class LinkedList<E>
0N/A extends AbstractSequentialList<E>
0N/A implements List<E>, Deque<E>, Cloneable, java.io.Serializable
0N/A{
1818N/A transient int size = 0;
1818N/A
1818N/A /**
1818N/A * Pointer to first node.
1818N/A * Invariant: (first == null && last == null) ||
1818N/A * (first.prev == null && first.item != null)
1818N/A */
1818N/A transient Node<E> first;
1818N/A
1818N/A /**
1818N/A * Pointer to last node.
1818N/A * Invariant: (first == null && last == null) ||
1818N/A * (last.next == null && last.item != null)
1818N/A */
1818N/A transient Node<E> last;
0N/A
0N/A /**
0N/A * Constructs an empty list.
0N/A */
0N/A public LinkedList() {
0N/A }
0N/A
0N/A /**
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 * iterator.
0N/A *
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
0N/A */
0N/A public LinkedList(Collection<? extends E> c) {
0N/A this();
0N/A addAll(c);
0N/A }
0N/A
0N/A /**
1818N/A * Links e as first element.
1818N/A */
1818N/A private void linkFirst(E e) {
1818N/A final Node<E> f = first;
3323N/A final Node<E> newNode = new Node<>(null, e, f);
1818N/A first = newNode;
1818N/A if (f == null)
1818N/A last = newNode;
1818N/A else
1818N/A f.prev = newNode;
1818N/A size++;
1818N/A modCount++;
1818N/A }
1818N/A
1818N/A /**
1818N/A * Links e as last element.
1818N/A */
1818N/A void linkLast(E e) {
1818N/A final Node<E> l = last;
3323N/A final Node<E> newNode = new Node<>(l, e, null);
1818N/A last = newNode;
1818N/A if (l == null)
1818N/A first = newNode;
1818N/A else
1818N/A l.next = newNode;
1818N/A size++;
1818N/A modCount++;
1818N/A }
1818N/A
1818N/A /**
1818N/A * Inserts element e before non-null Node succ.
1818N/A */
1818N/A void linkBefore(E e, Node<E> succ) {
1818N/A // assert succ != null;
1818N/A final Node<E> pred = succ.prev;
3323N/A final Node<E> newNode = new Node<>(pred, e, succ);
1818N/A succ.prev = newNode;
1818N/A if (pred == null)
1818N/A first = newNode;
1818N/A else
1818N/A pred.next = newNode;
1818N/A size++;
1818N/A modCount++;
1818N/A }
1818N/A
1818N/A /**
1818N/A * Unlinks non-null first node f.
1818N/A */
1818N/A private E unlinkFirst(Node<E> f) {
1818N/A // assert f == first && f != null;
1818N/A final E element = f.item;
1818N/A final Node<E> next = f.next;
1818N/A f.item = null;
1818N/A f.next = null; // help GC
1818N/A first = next;
1818N/A if (next == null)
1818N/A last = null;
1818N/A else
1818N/A next.prev = null;
1818N/A size--;
1818N/A modCount++;
1818N/A return element;
1818N/A }
1818N/A
1818N/A /**
1818N/A * Unlinks non-null last node l.
1818N/A */
1818N/A private E unlinkLast(Node<E> l) {
1818N/A // assert l == last && l != null;
1818N/A final E element = l.item;
1818N/A final Node<E> prev = l.prev;
1818N/A l.item = null;
1818N/A l.prev = null; // help GC
1818N/A last = prev;
1818N/A if (prev == null)
1818N/A first = null;
1818N/A else
1818N/A prev.next = null;
1818N/A size--;
1818N/A modCount++;
1818N/A return element;
1818N/A }
1818N/A
1818N/A /**
1818N/A * Unlinks non-null node x.
1818N/A */
1818N/A E unlink(Node<E> x) {
1818N/A // assert x != null;
1818N/A final E element = x.item;
1818N/A final Node<E> next = x.next;
1818N/A final Node<E> prev = x.prev;
1818N/A
1818N/A if (prev == null) {
1818N/A first = next;
1818N/A } else {
1818N/A prev.next = next;
1818N/A x.prev = null;
1818N/A }
1818N/A
1818N/A if (next == null) {
1818N/A last = prev;
1818N/A } else {
1818N/A next.prev = prev;
1818N/A x.next = null;
1818N/A }
1818N/A
1818N/A x.item = null;
1818N/A size--;
1818N/A modCount++;
1818N/A return element;
1818N/A }
1818N/A
1818N/A /**
0N/A * Returns the first element in this list.
0N/A *
0N/A * @return the first element in this list
0N/A * @throws NoSuchElementException if this list is empty
0N/A */
0N/A public E getFirst() {
1818N/A final Node<E> f = first;
1818N/A if (f == null)
0N/A throw new NoSuchElementException();
1818N/A return f.item;
0N/A }
0N/A
0N/A /**
0N/A * Returns the last element in this list.
0N/A *
0N/A * @return the last element in this list
0N/A * @throws NoSuchElementException if this list is empty
0N/A */
3387N/A public E getLast() {
1818N/A final Node<E> l = last;
1818N/A if (l == null)
0N/A throw new NoSuchElementException();
1818N/A return l.item;
0N/A }
0N/A
0N/A /**
0N/A * Removes and returns the first element from this list.
0N/A *
0N/A * @return the first element from this list
0N/A * @throws NoSuchElementException if this list is empty
0N/A */
0N/A public E removeFirst() {
1818N/A final Node<E> f = first;
1818N/A if (f == null)
1818N/A throw new NoSuchElementException();
1818N/A return unlinkFirst(f);
0N/A }
0N/A
0N/A /**
0N/A * Removes and returns the last element from this list.
0N/A *
0N/A * @return the last element from this list
0N/A * @throws NoSuchElementException if this list is empty
0N/A */
0N/A public E removeLast() {
1818N/A final Node<E> l = last;
1818N/A if (l == null)
1818N/A throw new NoSuchElementException();
1818N/A return unlinkLast(l);
0N/A }
0N/A
0N/A /**
0N/A * Inserts the specified element at the beginning of this list.
0N/A *
0N/A * @param e the element to add
0N/A */
0N/A public void addFirst(E e) {
1818N/A linkFirst(e);
0N/A }
0N/A
0N/A /**
0N/A * Appends the specified element to the end of this list.
0N/A *
0N/A * <p>This method is equivalent to {@link #add}.
0N/A *
0N/A * @param e the element to add
0N/A */
0N/A public void addLast(E e) {
1818N/A linkLast(e);
0N/A }
0N/A
0N/A /**
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&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
0N/A *
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 */
0N/A public boolean contains(Object o) {
0N/A return indexOf(o) != -1;
0N/A }
0N/A
0N/A /**
0N/A * Returns the number of elements in this list.
0N/A *
0N/A * @return the number of elements in this list
0N/A */
0N/A public int size() {
0N/A return size;
0N/A }
0N/A
0N/A /**
0N/A * Appends the specified element to the end of this list.
0N/A *
0N/A * <p>This method is equivalent to {@link #addLast}.
0N/A *
0N/A * @param e element to be appended to this list
1818N/A * @return {@code true} (as specified by {@link Collection#add})
0N/A */
0N/A public boolean add(E e) {
1818N/A linkLast(e);
0N/A return true;
0N/A }
0N/A
0N/A /**
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
1818N/A * {@code i} such that
0N/A * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;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 *
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 */
0N/A public boolean remove(Object o) {
1818N/A if (o == null) {
1818N/A for (Node<E> x = first; x != null; x = x.next) {
1818N/A if (x.item == null) {
1818N/A unlink(x);
0N/A return true;
0N/A }
0N/A }
0N/A } else {
1818N/A for (Node<E> x = first; x != null; x = x.next) {
1818N/A if (o.equals(x.item)) {
1818N/A unlink(x);
0N/A return true;
0N/A }
0N/A }
0N/A }
0N/A return false;
0N/A }
0N/A
0N/A /**
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 *
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 */
0N/A public boolean addAll(Collection<? extends E> c) {
0N/A return addAll(size, c);
0N/A }
0N/A
0N/A /**
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 *
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 */
0N/A public boolean addAll(int index, Collection<? extends E> c) {
1818N/A checkPositionIndex(index);
1818N/A
0N/A Object[] a = c.toArray();
0N/A int numNew = a.length;
1818N/A if (numNew == 0)
0N/A return false;
1818N/A
1818N/A Node<E> pred, succ;
1818N/A if (index == size) {
1818N/A succ = null;
1818N/A pred = last;
1818N/A } else {
1818N/A succ = node(index);
1818N/A pred = succ.prev;
1818N/A }
0N/A
1818N/A for (Object o : a) {
1818N/A @SuppressWarnings("unchecked") E e = (E) o;
3323N/A Node<E> newNode = new Node<>(pred, e, null);
1818N/A if (pred == null)
1818N/A first = newNode;
1818N/A else
1818N/A pred.next = newNode;
1818N/A pred = newNode;
0N/A }
1818N/A
1818N/A if (succ == null) {
1818N/A last = pred;
1818N/A } else {
1818N/A pred.next = succ;
1818N/A succ.prev = pred;
1818N/A }
0N/A
0N/A size += numNew;
1818N/A modCount++;
0N/A return true;
0N/A }
0N/A
0N/A /**
0N/A * Removes all of the elements from this list.
1818N/A * The list will be empty after this call returns.
0N/A */
0N/A public void clear() {
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
1818N/A for (Node<E> x = first; x != null; ) {
1818N/A Node<E> next = x.next;
1818N/A x.item = null;
1818N/A x.next = null;
1818N/A x.prev = null;
1818N/A x = next;
0N/A }
1818N/A first = last = null;
0N/A size = 0;
0N/A modCount++;
0N/A }
0N/A
0N/A
0N/A // Positional Access Operations
0N/A
0N/A /**
0N/A * Returns the element at the specified position in this list.
0N/A *
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 */
0N/A public E get(int index) {
1818N/A checkElementIndex(index);
1818N/A return node(index).item;
0N/A }
0N/A
0N/A /**
0N/A * Replaces the element at the specified position in this list with the
0N/A * specified element.
0N/A *
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 */
0N/A public E set(int index, E element) {
1818N/A checkElementIndex(index);
1818N/A Node<E> x = node(index);
1818N/A E oldVal = x.item;
1818N/A x.item = element;
0N/A return oldVal;
0N/A }
0N/A
0N/A /**
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 *
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 */
0N/A public void add(int index, E element) {
1818N/A checkPositionIndex(index);
1818N/A
1818N/A if (index == size)
1818N/A linkLast(element);
1818N/A else
1818N/A linkBefore(element, node(index));
0N/A }
0N/A
0N/A /**
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 *
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}
0N/A */
0N/A public E remove(int index) {
1818N/A checkElementIndex(index);
1818N/A return unlink(node(index));
1818N/A }
1818N/A
1818N/A /**
1818N/A * Tells if the argument is the index of an existing element.
1818N/A */
1818N/A private boolean isElementIndex(int index) {
1818N/A return index >= 0 && index < size;
1818N/A }
1818N/A
1818N/A /**
1818N/A * Tells if the argument is the index of a valid position for an
1818N/A * iterator or an add operation.
1818N/A */
1818N/A private boolean isPositionIndex(int index) {
1818N/A return index >= 0 && index <= size;
0N/A }
0N/A
0N/A /**
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.
0N/A */
1818N/A private String outOfBoundsMsg(int index) {
1818N/A return "Index: "+index+", Size: "+size;
1818N/A }
1818N/A
1818N/A private void checkElementIndex(int index) {
1818N/A if (!isElementIndex(index))
1818N/A throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1818N/A }
1818N/A
1818N/A private void checkPositionIndex(int index) {
1818N/A if (!isPositionIndex(index))
1818N/A throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
0N/A }
0N/A
1818N/A /**
1818N/A * Returns the (non-null) Node at the specified element index.
1818N/A */
1818N/A Node<E> node(int index) {
1818N/A // assert isElementIndex(index);
1818N/A
1818N/A if (index < (size >> 1)) {
1818N/A Node<E> x = first;
1818N/A for (int i = 0; i < index; i++)
1818N/A x = x.next;
1818N/A return x;
1818N/A } else {
1818N/A Node<E> x = last;
1818N/A for (int i = size - 1; i > index; i--)
1818N/A x = x.prev;
1818N/A return x;
1818N/A }
1818N/A }
0N/A
0N/A // Search Operations
0N/A
0N/A /**
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&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
0N/A * or -1 if there is no such index.
0N/A *
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 */
0N/A public int indexOf(Object o) {
0N/A int index = 0;
1818N/A if (o == null) {
1818N/A for (Node<E> x = first; x != null; x = x.next) {
1818N/A if (x.item == null)
0N/A return index;
0N/A index++;
0N/A }
0N/A } else {
1818N/A for (Node<E> x = first; x != null; x = x.next) {
1818N/A if (o.equals(x.item))
0N/A return index;
0N/A index++;
0N/A }
0N/A }
0N/A return -1;
0N/A }
0N/A
0N/A /**
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&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
0N/A * or -1 if there is no such index.
0N/A *
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 */
0N/A public int lastIndexOf(Object o) {
0N/A int index = size;
1818N/A if (o == null) {
1818N/A for (Node<E> x = last; x != null; x = x.prev) {
0N/A index--;
1818N/A if (x.item == null)
0N/A return index;
0N/A }
0N/A } else {
1818N/A for (Node<E> x = last; x != null; x = x.prev) {
0N/A index--;
1818N/A if (o.equals(x.item))
0N/A return index;
0N/A }
0N/A }
0N/A return -1;
0N/A }
0N/A
0N/A // Queue operations.
0N/A
0N/A /**
0N/A * Retrieves, but does not remove, the head (first element) of this list.
1818N/A *
1818N/A * @return the head of this list, or {@code null} if this list is empty
0N/A * @since 1.5
0N/A */
0N/A public E peek() {
1818N/A final Node<E> f = first;
1818N/A return (f == null) ? null : f.item;
0N/A }
0N/A
0N/A /**
0N/A * Retrieves, but does not remove, the head (first element) of this list.
1818N/A *
0N/A * @return the head of this list
0N/A * @throws NoSuchElementException if this list is empty
0N/A * @since 1.5
0N/A */
0N/A public E element() {
0N/A return getFirst();
0N/A }
0N/A
0N/A /**
1818N/A * Retrieves and removes the head (first element) of this list.
1818N/A *
1818N/A * @return the head of this list, or {@code null} if this list is empty
0N/A * @since 1.5
0N/A */
0N/A public E poll() {
1818N/A final Node<E> f = first;
1818N/A return (f == null) ? null : unlinkFirst(f);
0N/A }
0N/A
0N/A /**
0N/A * Retrieves and removes the head (first element) of this list.
0N/A *
0N/A * @return the head of this list
0N/A * @throws NoSuchElementException if this list is empty
0N/A * @since 1.5
0N/A */
0N/A public E remove() {
0N/A return removeFirst();
0N/A }
0N/A
0N/A /**
0N/A * Adds the specified element as the tail (last element) of this list.
0N/A *
0N/A * @param e the element to add
1818N/A * @return {@code true} (as specified by {@link Queue#offer})
0N/A * @since 1.5
0N/A */
0N/A public boolean offer(E e) {
0N/A return add(e);
0N/A }
0N/A
0N/A // Deque operations
0N/A /**
0N/A * Inserts the specified element at the front of this list.
0N/A *
0N/A * @param e the element to insert
1818N/A * @return {@code true} (as specified by {@link Deque#offerFirst})
0N/A * @since 1.6
0N/A */
0N/A public boolean offerFirst(E e) {
0N/A addFirst(e);
0N/A return true;
0N/A }
0N/A
0N/A /**
0N/A * Inserts the specified element at the end of this list.
0N/A *
0N/A * @param e the element to insert
1818N/A * @return {@code true} (as specified by {@link Deque#offerLast})
0N/A * @since 1.6
0N/A */
0N/A public boolean offerLast(E e) {
0N/A addLast(e);
0N/A return true;
0N/A }
0N/A
0N/A /**
0N/A * Retrieves, but does not remove, the first element of this list,
1818N/A * or returns {@code null} if this list is empty.
0N/A *
1818N/A * @return the first element of this list, or {@code null}
0N/A * if this list is empty
0N/A * @since 1.6
0N/A */
0N/A public E peekFirst() {
1818N/A final Node<E> f = first;
1818N/A return (f == null) ? null : f.item;
1818N/A }
0N/A
0N/A /**
0N/A * Retrieves, but does not remove, the last element of this list,
1818N/A * or returns {@code null} if this list is empty.
0N/A *
1818N/A * @return the last element of this list, or {@code null}
0N/A * if this list is empty
0N/A * @since 1.6
0N/A */
0N/A public E peekLast() {
1818N/A final Node<E> l = last;
1818N/A return (l == null) ? null : l.item;
0N/A }
0N/A
0N/A /**
0N/A * Retrieves and removes the first element of this list,
1818N/A * or returns {@code null} if this list is empty.
0N/A *
1818N/A * @return the first element of this list, or {@code null} if
0N/A * this list is empty
0N/A * @since 1.6
0N/A */
0N/A public E pollFirst() {
1818N/A final Node<E> f = first;
1818N/A return (f == null) ? null : unlinkFirst(f);
0N/A }
0N/A
0N/A /**
0N/A * Retrieves and removes the last element of this list,
1818N/A * or returns {@code null} if this list is empty.
0N/A *
1818N/A * @return the last element of this list, or {@code null} if
0N/A * this list is empty
0N/A * @since 1.6
0N/A */
0N/A public E pollLast() {
1818N/A final Node<E> l = last;
1818N/A return (l == null) ? null : unlinkLast(l);
0N/A }
0N/A
0N/A /**
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 *
0N/A * <p>This method is equivalent to {@link #addFirst}.
0N/A *
0N/A * @param e the element to push
0N/A * @since 1.6
0N/A */
0N/A public void push(E e) {
0N/A addFirst(e);
0N/A }
0N/A
0N/A /**
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 *
0N/A * <p>This method is equivalent to {@link #removeFirst()}.
0N/A *
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 * @since 1.6
0N/A */
0N/A public E pop() {
0N/A return removeFirst();
0N/A }
0N/A
0N/A /**
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 *
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 * @since 1.6
0N/A */
0N/A public boolean removeFirstOccurrence(Object o) {
0N/A return remove(o);
0N/A }
0N/A
0N/A /**
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 *
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 * @since 1.6
0N/A */
0N/A public boolean removeLastOccurrence(Object o) {
1818N/A if (o == null) {
1818N/A for (Node<E> x = last; x != null; x = x.prev) {
1818N/A if (x.item == null) {
1818N/A unlink(x);
0N/A return true;
0N/A }
0N/A }
0N/A } else {
1818N/A for (Node<E> x = last; x != null; x = x.prev) {
1818N/A if (o.equals(x.item)) {
1818N/A unlink(x);
0N/A return true;
0N/A }
0N/A }
0N/A }
0N/A return false;
0N/A }
0N/A
0N/A /**
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 *
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 *
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)
0N/A */
0N/A public ListIterator<E> listIterator(int index) {
1818N/A checkPositionIndex(index);
0N/A return new ListItr(index);
0N/A }
0N/A
0N/A private class ListItr implements ListIterator<E> {
1818N/A private Node<E> lastReturned = null;
1818N/A private Node<E> next;
0N/A private int nextIndex;
0N/A private int expectedModCount = modCount;
0N/A
0N/A ListItr(int index) {
1818N/A // assert isPositionIndex(index);
1818N/A next = (index == size) ? null : node(index);
1818N/A nextIndex = index;
0N/A }
0N/A
0N/A public boolean hasNext() {
1818N/A return nextIndex < size;
0N/A }
0N/A
0N/A public E next() {
0N/A checkForComodification();
1818N/A if (!hasNext())
0N/A throw new NoSuchElementException();
0N/A
0N/A lastReturned = next;
0N/A next = next.next;
0N/A nextIndex++;
1818N/A return lastReturned.item;
0N/A }
0N/A
0N/A public boolean hasPrevious() {
1818N/A return nextIndex > 0;
0N/A }
0N/A
0N/A public E previous() {
1818N/A checkForComodification();
1818N/A if (!hasPrevious())
0N/A throw new NoSuchElementException();
0N/A
1818N/A lastReturned = next = (next == null) ? last : next.prev;
0N/A nextIndex--;
1818N/A return lastReturned.item;
0N/A }
0N/A
0N/A public int nextIndex() {
0N/A return nextIndex;
0N/A }
0N/A
0N/A public int previousIndex() {
1818N/A return nextIndex - 1;
0N/A }
0N/A
0N/A public void remove() {
0N/A checkForComodification();
1818N/A if (lastReturned == null)
0N/A throw new IllegalStateException();
1818N/A
1818N/A Node<E> lastNext = lastReturned.next;
1818N/A unlink(lastReturned);
1818N/A if (next == lastReturned)
0N/A next = lastNext;
0N/A else
0N/A nextIndex--;
1818N/A lastReturned = null;
0N/A expectedModCount++;
0N/A }
0N/A
0N/A public void set(E e) {
1818N/A if (lastReturned == null)
0N/A throw new IllegalStateException();
0N/A checkForComodification();
1818N/A lastReturned.item = e;
0N/A }
0N/A
0N/A public void add(E e) {
0N/A checkForComodification();
1818N/A lastReturned = null;
1818N/A if (next == null)
1818N/A linkLast(e);
1818N/A else
1818N/A linkBefore(e, next);
0N/A nextIndex++;
0N/A expectedModCount++;
0N/A }
0N/A
0N/A final void checkForComodification() {
0N/A if (modCount != expectedModCount)
0N/A throw new ConcurrentModificationException();
0N/A }
0N/A }
0N/A
1818N/A private static class Node<E> {
1818N/A E item;
1818N/A Node<E> next;
1818N/A Node<E> prev;
0N/A
1818N/A Node(Node<E> prev, E element, Node<E> next) {
1818N/A this.item = element;
1818N/A this.next = next;
1818N/A this.prev = prev;
1818N/A }
0N/A }
0N/A
0N/A /**
0N/A * @since 1.6
0N/A */
0N/A public Iterator<E> descendingIterator() {
0N/A return new DescendingIterator();
0N/A }
0N/A
1818N/A /**
1818N/A * Adapter to provide descending iterators via ListItr.previous
1818N/A */
1818N/A private class DescendingIterator implements Iterator<E> {
1818N/A private final ListItr itr = new ListItr(size());
0N/A public boolean hasNext() {
0N/A return itr.hasPrevious();
0N/A }
0N/A public E next() {
0N/A return itr.previous();
0N/A }
0N/A public void remove() {
0N/A itr.remove();
0N/A }
0N/A }
0N/A
1818N/A @SuppressWarnings("unchecked")
1818N/A private LinkedList<E> superClone() {
0N/A try {
1818N/A return (LinkedList<E>) super.clone();
0N/A } catch (CloneNotSupportedException e) {
0N/A throw new InternalError();
0N/A }
1818N/A }
1818N/A
1818N/A /**
1818N/A * Returns a shallow copy of this {@code LinkedList}. (The elements
1818N/A * themselves are not cloned.)
1818N/A *
1818N/A * @return a shallow copy of this {@code LinkedList} instance
1818N/A */
1818N/A public Object clone() {
1818N/A LinkedList<E> clone = superClone();
0N/A
0N/A // Put clone into "virgin" state
1818N/A clone.first = clone.last = null;
0N/A clone.size = 0;
0N/A clone.modCount = 0;
0N/A
0N/A // Initialize clone with our elements
1818N/A for (Node<E> x = first; x != null; x = x.next)
1818N/A clone.add(x.item);
0N/A
0N/A return clone;
0N/A }
0N/A
0N/A /**
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 *
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 *
0N/A * <p>This method acts as bridge between array-based and collection-based
0N/A * APIs.
0N/A *
0N/A * @return an array containing all of the elements in this list
0N/A * in proper sequence
0N/A */
0N/A public Object[] toArray() {
0N/A Object[] result = new Object[size];
0N/A int i = 0;
1818N/A for (Node<E> x = first; x != null; x = x.next)
1818N/A result[i++] = x.item;
0N/A return result;
0N/A }
0N/A
0N/A /**
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 *
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 *
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.
0N/A *
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 *
0N/A * <pre>
0N/A * String[] y = x.toArray(new String[0]);</pre>
0N/A *
1818N/A * Note that {@code toArray(new Object[0])} is identical in function to
1818N/A * {@code toArray()}.
0N/A *
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 * this list
0N/A * @throws NullPointerException if the specified array is null
0N/A */
1818N/A @SuppressWarnings("unchecked")
0N/A public <T> T[] toArray(T[] a) {
0N/A if (a.length < size)
0N/A a = (T[])java.lang.reflect.Array.newInstance(
0N/A a.getClass().getComponentType(), size);
0N/A int i = 0;
0N/A Object[] result = a;
1818N/A for (Node<E> x = first; x != null; x = x.next)
1818N/A result[i++] = x.item;
0N/A
0N/A if (a.length > size)
0N/A a[size] = null;
0N/A
0N/A return a;
0N/A }
0N/A
0N/A private static final long serialVersionUID = 876323262645176354L;
0N/A
0N/A /**
1818N/A * Saves the state of this {@code LinkedList} instance to a stream
1818N/A * (that is, serializes it).
0N/A *
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 */
0N/A private void writeObject(java.io.ObjectOutputStream s)
0N/A throws java.io.IOException {
0N/A // Write out any hidden serialization magic
0N/A s.defaultWriteObject();
0N/A
0N/A // Write out size
0N/A s.writeInt(size);
0N/A
0N/A // Write out all elements in the proper order.
1818N/A for (Node<E> x = first; x != null; x = x.next)
1818N/A s.writeObject(x.item);
0N/A }
0N/A
0N/A /**
1818N/A * Reconstitutes this {@code LinkedList} instance from a stream
1818N/A * (that is, deserializes it).
0N/A */
1818N/A @SuppressWarnings("unchecked")
0N/A private void readObject(java.io.ObjectInputStream s)
0N/A throws java.io.IOException, ClassNotFoundException {
0N/A // Read in any hidden serialization magic
0N/A s.defaultReadObject();
0N/A
0N/A // Read in size
0N/A int size = s.readInt();
0N/A
0N/A // Read in all elements in the proper order.
1818N/A for (int i = 0; i < size; i++)
1818N/A linkLast((E)s.readObject());
0N/A }
0N/A}