Overview Package Class Use Source Tree Index Deprecated About
Prev Class | Next ClassFrames | No Frames
Summary: Nested | Field | Method | ConstrDetail: Nested | Field | Method | Constr

java.util

Class LinkedList<T>

Implemented Interfaces:
Cloneable, Collection<E>, Deque, Iterable<E>, List<E>, Serializable
public class LinkedList<T>
extends AbstractSequentialList<E>
implements List<E>, Deque, 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<E>

modCount

Constructor Summary

LinkedList()
Create an empty linked list.
LinkedList(T> c)
Create a linked list containing the elements, in order, of a given collection.

Method Summary

S[] toArray(S[] a)
Returns an Array whose component type is the runtime component type of the passed-in Array.
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(T> c)
Append the elements of the collection in iteration order to the end of this list.
boolean
addAll(int index, 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
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
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.

Methods inherited from class java.util.AbstractSequentialList<E>

add, addAll, get, iterator, listIterator, remove, set

Methods inherited from class java.util.AbstractList<E>

add, add, addAll, clear, equals, get, hashCode, indexOf, iterator, lastIndexOf, listIterator, listIterator, remove, removeRange, set, subList

Methods inherited from class java.util.AbstractCollection<E>

T[] toArray, add, addAll, clear, contains, containsAll, isEmpty, iterator, remove, removeAll, retainAll, size, toArray, toString

Methods inherited from class java.lang.Object

clone, equals, extends Object> getClass, finalize, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

LinkedList

public LinkedList()
Create an empty linked list.

LinkedList

public LinkedList(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 Details

S[] toArray

public  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

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(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,
                      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.
Specified by:
clear in interface List<E>
clear in interface Collection<E>
Overrides:
clear in interface AbstractList<E>

clone

public Object clone()
Create a shallow copy of this LinkedList (the elements are not cloned).
Overrides:
clone in interface Object
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).
Specified by:
contains in interface List<E>
contains in interface Collection<E>
Overrides:
contains in interface AbstractCollection<E>
Parameters:
o - the element to look for
Returns:
true if it is found

descendingIterator

public Iterator 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.
Specified by:
get in interface List<E>
Overrides:
get in interface AbstractSequentialList<E>
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.
Specified by:
indexOf in interface List<E>
Overrides:
indexOf in interface AbstractList<E>
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<E>
Overrides:
lastIndexOf in interface AbstractList<E>
Parameters:
o - the element to look for
Returns:
its position, or -1 if not found

listIterator

public ListIterator 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<E>
Overrides:
listIterator in interface AbstractSequentialList<E>
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 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
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).
Parameters:
value - the element to push on to the stack.
Throws:
NoSuchElementException - if the list is empty.
Since:
1.6
See Also:
addFirst(T)

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

remove

public T remove(int index)
Removes the element at the given position from the list.
Specified by:
remove in interface List<E>
Overrides:
remove in interface AbstractSequentialList<E>
Parameters:
index - the location of the element to remove
Returns:
the removed element
Throws:
IndexOutOfBoundsException - if index < 0 || index > size()

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 List<E>
remove in interface Collection<E>
Overrides:
remove in interface AbstractCollection<E>
Parameters:
o - the object to remove
Returns:
true if an instance of the object was removed

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 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.
Specified by:
size in interface List<E>
size in interface Collection<E>
Overrides:
size in interface AbstractCollection<E>
Returns:
the list size

toArray

public Object[] toArray()
Returns an array which contains the elements of the list in order.
Specified by:
toArray in interface List<E>
toArray in interface Collection<E>
Overrides:
toArray in interface AbstractCollection<E>
Returns:
an array containing the list elements
LinkedList.java -- Linked list implementation of the List interface Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005, 2006 Free Software Foundation, Inc. This file is part of GNU Classpath. GNU Classpath is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2, or (at your option) any later version. GNU Classpath is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with GNU Classpath; see the file COPYING. If not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. Linking this library statically or dynamically with other modules is making a combined work based on this library. Thus, the terms and conditions of the GNU General Public License cover the whole combination. As a special exception, the copyright holders of this library give you permission to link this library with independent modules to produce an executable, regardless of the license terms of these independent modules, and to copy and distribute the resulting executable under terms of your choice, provided that you also meet, for each linked independent module, the terms and conditions of the license of that module. An independent module is a module which is not derived from or based on this library. If you modify this library, you may extend this exception to your version of the library, but you are not obligated to do so. If you do not wish to do so, delete this exception statement from your version.

Overview Package Class Use Source Tree Index Deprecated About