gnu.trove
Class TLinkedList<T,extends,TLinkable>
AbstractSequentialList
gnu.trove.TLinkedList<T,extends,TLinkable>
- 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
$Id: TLinkedList.java,v 1.12 2007/11/01 16:08:14 robeden Exp $
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
|
@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)
|
_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
TLinkedList
public TLinkedList()
Creates a new TLinkedList
instance.
T get
public @Override T get(int index)
add
public boolean add(T linkable)
Appends linkable to the end of the list.
linkable
- an object of type TLinkable
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.
index
- an int
valuelinkable
- 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.
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.
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.
linkable
- an object of type TLinkable
addLast
public void addLast(T linkable)
Adds linkable to the end of the list.
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.
forEachValue
public boolean forEachValue(TObjectProcedure procedure)
Executes procedure for each entry in the list.
procedure
- a TObjectProcedure
value
- 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
getLast
public T getLast()
Returns the tail of the list.
getNext
public T getNext(T current)
Return the node following the given node. This method exists for two reasons:
- It's really not recommended that the methods implemented by TLinkable be
called directly since they're used internally by this class.
- 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:
- It's really not recommended that the methods implemented by TLinkable be
called directly since they're used internally by this class.
- 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.
index
- an int
valuelinkable
- 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().
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.
o
- a TLinkable element already inserted in this list.
- true if the element was a TLinkable and removed
removeFirst
public T removeFirst()
Remove and return the first element in the list.
removeLast
public T removeLast()
Remove and return the last element in the list.
size
public int size()
Returns the number of elements in the list.
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!
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.
writeExternal
public void writeExternal(ObjectOutput out)
throws IOException
GNU Trove is copyright B) 2001-2008 Eric D. Friedman. All Rights Reserved.