java.util
Class LinkedList<E>

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractList<E>
          java.util.AbstractSequentialList<E>
              java.util.LinkedList<E>

All Implemented Interfaces:

Serializable, Cloneable, Iterable<E>, Collection<E>, List<E>, Queue<E>

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Queue<E>, Cloneable, Serializable

LinkedList is an implementation of List, backed by a linked list. All optional operations are supported, adding, removing and replacing. The elements can be any objects.

Since:

1.2

See Also:

Serialized Form

Field Summary

(package private) int	size
(package private) java.util.LinkedList.Link<E>	voidLink

Fields inherited from class java.util.AbstractList

modCount

Constructor Summary

LinkedList()
Constructs a new empty instance of LinkedList.

LinkedList(Collection<? extends E> collection)
Constructs a new instance of LinkedList that holds all of the elements contained in the supplied collection argument.

Method Summary

boolean	add(E object) Adds the specified object at the end of this LinkedList.
void	add(int location, E object) Inserts the specified object into this LinkedList at the specified location.
boolean	addAll(Collection<? extends E> collection) Adds the objects in the specified Collection to this LinkedList.
boolean	addAll(int location, Collection<? extends E> collection) Inserts the objects in the specified Collection at the specified location in this LinkedList.
void	addFirst(E object) Adds the specified object at the beginning of this LinkedList.
void	addLast(E object) Adds the specified object at the end of this LinkedList.
void	clear() Removes all elements from this LinkedList, leaving it empty.
Object	clone() Returns a new LinkedList with the same elements and size as this LinkedList.
boolean	contains(Object object) Searches this LinkedList for the specified object.
E	element() Gets but not removes the element in the head of the queue.
E	get(int location) Returns the element at the specified location in this List.
E	getFirst() Returns the first element in this LinkedList.
E	getLast() Returns the last element in this LinkedList.
int	indexOf(Object object) Searches this LinkedList for the specified object and returns the index of the first occurrence.
int	lastIndexOf(Object object) Searches this LinkedList for the specified object and returns the index of the last occurrence.
ListIterator<E>	listIterator(int location) Returns a ListIterator on the elements of this LinkedList.
boolean	offer(E o) Inserts the specified element into the queue provided that the condition allows such an operation.
E	peek() Gets but not removes the element in the head of the queue, or throws exception if there is no element in the queue.
E	poll() Gets and removes the element in the head of the queue, or returns null if there is no element in the queue.
E	remove() Gets and removes the element in the head of the queue.
E	remove(int location) Removes the object at the specified location from this LinkedList.
boolean	remove(Object object) Removes the first occurrence of the specified object from this Collection.
E	removeFirst() Removes the first object from this LinkedList.
E	removeLast() Removes the last object from this LinkedList.
E	set(int location, E object) Replaces the element at the specified location in this LinkedList with the specified object.
int	size() Returns the number of elements in this LinkedList.
Object[]	toArray() Returns a new array containing all elements contained in this LinkedList.
<T> T[]	toArray(T[] contents) Returns an array containing all elements contained in this LinkedList.

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

Field Detail

size

transient int size

voidLink

transient java.util.LinkedList.Link<E> voidLink

Constructor Detail

LinkedList

public LinkedList()

Constructs a new empty instance of LinkedList.

LinkedList

public LinkedList(Collection<? extends E> collection)

Constructs a new instance of LinkedList that holds all of the elements contained in the supplied collection argument. The order of the elements in this new LinkedList will be determined by the iteration order of collection.

Parameters:

collection - the collection of elements to add

Method Detail

add

public void add(int location,
                E object)

Inserts the specified object into this LinkedList at the specified location. The object is inserted before any previous element at the specified location. If the location is equal to the size of this LinkedList, the object is added at the end.

Specified by:

add in interface List<E>

Overrides:

add in class AbstractSequentialList<E>

Parameters:

location - the index at which to insert

object - the object to add

Throws:

IndexOutOfBoundsException - when location < 0 || >= size()

add

public boolean add(E object)

Adds the specified object at the end of this LinkedList.

Specified by:

add in interface Collection<E>

Specified by:

add in interface List<E>

Overrides:

add in class AbstractList<E>

Parameters:

object - the object to add

Returns:

true

addAll

public boolean addAll(int location,
                      Collection<? extends E> collection)

Inserts the objects in the specified Collection at the specified location in this LinkedList. The objects are added in the order they are returned from the Collection iterator.

Specified by:

addAll in interface List<E>

Overrides:

addAll in class AbstractSequentialList<E>

Parameters:

location - the index at which to insert

collection - the Collection of objects

Returns:

true if this LinkedList is modified, false otherwise

Throws:

IndexOutOfBoundsException - when location < 0 || > size()

addAll

public boolean addAll(Collection<? extends E> collection)

Adds the objects in the specified Collection to this LinkedList.

Specified by:

addAll in interface Collection<E>

Specified by:

addAll in interface List<E>

Overrides:

addAll in class AbstractCollection<E>

Parameters:

collection - the Collection of objects

Returns:

true if this LinkedList is modified, false otherwise

addFirst

public void addFirst(E object)

Adds the specified object at the beginning of this LinkedList.

Parameters:

object - the object to add

addLast

public void addLast(E object)

Adds the specified object at the end of this LinkedList.

Parameters:

object - the object to add

clear

public void clear()

Removes all elements from this LinkedList, leaving it empty.

Specified by:

clear in interface Collection<E>

Specified by:

clear in interface List<E>

Overrides:

clear in class AbstractList<E>

See Also:

List.isEmpty(), size

clone

public Object clone()

Returns a new LinkedList with the same elements and size as this LinkedList.

Overrides:

clone in class Object

Returns:

a shallow copy of this LinkedList

See Also:

Cloneable

contains

public boolean contains(Object object)

Searches this LinkedList for the specified object.

Specified by:

contains in interface Collection<E>

Specified by:

contains in interface List<E>

Overrides:

contains in class AbstractCollection<E>

Parameters:

object - the object to search for

Returns:

true if object is an element of this LinkedList, false otherwise

get

public E get(int location)

Description copied from class: AbstractSequentialList

Returns the element at the specified location in this List.

Specified by:

get in interface List<E>

Overrides:

get in class AbstractSequentialList<E>

Parameters:

location - the index of the element to return

Returns:

the element at the specified location

getFirst

public E getFirst()

Returns the first element in this LinkedList.

Returns:

the first element

Throws:

NoSuchElementException - when this LinkedList is empty

getLast

public E getLast()

Returns the last element in this LinkedList.

Returns:

the last element

Throws:

NoSuchElementException - when this LinkedList is empty

indexOf

public int indexOf(Object object)

Searches this LinkedList for the specified object and returns the index of the first occurrence.

Specified by:

indexOf in interface List<E>

Overrides:

indexOf in class AbstractList<E>

Parameters:

object - the object to search for

Returns:

the index of the first occurrence of the object

lastIndexOf

public int lastIndexOf(Object object)

Searches this LinkedList for the specified object and returns the index of the last occurrence.

Specified by:

lastIndexOf in interface List<E>

Overrides:

lastIndexOf in class AbstractList<E>

Parameters:

object - the object to search for

Returns:

the index of the last occurrence of the object

listIterator

public ListIterator<E> listIterator(int location)

Returns a ListIterator on the elements of this LinkedList. The elements are iterated in the same order that they occur in the LinkedList. The iteration starts at the specified location.

Specified by:

listIterator in interface List<E>

Specified by:

listIterator in class AbstractSequentialList<E>

Parameters:

location - the index at which to start the iteration

Returns:

a ListIterator on the elements of this LinkedList

Throws:

IndexOutOfBoundsException - when location < 0 || >= size()

See Also:

ListIterator

remove

public E remove(int location)

Removes the object at the specified location from this LinkedList.

Specified by:

remove in interface List<E>

Overrides:

remove in class AbstractSequentialList<E>

Parameters:

location - the index of the object to remove

Returns:

the removed object

Throws:

IndexOutOfBoundsException - when location < 0 || >= size()

remove

public boolean remove(Object object)

Description copied from class: AbstractCollection

Removes the first occurrence of the specified object from this Collection. This operation traverses over the collection, looking for the specified object. Once the object is found, the object will be removed from the collection using the iterator's remove method. This collection will throw an UnsupportedOperationException if the iterator returned does not implement remove method, and the specified object is in this collection.

Specified by:

remove in interface Collection<E>

Specified by:

remove in interface List<E>

Overrides:

remove in class AbstractCollection<E>

Parameters:

object - the object to remove

Returns:

true if this Collection is modified, false otherwise

removeFirst

public E removeFirst()

Removes the first object from this LinkedList.

Returns:

the removed object

Throws:

NoSuchElementException - when this LinkedList is empty

removeLast

public E removeLast()

Removes the last object from this LinkedList.

Returns:

the removed object

Throws:

NoSuchElementException - when this LinkedList is empty

set

public E set(int location,
             E object)

Replaces the element at the specified location in this LinkedList with the specified object.

Specified by:

set in interface List<E>

Overrides:

set in class AbstractSequentialList<E>

Parameters:

location - the index at which to put the specified object

object - the object to add

Returns:

the previous element at the index

Throws:

IndexOutOfBoundsException - when location < 0 || >= size()

size

public int size()

Returns the number of elements in this LinkedList.

Specified by:

size in interface Collection<E>

Specified by:

size in interface List<E>

Specified by:

size in class AbstractCollection<E>

Returns:

the number of elements in this LinkedList

offer

public boolean offer(E o)

Description copied from interface: Queue

Inserts the specified element into the queue provided that the condition allows such an operation. The method is generally preferable to the collection.add(E), since the latter might throw an exception if the operation fails.

Specified by:

offer in interface Queue<E>

Parameters:

o - the specified element to insert into the queue.

Returns:

true if the operation succeeds and false if it fails.

poll

public E poll()

Description copied from interface: Queue

Gets and removes the element in the head of the queue, or returns null if there is no element in the queue.

Specified by:

poll in interface Queue<E>

Returns:

the element in the head of the queue or null if there is no element in the queue.

remove

public E remove()

Description copied from interface: Queue

Gets and removes the element in the head of the queue. Throws a NoSuchElementException if there is no element in the queue.

Specified by:

remove in interface Queue<E>

Returns:

the element in the head of the queue.

peek

public E peek()

Description copied from interface: Queue

Gets but not removes the element in the head of the queue, or throws exception if there is no element in the queue.

Specified by:

peek in interface Queue<E>

Returns:

the element in the head of the queue or null if there is no element in the queue.

element

public E element()

Description copied from interface: Queue

Gets but not removes the element in the head of the queue. Throws a NoSuchElementException if there is no element in the queue.

Specified by:

element in interface Queue<E>

Returns:

the element in the head of the queue.

toArray

public Object[] toArray()

Returns a new array containing all elements contained in this LinkedList.

Specified by:

toArray in interface Collection<E>

Specified by:

toArray in interface List<E>

Overrides:

toArray in class AbstractCollection<E>

Returns:

an array of the elements from this LinkedList

toArray

public <T> T[] toArray(T[] contents)

Returns an array containing all elements contained in this LinkedList. If the specified array is large enough to hold the elements, the specified array is used, otherwise an array of the same type is created. If the specified array is used and is larger than this LinkedList, the array element following the collection elements is set to null.

Specified by:

toArray in interface Collection<E>

Specified by:

toArray in interface List<E>

Overrides:

toArray in class AbstractCollection<E>

Parameters:

contents - the array

Returns:

an array of the elements from this LinkedList

Throws:

ArrayStoreException - when the type of an element in this LinkedList cannot be stored in the type of the specified array