java.util
Class LinkedList<T>

java.lang.Object
  extended by java.util.AbstractCollection<E>
      extended by java.util.AbstractList<E>
          extended by java.util.AbstractSequentialList<T>
              extended by java.util.LinkedList<T>
All Implemented Interfaces:
Serializable, Cloneable, Iterable<T>, Collection<T>, java.util.Deque<T>, List<T>, java.util.Queue<T>

public class LinkedList<T>
extends AbstractSequentialList<T>
implements List<T>, java.util.Deque<T>, Cloneable, Serializable

Linked list implementation of the List interface. In addition to the methods of the List interface, this class provides access to the first and last list elements in O(1) time for easy stack, queue, or double-ended queue (deque) creation. The list is doubly-linked, with traversal to a given index starting from the end closest to the element.

LinkedList is not synchronized, so if you need multi-threaded access, consider using:
List l = Collections.synchronizedList(new LinkedList(...));

The iterators are fail-fast, meaning that any structural modification, except for remove() called on the iterator itself, cause the iterator to throw a ConcurrentModificationException rather than exhibit non-deterministic behavior.

Since:
1.2
See Also:
List, ArrayList, Vector, Collections.synchronizedList(List), Serialized Form

Field Summary
 
Fields inherited from class java.util.AbstractList
modCount
 
Constructor Summary
LinkedList()
          Create an empty linked list.
LinkedList(Collection<? extends T> c)
          Create a linked list containing the elements, in order, of a given collection.
 
Method Summary
 void add(int index, T o)
          Inserts an element in the given position in the list.
 boolean add(T o)
          Adds an element to the end of the list.
 boolean addAll(Collection<? extends T> c)
          Append the elements of the collection in iteration order to the end of this list.
 boolean addAll(int index, Collection<? extends T> c)
          Insert the elements of the collection in iteration order at the given index of this list.
 void addFirst(T o)
          Insert an element at the first of the list.
 void addLast(T o)
          Insert an element at the last of the list.
 void clear()
          Remove all elements from this list.
 Object clone()
          Create a shallow copy of this LinkedList (the elements are not cloned).
 boolean contains(Object o)
          Returns true if the list contains the given object.
 Iterator<T> descendingIterator()
          Obtain an Iterator over this list in reverse sequential order.
 T element()
          Returns the first element of the list without removing it.
 T get(int index)
          Return the element at index.
 T getFirst()
          Returns the first element in the list.
 T getLast()
          Returns the last element in the list.
 int indexOf(Object o)
          Returns the first index where the element is located in the list, or -1.
 int lastIndexOf(Object o)
          Returns the last index where the element is located in the list, or -1.
 ListIterator<T> listIterator(int index)
          Obtain a ListIterator over this list, starting at a given index.
 boolean offer(T value)
          Adds the specified element to the end of the list.
 boolean offerFirst(T value)
          Inserts the specified element at the front of the list.
 boolean offerLast(T value)
          Inserts the specified element at the end of the list.
 T peek()
          Returns the first element of the list without removing it.
 T peekFirst()
          Returns the first element of the list without removing it.
 T peekLast()
          Returns the last element of the list without removing it.
 T poll()
          Removes and returns the first element of the list.
 T pollFirst()
          Removes and returns the first element of the list.
 T pollLast()
          Removes and returns the last element of the list.
 T pop()
          Pops an element from the stack by removing and returning the first element in the list.
 void push(T value)
          Pushes an element on to the stack by adding it to the front of the list.
 T remove()
          Removes and returns the first element of the list.
 T remove(int index)
          Removes the element at the given position from the list.
 boolean remove(Object o)
          Removes the entry at the lowest index in the list that matches the given object, comparing by o == null ?
 T removeFirst()
          Remove and return the first element in the list.
 boolean removeFirstOccurrence(Object o)
          Removes the first occurrence of the specified element from the list, when traversing the list from head to tail.
 T removeLast()
          Remove and return the last element in the list.
 boolean removeLastOccurrence(Object o)
          Removes the last occurrence of the specified element from the list, when traversing the list from head to tail.
 T set(int index, T o)
          Replace the element at the given location in the list.
 int size()
          Returns the size of the list.
 Object[] toArray()
          Returns an array which contains the elements of the list in order.
<S> S[]
toArray(S[] a)
          Returns an Array whose component type is the runtime component type of the passed-in Array.
 
Methods inherited from class java.util.AbstractSequentialList
iterator
 
Methods inherited from class java.util.AbstractList
equals, hashCode, listIterator, removeRange, subList
 
Methods inherited from class java.util.AbstractCollection
containsAll, isEmpty, removeAll, retainAll, toString
 
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface java.util.List
containsAll, equals, hashCode, isEmpty, iterator, listIterator, removeAll, retainAll, subList
 
Methods inherited from interface java.util.Deque
iterator
 

Constructor Detail

LinkedList

public LinkedList()
Create an empty linked list.


LinkedList

public LinkedList(Collection<? extends T> c)
Create a linked list containing the elements, in order, of a given collection.

Parameters:
c - the collection to populate this list from
Throws:
NullPointerException - if c is null
Method Detail

getFirst

public T getFirst()
Returns the first element in the list.

Specified by:
getFirst in interface java.util.Deque<T>
Returns:
the first list element
Throws:
NoSuchElementException - if the list is empty

getLast

public T getLast()
Returns the last element in the list.

Specified by:
getLast in interface java.util.Deque<T>
Returns:
the last list element
Throws:
NoSuchElementException - if the list is empty

removeFirst

public T removeFirst()
Remove and return the first element in the list.

Specified by:
removeFirst in interface java.util.Deque<T>
Returns:
the former first element in the list
Throws:
NoSuchElementException - if the list is empty

removeLast

public T removeLast()
Remove and return the last element in the list.

Specified by:
removeLast in interface java.util.Deque<T>
Returns:
the former last element in the list
Throws:
NoSuchElementException - if the list is empty

addFirst

public void addFirst(T o)
Insert an element at the first of the list.

Specified by:
addFirst in interface java.util.Deque<T>
Parameters:
o - the element to insert

addLast

public void addLast(T o)
Insert an element at the last of the list.

Specified by:
addLast in interface java.util.Deque<T>
Parameters:
o - the element to insert

contains

public boolean contains(Object o)
Returns true if the list contains the given object. Comparison is done by o == null ? e = null : o.equals(e).

Specified by:
contains in interface Collection<T>
Specified by:
contains in interface java.util.Deque<T>
Specified by:
contains in interface List<T>
Overrides:
contains in class AbstractCollection<T>
Parameters:
o - the element to look for
Returns:
true if it is found

size

public int size()
Returns the size of the list.

Specified by:
size in interface Collection<T>
Specified by:
size in interface java.util.Deque<T>
Specified by:
size in interface List<T>
Specified by:
size in class AbstractCollection<T>
Returns:
the list size

add

public boolean add(T o)
Adds an element to the end of the list.

Specified by:
add in interface Collection<T>
Specified by:
add in interface java.util.Deque<T>
Specified by:
add in interface List<T>
Specified by:
add in interface java.util.Queue<T>
Overrides:
add in class AbstractList<T>
Parameters:
o - the entry to add
Returns:
true, as it always succeeds
See Also:
AbstractList.add(int, Object)

remove

public boolean remove(Object o)
Removes the entry at the lowest index in the list that matches the given object, comparing by o == null ? e = null : o.equals(e).

Specified by:
remove in interface Collection<T>
Specified by:
remove in interface java.util.Deque<T>
Specified by:
remove in interface List<T>
Overrides:
remove in class AbstractCollection<T>
Parameters:
o - the object to remove
Returns:
true if an instance of the object was removed
See Also:
Iterator.remove()

addAll

public boolean addAll(Collection<? extends T> c)
Append the elements of the collection in iteration order to the end of this list. If this list is modified externally (for example, if this list is the collection), behavior is unspecified.

Specified by:
addAll in interface Collection<T>
Specified by:
addAll in interface List<T>
Overrides:
addAll in class AbstractCollection<T>
Parameters:
c - the collection to append
Returns:
true if the list was modified
Throws:
NullPointerException - if c is null
See Also:
AbstractCollection.add(Object)

addAll

public boolean addAll(int index,
                      Collection<? extends T> c)
Insert the elements of the collection in iteration order at the given index of this list. If this list is modified externally (for example, if this list is the collection), behavior is unspecified.

Specified by:
addAll in interface List<T>
Overrides:
addAll in class AbstractSequentialList<T>
Parameters:
c - the collection to append
index - the location to insert the collection
Returns:
true if the list was modified
Throws:
NullPointerException - if c is null
IndexOutOfBoundsException - if index < 0 || index > size()
See Also:
AbstractSequentialList.add(int, Object)

clear

public void clear()
Remove all elements from this list.

Specified by:
clear in interface Collection<T>
Specified by:
clear in interface List<T>
Overrides:
clear in class AbstractList<T>
See Also:
AbstractList.remove(int), AbstractList.removeRange(int, int)

get

public T get(int index)
Return the element at index.

Specified by:
get in interface List<T>
Overrides:
get in class AbstractSequentialList<T>
Parameters:
index - the place to look
Returns:
the element at index
Throws:
IndexOutOfBoundsException - if index < 0 || index >= size()

set

public T set(int index,
             T o)
Replace the element at the given location in the list.

Specified by:
set in interface List<T>
Overrides:
set in class AbstractSequentialList<T>
Parameters:
index - which index to change
o - the new element
Returns:
the prior element
Throws:
IndexOutOfBoundsException - if index < 0 || index >= size()

add

public void add(int index,
                T o)
Inserts an element in the given position in the list.

Specified by:
add in interface List<T>
Overrides:
add in class AbstractSequentialList<T>
Parameters:
index - where to insert the element
o - the element to insert
Throws:
IndexOutOfBoundsException - if index < 0 || index > size()
See Also:
AbstractList.modCount

remove

public T remove(int index)
Removes the element at the given position from the list.

Specified by:
remove in interface List<T>
Overrides:
remove in class AbstractSequentialList<T>
Parameters:
index - the location of the element to remove
Returns:
the removed element
Throws:
IndexOutOfBoundsException - if index < 0 || index > size()
See Also:
AbstractList.modCount

indexOf

public int indexOf(Object o)
Returns the first index where the element is located in the list, or -1.

Specified by:
indexOf in interface List<T>
Overrides:
indexOf in class AbstractList<T>
Parameters:
o - the element to look for
Returns:
its position, or -1 if not found

lastIndexOf

public int lastIndexOf(Object o)
Returns the last index where the element is located in the list, or -1.

Specified by:
lastIndexOf in interface List<T>
Overrides:
lastIndexOf in class AbstractList<T>
Parameters:
o - the element to look for
Returns:
its position, or -1 if not found

listIterator

public ListIterator<T> listIterator(int index)
Obtain a ListIterator over this list, starting at a given index. The ListIterator returned by this method supports the add, remove and set methods.

Specified by:
listIterator in interface List<T>
Specified by:
listIterator in class AbstractSequentialList<T>
Parameters:
index - the index of the element to be returned by the first call to next(), or size() to be initially positioned at the end of the list
Returns:
the list iterator
Throws:
IndexOutOfBoundsException - if index < 0 || index > size()
See Also:
AbstractList.modCount

clone

public Object clone()
Create a shallow copy of this LinkedList (the elements are not cloned).

Overrides:
clone in class Object
Returns:
an object of the same class as this object, containing the same elements in the same order
See Also:
Cloneable

toArray

public Object[] toArray()
Returns an array which contains the elements of the list in order.

Specified by:
toArray in interface Collection<T>
Specified by:
toArray in interface List<T>
Overrides:
toArray in class AbstractCollection<T>
Returns:
an array containing the list elements

toArray

public <S> S[] toArray(S[] a)
Returns an Array whose component type is the runtime component type of the passed-in Array. The returned Array is populated with all of the elements in this LinkedList. If the passed-in Array is not large enough to store all of the elements in this List, a new Array will be created and returned; if the passed-in Array is larger than the size of this List, then size() index will be set to null.

Specified by:
toArray in interface Collection<T>
Specified by:
toArray in interface List<T>
Overrides:
toArray in class AbstractCollection<T>
Parameters:
a - the passed-in Array
Returns:
an array representation of this list
Throws:
ArrayStoreException - if the runtime type of a does not allow an element in this list
NullPointerException - if a is null

offer

public boolean offer(T value)
Adds the specified element to the end of the list.

Specified by:
offer in interface java.util.Deque<T>
Specified by:
offer in interface java.util.Queue<T>
Parameters:
value - the value to add.
Returns:
true.
Since:
1.5

element

public T element()
Returns the first element of the list without removing it.

Specified by:
element in interface java.util.Deque<T>
Specified by:
element in interface java.util.Queue<T>
Returns:
the first element of the list.
Throws:
NoSuchElementException - if the list is empty.
Since:
1.5

peek

public T peek()
Returns the first element of the list without removing it.

Specified by:
peek in interface java.util.Deque<T>
Specified by:
peek in interface java.util.Queue<T>
Returns:
the first element of the list, or null if the list is empty.
Since:
1.5

poll

public T poll()
Removes and returns the first element of the list.

Specified by:
poll in interface java.util.Deque<T>
Specified by:
poll in interface java.util.Queue<T>
Returns:
the first element of the list, or null if the list is empty.
Since:
1.5

remove

public T remove()
Removes and returns the first element of the list.

Specified by:
remove in interface java.util.Deque<T>
Specified by:
remove in interface java.util.Queue<T>
Returns:
the first element of the list.
Throws:
NoSuchElementException - if the list is empty.
Since:
1.5

descendingIterator

public Iterator<T> descendingIterator()
Obtain an Iterator over this list in reverse sequential order.

Specified by:
descendingIterator in interface java.util.Deque<T>
Returns:
an Iterator over the elements of the list in reverse order.
Since:
1.6

offerFirst

public boolean offerFirst(T value)
Inserts the specified element at the front of the list.

Specified by:
offerFirst in interface java.util.Deque<T>
Parameters:
value - the element to insert.
Returns:
true.
Since:
1.6

offerLast

public boolean offerLast(T value)
Inserts the specified element at the end of the list.

Specified by:
offerLast in interface java.util.Deque<T>
Parameters:
value - the element to insert.
Returns:
true.
Since:
1.6

peekFirst

public T peekFirst()
Returns the first element of the list without removing it.

Specified by:
peekFirst in interface java.util.Deque<T>
Returns:
the first element of the list, or null if the list is empty.
Since:
1.6

peekLast

public T peekLast()
Returns the last element of the list without removing it.

Specified by:
peekLast in interface java.util.Deque<T>
Returns:
the last element of the list, or null if the list is empty.
Since:
1.6

pollFirst

public T pollFirst()
Removes and returns the first element of the list.

Specified by:
pollFirst in interface java.util.Deque<T>
Returns:
the first element of the list, or null if the list is empty.
Since:
1.6

pollLast

public T pollLast()
Removes and returns the last element of the list.

Specified by:
pollLast in interface java.util.Deque<T>
Returns:
the last element of the list, or null if the list is empty.
Since:
1.6

pop

public T pop()
Pops an element from the stack by removing and returning the first element in the list. This is equivalent to calling removeFirst().

Specified by:
pop in interface java.util.Deque<T>
Returns:
the top of the stack, which is the first element of the list.
Throws:
NoSuchElementException - if the list is empty.
Since:
1.6
See Also:
removeFirst()

push

public void push(T value)
Pushes an element on to the stack by adding it to the front of the list. This is equivalent to calling #addFirst(T).

Specified by:
push in interface java.util.Deque<T>
Parameters:
value - the element to push on to the stack.
Throws:
NoSuchElementException - if the list is empty.
Since:
1.6
See Also:
#addFirst(T)

removeFirstOccurrence

public boolean removeFirstOccurrence(Object o)
Removes the first occurrence of the specified element from the list, when traversing the list from head to tail. The list is unchanged if the element is not found. This is equivalent to calling remove(Object).

Specified by:
removeFirstOccurrence in interface java.util.Deque<T>
Parameters:
o - the element to remove.
Returns:
true if an instance of the object was removed.
Since:
1.6

removeLastOccurrence

public boolean removeLastOccurrence(Object o)
Removes the last occurrence of the specified element from the list, when traversing the list from head to tail. The list is unchanged if the element is not found.

Specified by:
removeLastOccurrence in interface java.util.Deque<T>
Parameters:
o - the element to remove.
Returns:
true if an instance of the object was removed.
Since:
1.6