Class | Tree | Index | Help
PREV CLASS | NEXT CLASS	FRAMES | NO FRAMES
SUMMARY: INNER | FIELD | CONSTR | METHOD	DETAIL: FIELD | CONSTR | METHOD

Class java.util.LinkedList

java.lang.Object
  |
  +--java.util.AbstractCollection
        |
        +--java.util.AbstractList
              |
              +--java.util.AbstractSequentialList
                    |
                    +--java.util.LinkedList

public class LinkedList

extends java.util.AbstractSequentialList

implements java.util.List, java.lang.Cloneable, java.io.Serializable

Linked list implementation of the List interface. Implements all optional List operations, and permits all elements (including null). In addition to implementing the List interface, LinkedList provides uniformly named methods to get, remove and insert an element at the beginning and end of the List. These operations allow LinkedList to be used as a stack, queue, or double-ended queue (deque).

All of the stack/queue/deque operations could be easily recast in terms of the standard List operations. They're included here primarily for convenience, though they may run slightly faster than the equivalent List operations.

All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the begining or the end, whichever is closer to the specified index.

Note that this implementation is not synchronized. If multiple threads access a LinkedList concurrently, and at least one of the threads modifies the LinkedList structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more elements; merely setting the value of an element is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the LinkedList. If no such object exists, the LinkedList should be "wrapped" using the Collections.synchronizedSet method. This is best done at creation time, to prevent accidental unsynchronized access to the LinkedList:

	List list = Collections.synchronizedList(new LinkedList(...));
 

The Iterators returned by LinkedList's iterator and listIterator methods are fail-fast: if the LinkedList is structurally modified at any time after the Iterator is created, in any way except through the Iterator's own remove or add methods, the Iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the Iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

Since:

JDK1.2

Version:

1.20 05/06/98

See Also:

java.util.List, java.util.ArrayList, Vector, Collections.synchronizedList, Serialized Form

Fields inherited from class java.util.AbstractList

modCount

Constructor Summary

LinkedList()
Constructs an empty Linked List.

LinkedList(java.util.Collection c)
Constructs a LinkedList containing the elements of the specified Collection, in the order they are returned by the Collection's iterator.

Method Summary

void	addFirst(java.lang.Object o) Inserts the given element at the beginning of this List.
void	addLast(java.lang.Object o) Appends the given element to the end of this List.
void	clear() Removes all of the elements from this List.
java.lang.Object	clone() Returns a shallow copy of this LinkedList.
java.lang.Object	getFirst() Returns the first Element in this List.
java.lang.Object	getLast() Returns the last Element in this List.
ListIterator	listIterator(int index) Returns a ListIterator of the elements in this List (in proper sequence), starting at the specified position in the list.
java.lang.Object	removeFirst() Removes and returns the first Element from this List.
java.lang.Object	removeLast() Removes and returns the last Element from this List.
int	size() Returns the number of elements in this List.

Methods inherited from class java.util.AbstractSequentialList

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

Methods inherited from class java.util.AbstractList

add, add, addAll, equals, get, hashCode, indexOf, iterator, lastIndexOf, listIterator, listIterator, remove, 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, notifyAll, notify, toString, wait, wait, wait

Constructor Detail

LinkedList

public LinkedList()

Constructs an empty Linked List.

LinkedList

public LinkedList(java.util.Collection c)

Constructs a LinkedList containing the elements of the specified Collection, in the order they are returned by the Collection's iterator.

Method Detail

getFirst

public java.lang.Object getFirst()

Returns the first Element in this List.

getLast

public java.lang.Object getLast()

Returns the last Element in this List.

Throws:

NoSuchElementException - List is empty.

removeFirst

public java.lang.Object removeFirst()

Removes and returns the first Element from this List.

Returns:

the first Element from this List.

Throws:

NoSuchElementException - List is empty.

removeLast

public java.lang.Object removeLast()

Removes and returns the last Element from this List.

Returns:

the last Element from this List.

Throws:

NoSuchElementException - List is empty.

addFirst

public void addFirst(java.lang.Object o)

Inserts the given element at the beginning of this List.

addLast

public void addLast(java.lang.Object o)

Appends the given element to the end of this List. (Identical in function to add(); included only for consistency.)

size

public int size()

Returns the number of elements in this List.

Specified by:

size() in interface java.util.List

Overrides:

size in class java.util.AbstractCollection

clear

public void clear()

Removes all of the elements from this List.

Specified by:

clear() in interface java.util.List

Overrides:

clear in class java.util.AbstractCollection

listIterator

public ListIterator listIterator(int index)

Returns a ListIterator of the elements in this List (in proper sequence), starting at the specified position in the list. Obeys the general contract of List.listIterator(int).

The ListIterator is fail-fast: if the LinkedList is structurally modified at any time after the Iterator is created, in any way except through the ListIterator's own remove or add methods, the Iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the Iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

Specified by:

listIterator(int) in interface java.util.List

Parameters:

index - index of first element to be returned from the ListIterator (by a call to getNext).

Throws:

IndexOutOfBoundsException - index is out of range (index < 0 || index > size()).

Overrides:

listIterator in class java.util.AbstractSequentialList

See Also:

listIterator(int)

clone

public java.lang.Object clone()

Returns a shallow copy of this LinkedList. (The elements themselves are not cloned.)

Overrides:

clone in class java.lang.Object