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.