org.apache.commons.collections.list

Class AbstractLinkedList

public abstract class AbstractLinkedList extends Object implements 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: 219343 $ $Date: 2005-07-16 18:08:16 +0100 (Sat, 16 Jul 2005) $

Author: Rich Dougherty Phil Steitz Stephen Colebourne

Nested Class Summary
protected static classAbstractLinkedList.LinkedListIterator
A list iterator over the linked list.
protected static classAbstractLinkedList.LinkedSubList
The sublist implementation for AbstractLinkedList.
protected static classAbstractLinkedList.LinkedSubListIterator
A list iterator over the linked sub list.
protected static classAbstractLinkedList.Node
A node within the linked list.
Field Summary
protected AbstractLinkedList.Nodeheader
A Node which indicates the start and end of the list and does not hold a value.
protected intmodCount
Modification count for iterators
protected intsize
The size of the list
Constructor Summary
protected AbstractLinkedList()
Constructor that does nothing intended for deserialization.
protected AbstractLinkedList(Collection coll)
Constructs a list copying data from the specified collection.
Method Summary
booleanadd(Object value)
voidadd(int index, Object value)
booleanaddAll(Collection coll)
booleanaddAll(int index, Collection coll)
booleanaddFirst(Object o)
booleanaddLast(Object o)
protected voidaddNode(AbstractLinkedList.Node nodeToInsert, AbstractLinkedList.Node insertBeforeNode)
Inserts a new node into the list.
protected voidaddNodeAfter(AbstractLinkedList.Node node, Object value)
Creates a new node with the specified object as its value and inserts it after node.
protected voidaddNodeBefore(AbstractLinkedList.Node node, Object value)
Creates a new node with the specified object as its value and inserts it before node.
voidclear()
booleancontains(Object value)
booleancontainsAll(Collection coll)
protected AbstractLinkedList.NodecreateHeaderNode()
Creates a new node with previous, next and element all set to null.
protected AbstractLinkedList.NodecreateNode(Object value)
Creates a new node with the specified properties.
protected IteratorcreateSubListIterator(AbstractLinkedList.LinkedSubList subList)
Creates an iterator for the sublist.
protected ListIteratorcreateSubListListIterator(AbstractLinkedList.LinkedSubList subList, int fromIndex)
Creates a list iterator for the sublist.
protected voiddoReadObject(ObjectInputStream inputStream)
Deserializes the data held in this object to the stream specified.
protected voiddoWriteObject(ObjectOutputStream outputStream)
Serializes the data held in this object to the stream specified.
booleanequals(Object obj)
Objectget(int index)
ObjectgetFirst()
ObjectgetLast()
protected AbstractLinkedList.NodegetNode(int index, boolean endMarkerAllowed)
Gets the node at a particular index.
inthashCode()
intindexOf(Object value)
protected voidinit()
The equivalent of a default constructor, broken out so it can be called by any constructor and by readObject.
booleanisEmpty()
protected booleanisEqualValue(Object value1, Object value2)
Compares two values for equals.
Iteratoriterator()
intlastIndexOf(Object value)
ListIteratorlistIterator()
ListIteratorlistIterator(int fromIndex)
Objectremove(int index)
booleanremove(Object value)
booleanremoveAll(Collection coll)
protected voidremoveAllNodes()
Removes all nodes by resetting the circular list marker.
ObjectremoveFirst()
ObjectremoveLast()
protected voidremoveNode(AbstractLinkedList.Node node)
Removes the specified node from the list.
booleanretainAll(Collection coll)
Objectset(int index, Object value)
intsize()
ListsubList(int fromIndexInclusive, int toIndexExclusive)
Gets a sublist of the main list.
Object[]toArray()
Object[]toArray(Object[] array)
StringtoString()
protected voidupdateNode(AbstractLinkedList.Node node, Object value)
Updates the node with a new value.

Field Detail

header

protected transient AbstractLinkedList.Node header
A 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.

modCount

protected transient int modCount
Modification count for iterators

size

protected transient int size
The size of the list

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(Collection coll)
Constructs a list copying data from the specified collection.

Parameters: coll the collection to copy

Method Detail

add

public boolean add(Object value)

add

public void add(int index, Object value)

addAll

public boolean addAll(Collection coll)

addAll

public boolean addAll(int index, Collection coll)

addFirst

public boolean addFirst(Object o)

addLast

public boolean addLast(Object o)

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: NullPointerException if either node is null

addNodeAfter

protected void addNodeAfter(AbstractLinkedList.Node node, Object value)
Creates a new node with the specified object as its value and inserts it after node.

This implementation uses createNode and addNode.

Parameters: node node to insert after value value of the newly added node

Throws: NullPointerException if node is null

addNodeBefore

protected void addNodeBefore(AbstractLinkedList.Node node, Object value)
Creates a new node with the specified object as its value and inserts it before node.

This implementation uses createNode and addNode.

Parameters: node node to insert before value value of the newly added node

Throws: NullPointerException if node is null

clear

public void clear()

contains

public boolean contains(Object value)

containsAll

public boolean containsAll(Collection coll)

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

createSubListIterator

protected Iterator createSubListIterator(AbstractLinkedList.LinkedSubList subList)
Creates an iterator for the sublist.

Parameters: subList the sublist to get an iterator for

createSubListListIterator

protected 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

doReadObject

protected void doReadObject(ObjectInputStream inputStream)
Deserializes the data held in this object to the stream specified.

The first serializable subclass must call this method from readObject.

doWriteObject

protected void doWriteObject(ObjectOutputStream outputStream)
Serializes the data held in this object to the stream specified.

The first serializable subclass must call this method from writeObject.

equals

public boolean equals(Object obj)

get

public Object get(int index)

getFirst

public Object getFirst()

getLast

public Object getLast()

getNode

protected AbstractLinkedList.Node getNode(int index, boolean endMarkerAllowed)
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: 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

hashCode

public int hashCode()

indexOf

public int indexOf(Object value)

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.

isEmpty

public boolean isEmpty()

isEqualValue

protected boolean isEqualValue(Object value1, 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

iterator

public Iterator iterator()

lastIndexOf

public int lastIndexOf(Object value)

listIterator

public ListIterator listIterator()

listIterator

public ListIterator listIterator(int fromIndex)

remove

public Object remove(int index)

remove

public boolean remove(Object value)

removeAll

public boolean removeAll(Collection coll)

removeAllNodes

protected void removeAllNodes()
Removes all nodes by resetting the circular list marker.

removeFirst

public Object removeFirst()

removeLast

public Object removeLast()

removeNode

protected void removeNode(AbstractLinkedList.Node node)
Removes the specified node from the list.

Parameters: node the node to remove

Throws: NullPointerException if node is null

retainAll

public boolean retainAll(Collection coll)

set

public Object set(int index, Object value)

size

public int size()

subList

public List subList(int fromIndexInclusive, int toIndexExclusive)
Gets a sublist of the main list.

Parameters: fromIndexInclusive the index to start from toIndexExclusive the index to end at

Returns: the new sublist

toArray

public Object[] toArray()

toArray

public Object[] toArray(Object[] array)

toString

public String toString()

updateNode

protected void updateNode(AbstractLinkedList.Node node, 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

Copyright © 2001-2008 Apache Software Foundation. All Rights Reserved.