java.util

Class LinkedList<T>

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

Since: 1.2

UNKNOWN: Complete to 1.6

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
boolean	add(T o) Adds an element to the end of the list.
void	add(int index, T o) Inserts an element in the given position in 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.
boolean	remove(Object o) Removes the entry at the lowest index in the list that matches the given object, comparing by `o == null ?`
T	remove(int index) Removes the element at the given position from the list.
T	remove() Removes and returns the first element of the list.
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.

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

descendingIterator

public Iterator<T> descendingIterator()

Obtain an Iterator over this list in reverse sequential order.

Returns: an Iterator over the elements of the list in reverse order.

Since: 1.6

element

public T element()

Returns the first element of the list without removing it.

Returns: the first element of the list.

Throws: NoSuchElementException if the list is empty.

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)

Adds the specified element to the end of the list.

Parameters: value the value to add.

Returns: true.

Since: 1.5

offerFirst

public boolean offerFirst(T value)

Inserts the specified element at the front of the list.

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.

Parameters: value the element to insert.

Returns: true.

Since: 1.6

peek

public T peek()

Returns the first element of the list without removing it.

Returns: the first element of the list, or null if the list is empty.

Since: 1.5

peekFirst

public T peekFirst()

Returns the first element of the list without removing it.

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.

Returns: the last element of the list, or null if the list is empty.

Since: 1.6

poll

public T poll()

Removes and returns the first element of the list.

Returns: the first element of the list, or null if the list is empty.

Since: 1.5

pollFirst

public T pollFirst()

Removes and returns the first element of the list.

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.

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 {@link #removeFirst()}.

Returns: the top of the stack, which is the first element of the list.

Throws: NoSuchElementException if the list is empty.

Since: 1.6

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 {@link #addFirst(T)}.

Parameters: value the element to push on to the stack.

Throws: NoSuchElementException if the list is empty.

Since: 1.6

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

Removes and returns the first element of the list.

Returns: the first element of the list.

Throws: NoSuchElementException if the list is empty.

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

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 {@link #remove(Object)}.

Parameters: o the element to remove.

Returns: true if an instance of the object was removed.

Since: 1.6

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

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.

Parameters: o the element to remove.

Returns: true if an instance of the object was removed.

Since: 1.6

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