gnu.trove

Class TLinkedList

java.lang.Object

java.util.AbstractCollection<E>

java.util.AbstractList<E>

java.util.AbstractSequentialList

gnu.trove.TLinkedList

All Implemented Interfaces:

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

public class TLinkedList
extends java.util.AbstractSequentialList
implements java.io.Serializable

A LinkedList implementation which holds instances of type TLinkable.

Using this implementation allows you to get java.util.LinkedList behavior (a doubly linked list, with Iterators that support insert and delete operations) without incurring the overhead of creating Node wrapper objects for every element in your list.

The requirement to achieve this time/space gain is that the Objects stored in the List implement the TLinkable interface.

The limitations are that you cannot put the same object into more than one list or more than once in the same list. You must also ensure that you only remove objects that are actually in the list. That is, if you have an object A and lists l1 and l2, you must ensure that you invoke List.remove(A) on the correct list. It is also forbidden to invoke List.remove() with an unaffiliated TLinkable (one that belongs to no list): this will destroy the list you invoke it on.

Created: Sat Nov 10 15:25:10 2001

Version:

$Id: TLinkedList.java,v 1.4 2002/04/08 02:02:28 ericdf Exp $

Author:

Eric D. Friedman

See Also:

TLinkable, Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected class	TLinkedList.IteratorImpl A ListIterator that supports additions and deletions.

Field Summary

Fields

Modifier and Type	Field and Description
protected TLinkable	_head the head of the list
protected int	_size the number of elements in the list
protected TLinkable	_tail the tail of the list

Fields inherited from class java.util.AbstractList

modCount

Constructor Summary

Constructors

Constructor and Description
TLinkedList() Creates a new TLinkedList instance.

Method Summary

Methods

Modifier and Type	Method and Description
void	add(int index, java.lang.Object linkable) Inserts linkable at index index in the list.
boolean	add(java.lang.Object linkable) Appends linkable to the end of the list.
void	addBefore(TLinkable current, TLinkable newElement) Inserts newElement into the list immediately before current.
void	addFirst(java.lang.Object linkable) Inserts linkable at the head of the list.
void	addLast(java.lang.Object linkable) Adds linkable to the end of the list.
void	clear() Empties the list.
boolean	contains(java.lang.Object o) A linear search for o in the list.
java.lang.Object	getFirst() Returns the head of the list
java.lang.Object	getLast() Returns the tail of the list.
protected void	insert(int index, java.lang.Object linkable) Implementation of index-based list insertions.
java.util.ListIterator	listIterator(int index) Returns an iterator positioned at index.
boolean	remove(java.lang.Object o) Removes the specified element from the list.
java.lang.Object	removeFirst() Remove and return the first element in the list.
java.lang.Object	removeLast() Remove and return the last element in the list.
int	size() Returns the number of elements in the list.
java.lang.Object[]	toArray() Copies the list's contents into a native array.
java.lang.Object[]	toUnlinkedArray() Copies the list to a native array, destroying the next/previous links as the copy is made.

Methods inherited from class java.util.AbstractSequentialList

addAll, get, iterator, remove, set

Methods inherited from class java.util.AbstractList

equals, hashCode, indexOf, lastIndexOf, listIterator, removeRange, subList

Methods inherited from class java.util.AbstractCollection

addAll, containsAll, isEmpty, removeAll, retainAll, toArray, toString

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.List

addAll, containsAll, isEmpty, removeAll, retainAll, toArray

Field Detail

_head

protected TLinkable _head

the head of the list

_tail

protected TLinkable _tail

the tail of the list

_size

protected int _size

the number of elements in the list

Constructor Detail

TLinkedList

public TLinkedList()

Creates a new TLinkedList instance.

Method Detail

listIterator

public java.util.ListIterator listIterator(int index)

Returns an iterator positioned at index. Assuming that the list has a value at that index, calling next() will retrieve and advance the iterator. Assuming that there is a value before index in the list, calling previous() will retrieve it (the value at index - 1) and move the iterator to that position. So, iterating from front to back starts at 0; iterating from back to front starts at size().

Specified by:

listIterator in interface java.util.List

Specified by:

listIterator in class java.util.AbstractSequentialList

Parameters:

index - an int value

Returns:

a ListIterator value

size

public int size()

Returns the number of elements in the list.

Specified by:

size in interface java.util.Collection

Specified by:

size in interface java.util.List

Specified by:

size in class java.util.AbstractCollection

Returns:

an int value

add

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

Inserts linkable at index index in the list. All values > index are shifted over one position to accomodate the new addition.

Specified by:

add in interface java.util.List

Overrides:

add in class java.util.AbstractSequentialList

Parameters:

index - an int value

linkable - an object of type TLinkable

add

public boolean add(java.lang.Object linkable)

Appends linkable to the end of the list.

Specified by:

add in interface java.util.Collection

Specified by:

add in interface java.util.List

Overrides:

add in class java.util.AbstractList

Parameters:

linkable - an object of type TLinkable

Returns:

always true

addFirst

public void addFirst(java.lang.Object linkable)

Inserts linkable at the head of the list.

Parameters:

linkable - an object of type TLinkable

addLast

public void addLast(java.lang.Object linkable)

Adds linkable to the end of the list.

Parameters:

linkable - an object of type TLinkable

clear

public void clear()

Empties the list.

Specified by:

clear in interface java.util.Collection

Specified by:

clear in interface java.util.List

Overrides:

clear in class java.util.AbstractList

toArray

public java.lang.Object[] toArray()

Copies the list's contents into a native array. This will be a shallow copy: the Tlinkable instances in the Object[] array have links to one another: changing those will put this list into an unpredictable state. Holding a reference to one element in the list will prevent the others from being garbage collected unless you clear the next/previous links. Caveat programmer!

Specified by:

toArray in interface java.util.Collection

Specified by:

toArray in interface java.util.List

Overrides:

toArray in class java.util.AbstractCollection

Returns:

an Object[] value

toUnlinkedArray

public java.lang.Object[] toUnlinkedArray()

Copies the list to a native array, destroying the next/previous links as the copy is made. This list will be emptied after the copy (as if clear() had been invoked). The Object[] array returned will contain TLinkables that do not hold references to one another and so are less likely to be the cause of memory leaks.

Returns:

an Object[] value

contains

public boolean contains(java.lang.Object o)

A linear search for o in the list.

Specified by:

contains in interface java.util.Collection

Specified by:

contains in interface java.util.List

Overrides:

contains in class java.util.AbstractCollection

Parameters:

o - an Object value

Returns:

a boolean value

getFirst

public java.lang.Object getFirst()

Returns the head of the list

Returns:

an Object value

getLast

public java.lang.Object getLast()

Returns the tail of the list.

Returns:

an Object value

removeFirst

public java.lang.Object removeFirst()

Remove and return the first element in the list.

Returns:

an Object value

removeLast

public java.lang.Object removeLast()

Remove and return the last element in the list.

Returns:

an Object value

insert

protected void insert(int index,
          java.lang.Object linkable)

Implementation of index-based list insertions.

Parameters:

index - an int value

linkable - an object of type TLinkable

remove

public boolean remove(java.lang.Object o)

Removes the specified element from the list. Note that it is the caller's responsibility to ensure that the element does, in fact, belong to this list and not another instance of TLinkedList.

Specified by:

remove in interface java.util.Collection

Specified by:

remove in interface java.util.List

Overrides:

remove in class java.util.AbstractCollection

Parameters:

o - a TLinkable element already inserted in this list.

Returns:

true if the element was a TLinkable and removed

addBefore

public void addBefore(TLinkable current,
             TLinkable newElement)

Inserts newElement into the list immediately before current. All elements to the right of and including current are shifted over.

Parameters:

current - a TLinkable value currently in the list.

newElement - a TLinkable value to be added to the list.