Java 中Linkedlist类的源代码

/* * @(#)LinkedList.java 1.67 06/04/21 * * Copyright 2006 Sun Microsystems, Inc. All rights reserved. * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. */ package java.util; /** * Linked list implementation of the <tt>List</tt> interface. Implements all * optional list operations, and permits all elements (including * <tt>null</tt>). In addition to implementing the <tt>List</tt> interface, * the <tt>LinkedList</tt> class provides uniformly named methods to * <tt>get</tt>, <tt>remove</tt> and <tt>insert</tt> 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}. <p> * * The class implements the <tt>Deque</tt> interface, providing * first-in-first-out queue operations for <tt>add</tt>, * <tt>poll</tt>, along with other stack and deque operations.<p> * * 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.<p> * * <p><strong>Note that this implementation is not synchronized.</strong> * If multiple threads access a linked list concurrently, and at least * one of the threads modifies the list structurally, it <i>must</i> 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 * {@link Collections#synchronizedList Collections.synchronizedList} * method. This is best done at creation time, to prevent accidental * unsynchronized access to the list:<pre> * List list = Collections.synchronizedList(new LinkedList(...));</pre> * * <p>The iterators returned by this class's <tt>iterator</tt> and * <tt>listIterator</tt> methods are <i>fail-fast</i>: if the list is * structurally modified at any time after the iterator is created, in * any way except through the Iterator's own <tt>remove</tt> or * <tt>add</tt> methods, the iterator will throw a {@link * 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. * * <p>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 <tt>ConcurrentModificationException</tt> on a best-effort basis. * Therefore, it would be wrong to write a program that depended on this * exception for its correctness: <i>the fail-fast behavior of iterators * should be used only to detect bugs.</i> * * <p>This class is a member of the * <a href="{@docRoot}/../technotes/guides/collections/index.html"> * Java Collections Framework</a>. * * @author Josh Bloch * @version 1.67, 04/21/06 * @see List * @see ArrayList * @see Vector * @since 1.2 * @param <E> the type of elements held in this collection */ public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { private transient Entry<E> header = new Entry<E>(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<? extends E> 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 specified element at the beginning of this list. * * @param e the element to add */ public void addFirst(E e) { addBefore(e, header.next); } /** * Appends the specified element to the end of this list. * * <p>This method is equivalent to {@link #add}. * * @param e the element to add */ public void addLast(E e) { addBefore(e, header); } /** * Returns <tt>true</tt> if this list contains the specified element. * More formally, returns <tt>true</tt> if and only if this list contains * at least one element <tt>e</tt> such that * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>. * * @param o element whose presence in this list is to be tested * @return <tt>true</tt> 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. * * <p>This method is equivalent to {@link #addLast}. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */ public boolean add(E e) { addBefore(e, header); return true; } /** * Removes the first occurrence of the specified element from this list, * if it is present. If this list does not contain the element, it is * unchanged. More formally, removes the element with the lowest index * <tt>i</tt> such that * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt> * (if such an element exists). Returns <tt>true</tt> if this list * contained the specified element (or equivalently, if this list * changed as a result of the call). * * @param o element to be removed from this list, if present * @return <tt>true</tt> if this list contained the specified element */ public boolean remove(Object o) { if (o==null) { for (Entry<E> e = header.next; e != header; e = e.next) { if (e.element==null) { remove(e); return true; } } } else { for (Entry<E> e = header.next; e != header; e = e.next) { if (o.equals(e.element)) { remove(e); return true; } } } return false; } /** * Appends all of the element