org.apache.commons.collections.list
Class AbstractLinkedList

java.lang.Object
  org.apache.commons.collections.list.AbstractLinkedList

All Implemented Interfaces:

java.lang.Iterable, java.util.Collection, java.util.List

Direct Known Subclasses:

CursorableLinkedList, NodeCachingLinkedList

public abstract class AbstractLinkedList
extends java.lang.Object
implements java.util.List

An abstract implementation of a linked list which provides numerous points for subclasses to override.

Overridable methods are provided to change the storage node and to change how nodes are added to and removed. Hopefully, all you need for unusual subclasses is here.

Since:

Commons Collections 3.0

Version:

$Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $

Author:

Rich Dougherty, Phil Steitz, Stephen Colebourne

Nested Class Summary

protected static class	AbstractLinkedList.LinkedListIterator A list iterator over the linked list.
protected static class	AbstractLinkedList.LinkedSubList The sublist implementation for AbstractLinkedList.
protected static class	AbstractLinkedList.LinkedSubListIterator A list iterator over the linked sub list.
protected static class	AbstractLinkedList.Node A node within the linked list.

Field Summary

protected AbstractLinkedList.Node	header A AbstractLinkedList.Node which indicates the start and end of the list and does not hold a value.
protected int	modCount Modification count for iterators
protected int	size The size of the list

Constructor Summary

protected	AbstractLinkedList() Constructor that does nothing intended for deserialization.
protected	AbstractLinkedList(java.util.Collection coll) Constructs a list copying data from the specified collection.

Method Summary

void	add(int index, java.lang.Object value)
boolean	add(java.lang.Object value)
boolean	addAll(java.util.Collection coll)
boolean	addAll(int index, java.util.Collection coll)
boolean	addFirst(java.lang.Object o)
boolean	addLast(java.lang.Object o)
protected void	addNode(AbstractLinkedList.Node nodeToInsert, AbstractLinkedList.Node insertBeforeNode) Inserts a new node into the list.
protected void	addNodeAfter(AbstractLinkedList.Node node, java.lang.Object value) Creates a new node with the specified object as its value and inserts it after node.
protected void	addNodeBefore(AbstractLinkedList.Node node, java.lang.Object value) Creates a new node with the specified object as its value and inserts it before node.
void	clear()
boolean	contains(java.lang.Object value)
boolean	containsAll(java.util.Collection coll)
protected AbstractLinkedList.Node	createHeaderNode() Creates a new node with previous, next and element all set to null.
protected AbstractLinkedList.Node	createNode(java.lang.Object value) Creates a new node with the specified properties.
protected java.util.Iterator	createSubListIterator(AbstractLinkedList.LinkedSubList subList) Creates an iterator for the sublist.
protected java.util.ListIterator	createSubListListIterator(AbstractLinkedList.LinkedSubList subList, int fromIndex) Creates a list iterator for the sublist.
protected void	doReadObject(java.io.ObjectInputStream inputStream) Deserializes the data held in this object to the stream specified.
protected void	doWriteObject(java.io.ObjectOutputStream outputStream) Serializes the data held in this object to the stream specified.
boolean	equals(java.lang.Object obj)
java.lang.Object	get(int index)
java.lang.Object	getFirst()
java.lang.Object	getLast()
protected AbstractLinkedList.Node	getNode(int index, boolean endMarkerAllowed) Gets the node at a particular index.
int	hashCode()
int	indexOf(java.lang.Object value)
protected void	init() The equivalent of a default constructor, broken out so it can be called by any constructor and by readObject.
boolean	isEmpty()
protected boolean	isEqualValue(java.lang.Object value1, java.lang.Object value2) Compares two values for equals.
java.util.Iterator	iterator()
int	lastIndexOf(java.lang.Object value)
java.util.ListIterator	listIterator()
java.util.ListIterator	listIterator(int fromIndex)
java.lang.Object	remove(int index)
boolean	remove(java.lang.Object value)
boolean	removeAll(java.util.Collection coll)
protected void	removeAllNodes() Removes all nodes by resetting the circular list marker.
java.lang.Object	removeFirst()
java.lang.Object	removeLast()
protected void	removeNode(AbstractLinkedList.Node node) Removes the specified node from the list.
boolean	retainAll(java.util.Collection coll)
java.lang.Object	set(int index, java.lang.Object value)
int	size()
java.util.List	subList(int fromIndexInclusive, int toIndexExclusive) Gets a sublist of the main list.
java.lang.Object[]	toArray()
java.lang.Object[]	toArray(java.lang.Object[] array)
java.lang.String	toString()
protected void	updateNode(AbstractLinkedList.Node node, java.lang.Object value) Updates the node with a new value.

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

header

protected transient AbstractLinkedList.Node header

A AbstractLinkedList.Node which indicates the start and end of the list and does not hold a value. The value of next is the first item in the list. The value of of previous is the last item in the list.

size

protected transient int size

The size of the list

modCount

protected transient int modCount

Modification count for iterators

Constructor Detail

AbstractLinkedList

protected AbstractLinkedList()

Constructor that does nothing intended for deserialization.

If this constructor is used by a serializable subclass then the init() method must be called.

AbstractLinkedList

protected AbstractLinkedList(java.util.Collection coll)

Constructs a list copying data from the specified collection.

Parameters:

coll - the collection to copy

Method Detail

init

protected void init()

The equivalent of a default constructor, broken out so it can be called by any constructor and by readObject. Subclasses which override this method should make sure they call super, so the list is initialised properly.

size

public int size()

Specified by:

size in interface java.util.Collection

Specified by:

size in interface java.util.List

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface java.util.Collection

Specified by:

isEmpty in interface java.util.List

get

public java.lang.Object get(int index)

Specified by:

get in interface java.util.List

iterator

public java.util.Iterator iterator()

Specified by:

iterator in interface java.lang.Iterable

Specified by:

iterator in interface java.util.Collection

Specified by:

iterator in interface java.util.List

listIterator

public java.util.ListIterator listIterator()

Specified by:

listIterator in interface java.util.List

listIterator

public java.util.ListIterator listIterator(int fromIndex)

Specified by:

listIterator in interface java.util.List

indexOf

public int indexOf(java.lang.Object value)

Specified by:

indexOf in interface java.util.List

lastIndexOf

public int lastIndexOf(java.lang.Object value)

Specified by:

lastIndexOf in interface java.util.List

contains

public boolean contains(java.lang.Object value)

Specified by:

contains in interface java.util.Collection

Specified by:

contains in interface java.util.List

containsAll

public boolean containsAll(java.util.Collection coll)

Specified by:

containsAll in interface java.util.Collection

Specified by:

containsAll in interface java.util.List

toArray

public java.lang.Object[] toArray()

Specified by:

toArray in interface java.util.Collection

Specified by:

toArray in interface java.util.List

toArray

public java.lang.Object[] toArray(java.lang.Object[] array)

Specified by:

toArray in interface java.util.Collection

Specified by:

toArray in interface java.util.List

subList

public java.util.List subList(int fromIndexInclusive,
                              int toIndexExclusive)

Gets a sublist of the main list.

Specified by:

subList in interface java.util.List

Parameters:

fromIndexInclusive - the index to start from

toIndexExclusive - the index to end at

Returns:

the new sublist

add

public boolean add(java.lang.Object value)

Specified by:

add in interface java.util.Collection

Specified by:

add in interface java.util.List

add

public void add(int index,
                java.lang.Object value)

Specified by:

add in interface java.util.List

addAll

public boolean addAll(java.util.Collection coll)

Specified by:

addAll in interface java.util.Collection

Specified by:

addAll in interface java.util.List

addAll

public boolean addAll(int index,
                      java.util.Collection coll)

Specified by:

addAll in interface java.util.List

remove

public java.lang.Object remove(int index)

Specified by:

remove in interface java.util.List

remove

public boolean remove(java.lang.Object value)

Specified by:

remove in interface java.util.Collection

Specified by:

remove in interface java.util.List

removeAll

public boolean removeAll(java.util.Collection coll)

Specified by:

removeAll in interface java.util.Collection

Specified by:

removeAll in interface java.util.List

retainAll

public boolean retainAll(java.util.Collection coll)

Specified by:

retainAll in interface java.util.Collection

Specified by:

retainAll in interface java.util.List

set

public java.lang.Object set(int index,
                            java.lang.Object value)

Specified by:

set in interface java.util.List

clear

public void clear()

Specified by:

clear in interface java.util.Collection

Specified by:

clear in interface java.util.List

getFirst

public java.lang.Object getFirst()

getLast

public java.lang.Object getLast()

addFirst

public boolean addFirst(java.lang.Object o)

addLast

public boolean addLast(java.lang.Object o)

removeFirst

public java.lang.Object removeFirst()

removeLast

public java.lang.Object removeLast()

equals

public boolean equals(java.lang.Object obj)

Specified by:

equals in interface java.util.Collection

Specified by:

equals in interface java.util.List

Overrides:

equals in class java.lang.Object

hashCode

public int hashCode()

Specified by:

hashCode in interface java.util.Collection

Specified by:

hashCode in interface java.util.List

Overrides:

hashCode in class java.lang.Object

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

isEqualValue

protected boolean isEqualValue(java.lang.Object value1,
                               java.lang.Object value2)

Compares two values for equals. This implementation uses the equals method. Subclasses can override this to match differently.

Parameters:

value1 - the first value to compare, may be null

value2 - the second value to compare, may be null

Returns:

true if equal

updateNode

protected void updateNode(AbstractLinkedList.Node node,
                          java.lang.Object value)

Updates the node with a new value. This implementation sets the value on the node. Subclasses can override this to record the change.

Parameters:

node - node to update

value - new value of the node

createHeaderNode

protected AbstractLinkedList.Node createHeaderNode()

Creates a new node with previous, next and element all set to null. This implementation creates a new empty Node. Subclasses can override this to create a different class.

Returns:

newly created node

createNode

protected AbstractLinkedList.Node createNode(java.lang.Object value)

Creates a new node with the specified properties. This implementation creates a new Node with data. Subclasses can override this to create a different class.

Parameters:

value - value of the new node

addNodeBefore

protected void addNodeBefore(AbstractLinkedList.Node node,
                             java.lang.Object value)

Creates a new node with the specified object as its value and inserts it before node.

This implementation uses createNode(Object) and addNode(AbstractLinkedList.Node,AbstractLinkedList.Node).

Parameters:

node - node to insert before

value - value of the newly added node

Throws:

java.lang.NullPointerException - if node is null

addNodeAfter

protected void addNodeAfter(AbstractLinkedList.Node node,
                            java.lang.Object value)

Creates a new node with the specified object as its value and inserts it after node.

This implementation uses createNode(Object) and addNode(AbstractLinkedList.Node,AbstractLinkedList.Node).

Parameters:

node - node to insert after

value - value of the newly added node

Throws:

java.lang.NullPointerException - if node is null

addNode

protected void addNode(AbstractLinkedList.Node nodeToInsert,
                       AbstractLinkedList.Node insertBeforeNode)

Inserts a new node into the list.

Parameters:

nodeToInsert - new node to insert

insertBeforeNode - node to insert before

Throws:

java.lang.NullPointerException - if either node is null

removeNode

protected void removeNode(AbstractLinkedList.Node node)

Removes the specified node from the list.

Parameters:

node - the node to remove

Throws:

java.lang.NullPointerException - if node is null

removeAllNodes

protected void removeAllNodes()

Removes all nodes by resetting the circular list marker.

getNode

protected AbstractLinkedList.Node getNode(int index,
                                          boolean endMarkerAllowed)
                                   throws java.lang.IndexOutOfBoundsException

Gets the node at a particular index.

Parameters:

index - the index, starting from 0

endMarkerAllowed - whether or not the end marker can be returned if startIndex is set to the list's size

Throws:

java.lang.IndexOutOfBoundsException - if the index is less than 0; equal to the size of the list and endMakerAllowed is false; or greater than the size of the list

createSubListIterator

protected java.util.Iterator createSubListIterator(AbstractLinkedList.LinkedSubList subList)

Creates an iterator for the sublist.

Parameters:

subList - the sublist to get an iterator for

createSubListListIterator

protected java.util.ListIterator createSubListListIterator(AbstractLinkedList.LinkedSubList subList,
                                                           int fromIndex)

Creates a list iterator for the sublist.

Parameters:

subList - the sublist to get an iterator for

fromIndex - the index to start from, relative to the sublist

doWriteObject

protected void doWriteObject(java.io.ObjectOutputStream outputStream)
                      throws java.io.IOException

Serializes the data held in this object to the stream specified.

The first serializable subclass must call this method from writeObject.

Throws:

java.io.IOException

doReadObject

protected void doReadObject(java.io.ObjectInputStream inputStream)
                     throws java.io.IOException,
                            java.lang.ClassNotFoundException

Deserializes the data held in this object to the stream specified.

The first serializable subclass must call this method from readObject.

Throws:

java.io.IOException

java.lang.ClassNotFoundException