java.util

Class LinkedList

Implemented Interfaces:
Cloneable, Collection, List, Serializable

public class LinkedList
extends AbstractSequentialList
implements List, 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 c)
Create a linked list containing the elements, in order, of a given collection.

Method Summary

void
add(int index, Object o)
Inserts an element in the given position in the list.
boolean
add(Object o)
Adds an element to the end of the list.
boolean
addAll(int index, Collection c)
Insert the elements of the collection in iteration order at the given index of this list.
boolean
addAll(Collection c)
Append the elements of the collection in iteration order to the end of this list.
void
addFirst(Object o)
Insert an element at the first of the list.
void
addLast(Object 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.
Object
get(int index)
Return the element at index.
Object
getFirst()
Returns the first element in the list.
Object
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.
Object
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 ?
Object
removeFirst()
Remove and return the first element in the list.
Object
removeLast()
Remove and return the last element in the list.
Object
set(int index, Object 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.
Object[]
toArray(Object[] a)
Returns an Array whose component type is the runtime component type of the passed-in Array.

Methods inherited from class java.util.AbstractSequentialList

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

Methods inherited from class java.util.AbstractList

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

Methods inherited from class java.util.AbstractCollection

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

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

LinkedList

public LinkedList()
Create an empty linked list.


LinkedList

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

add

public void add(int index,
                Object o)
Inserts an element in the given position in the list.
Specified by:
add in interface List
Overrides:
add in interface AbstractSequentialList

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

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


add

public boolean add(Object o)
Adds an element to the end of the list.
Specified by:
add in interface List
add in interface Collection
Overrides:
add in interface AbstractList

Parameters:
o - the entry to add

Returns:
true, as it always succeeds


addAll

public boolean addAll(int index,
                      Collection 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
Overrides:
addAll in interface AbstractSequentialList

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


addAll

public boolean addAll(Collection 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 List
addAll in interface Collection
Overrides:
addAll in interface AbstractCollection

Parameters:
c - the collection to append

Returns:
true if the list was modified

Throws:
NullPointerException - if c is null


addFirst

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

Parameters:
o - the element to insert


addLast

public void addLast(Object 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
clear in interface Collection
Overrides:
clear in interface AbstractList


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
contains in interface Collection
Overrides:
contains in interface AbstractCollection

Parameters:
o - the element to look for

Returns:
true if it is found


get

public Object get(int index)
Return the element at index.
Specified by:
get in interface List
Overrides:
get in interface AbstractSequentialList

Parameters:
index - the place to look

Returns:
the element at index

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


getFirst

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

Returns:
the first list element

Throws:
NoSuchElementException - if the list is empty


getLast

public Object 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
Overrides:
indexOf in interface AbstractList

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
Overrides:
lastIndexOf in interface AbstractList

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
Overrides:
listIterator in interface AbstractSequentialList

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


remove

public Object remove(int index)
Removes the element at the given position from the list.
Specified by:
remove in interface List
Overrides:
remove in interface AbstractSequentialList

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
remove in interface Collection
Overrides:
remove in interface AbstractCollection

Parameters:
o - the object to remove

Returns:
true if an instance of the object was removed


removeFirst

public Object 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 Object 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 Object set(int index,
                  Object o)
Replace the element at the given location in the list.
Specified by:
set in interface List
Overrides:
set in interface AbstractSequentialList

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
size in interface Collection
Overrides:
size in interface AbstractCollection

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
toArray in interface Collection
Overrides:
toArray in interface AbstractCollection

Returns:
an array containing the list elements


toArray

public Object[] toArray(Object[] 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 List
toArray in interface Collection
Overrides:
toArray in interface AbstractCollection

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


LinkedList.java -- Linked list implementation of the List interface Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005 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.