java.util

Class LinkedList<T>

public class LinkedList<T> extends AbstractSequentialList<T> implements List<T>, Queue<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 {@link ConcurrentModificationException} rather than exhibit non-deterministic behavior.

Since: 1.2

See Also: List ArrayList Vector synchronizedList

UNKNOWN: missing javadoc, but complete to 1.4

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
booleanadd(T o)
Adds an element to the end of the list.
voidadd(int index, T o)
Inserts an element in the given position in the list.
booleanaddAll(Collection<? extends T> c)
Append the elements of the collection in iteration order to the end of this list.
booleanaddAll(int index, Collection<? extends T> c)
Insert the elements of the collection in iteration order at the given index of this list.
voidaddFirst(T o)
Insert an element at the first of the list.
voidaddLast(T o)
Insert an element at the last of the list.
voidclear()
Remove all elements from this list.
Objectclone()
Create a shallow copy of this LinkedList (the elements are not cloned).
booleancontains(Object o)
Returns true if the list contains the given object.
Telement()
Tget(int index)
Return the element at index.
TgetFirst()
Returns the first element in the list.
TgetLast()
Returns the last element in the list.
intindexOf(Object o)
Returns the first index where the element is located in the list, or -1.
intlastIndexOf(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.
booleanoffer(T value)
Tpeek()
Tpoll()
booleanremove(Object o)
Removes the entry at the lowest index in the list that matches the given object, comparing by o == null ?
Tremove(int index)
Removes the element at the given position from the list.
Tremove()
TremoveFirst()
Remove and return the first element in the list.
TremoveLast()
Remove and return the last element in the list.
Tset(int index, T o)
Replace the element at the given location in the list.
intsize()
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.

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

add

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

Parameters: o the entry to add

Returns: true, as it always succeeds

add

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

Parameters: index where to insert the element o the element to insert

Throws: IndexOutOfBoundsException if index < 0 || index > size()

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.

Parameters: c the collection to append

Returns: true if the list was modified

Throws: NullPointerException if c is null

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.

Parameters: c the collection to append

Returns: true if the list was modified

Throws: NullPointerException if c is null IndexOutOfBoundsException if index < 0 || index > size()

addFirst

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

Parameters: o the element to insert

addLast

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

Parameters: o the element to insert

clear

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

clone

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

Returns: an object of the same class as this object, containing the same elements in the same order

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).

Parameters: o the element to look for

Returns: true if it is found

element

public T element()

Since: 1.5

get

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

Parameters: index the place to look

Returns: the element at index

Throws: IndexOutOfBoundsException if index < 0 || index >= size()

getFirst

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

Returns: the first list element

Throws: NoSuchElementException if the list is empty

getLast

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

Returns: the last list element

Throws: NoSuchElementException if the list is empty

indexOf

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

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.

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.

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

Throws: IndexOutOfBoundsException if index < 0 || index > size()

offer

public boolean offer(T value)

Since: 1.5

peek

public T peek()

Since: 1.5

poll

public T poll()

Since: 1.5

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).

Parameters: o the object to remove

Returns: true if an instance of the object was removed

remove

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

Parameters: index the location of the element to remove

Returns: the removed element

Throws: IndexOutOfBoundsException if index < 0 || index > size()

remove

public T remove()

Since: 1.5

removeFirst

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

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.

Returns: the former last element in the list

Throws: NoSuchElementException if the list is empty

set

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

Parameters: index which index to change o the new element

Returns: the prior element

Throws: IndexOutOfBoundsException if index < 0 || index >= size()

size

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

Returns: the list size

toArray

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

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.

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