gnu.trove

Class TLinkedList<T,extends,TLinkable>

Implemented Interfaces:
Externalizable

public class TLinkedList<T,extends,TLinkable>
extends AbstractSequentialList
implements Externalizable

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.12 2007/11/01 16:08:14 robeden Exp $
Author:
Eric D. Friedman
See Also:
TLinkable

Nested Class Summary

protected class
TLinkedList.IteratorImpl
A ListIterator that supports additions and deletions.

Field Summary

protected T
_head
the head of the list
protected int
_size
the number of elements in the list
protected T
_tail
the tail of the list

Constructor Summary

TLinkedList()
Creates a new TLinkedList instance.

Method Summary

@Override
T get(int index)
boolean
add(T linkable)
Appends linkable to the end of the list.
void
add(int index, T linkable)
Inserts linkable at index index in the list.
void
addAfter(T current, T newElement)
Inserts newElement into the list immediately after current.
void
addBefore(T current, T newElement)
Inserts newElement into the list immediately before current.
void
addFirst(T linkable)
Inserts linkable at the head of the list.
void
addLast(T linkable)
Adds linkable to the end of the list.
void
clear()
Empties the list.
boolean
contains(Object o)
A linear search for o in the list.
boolean
forEachValue(TObjectProcedure procedure)
Executes procedure for each entry in the list.
T
getFirst()
Returns the head of the list
T
getLast()
Returns the tail of the list.
T
getNext(T current)
Return the node following the given node.
T
getPrevious(T current)
Return the node preceding the given node.
protected void
insert(int index, T linkable)
Implementation of index-based list insertions.
ListIterator
listIterator(int index)
Returns an iterator positioned at index.
void
readExternal(ObjectInput in)
boolean
remove(Object o)
Removes the specified element from the list.
T
removeFirst()
Remove and return the first element in the list.
T
removeLast()
Remove and return the last element in the list.
int
size()
Returns the number of elements in the list.
Object[]
toArray()
Copies the list's contents into a native array.
Object[]
toUnlinkedArray()
Copies the list to a native array, destroying the next/previous links as the copy is made.
void
writeExternal(ObjectOutput out)

Field Details

_head

protected T _head
the head of the list

_size

protected int _size
the number of elements in the list

_tail

protected T _tail
the tail of the list

Constructor Details

TLinkedList

public TLinkedList()
Creates a new TLinkedList instance.

Method Details

T get

public @Override T get(int index)

add

public boolean add(T linkable)
Appends linkable to the end of the list.
Parameters:
linkable - an object of type TLinkable
Returns:
always true

add

public void add(int index,
                T linkable)
Inserts linkable at index index in the list. All values > index are shifted over one position to accommodate the new addition.
Parameters:
index - an int value
linkable - an object of type TLinkable

addAfter

public void addAfter(T current,
                     T newElement)
Inserts newElement into the list immediately after current. All elements to the left 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.

addBefore

public void addBefore(T current,
                      T 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.

addFirst

public void addFirst(T linkable)
Inserts linkable at the head of the list.
Parameters:
linkable - an object of type TLinkable

addLast

public void addLast(T linkable)
Adds linkable to the end of the list.
Parameters:
linkable - an object of type TLinkable

clear

public void clear()
Empties the list.

contains

public boolean contains(Object o)
A linear search for o in the list.
Parameters:
o - an Object value
Returns:
a boolean value

forEachValue

public boolean forEachValue(TObjectProcedure procedure)
Executes procedure for each entry in the list.
Parameters:
procedure - a TObjectProcedure value
Returns:
false if the loop over the values terminated because the procedure returned false for some value.

getFirst

public T getFirst()
Returns the head of the list
Returns:
an Object value

getLast

public T getLast()
Returns the tail of the list.
Returns:
an Object value

getNext

public T getNext(T current)
Return the node following the given node. This method exists for two reasons:
  1. It's really not recommended that the methods implemented by TLinkable be called directly since they're used internally by this class.
  2. This solves problems arising from generics when working with the linked objects directly.

NOTE: this should only be used with nodes contained in the list. The results are undefined with anything else.


getPrevious

public T getPrevious(T current)
Return the node preceding the given node. This method exists for two reasons:
  1. It's really not recommended that the methods implemented by TLinkable be called directly since they're used internally by this class.
  2. This solves problems arising from generics when working with the linked objects directly.

NOTE: this should only be used with nodes contained in the list. The results are undefined with anything else.


insert

protected void insert(int index,
                      T linkable)
Implementation of index-based list insertions.
Parameters:
index - an int value
linkable - an object of type TLinkable

listIterator

public 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().
Parameters:
index - an int value
Returns:
a ListIterator value

readExternal

public void readExternal(ObjectInput in)
            throws IOException,
                   ClassNotFoundException

remove

public boolean remove(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.
Parameters:
o - a TLinkable element already inserted in this list.
Returns:
true if the element was a TLinkable and removed

removeFirst

public T removeFirst()
Remove and return the first element in the list.
Returns:
an Object value

removeLast

public T removeLast()
Remove and return the last element in the list.
Returns:
an Object value

size

public int size()
Returns the number of elements in the list.
Returns:
an int value

toArray

public 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!
Returns:
an Object[] value

toUnlinkedArray

public 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

writeExternal

public void writeExternal(ObjectOutput out)
            throws IOException

GNU Trove is copyright B) 2001-2008 Eric D. Friedman. All Rights Reserved.