fi.joensuu.cs.tra
Class TraLinkedList<E>

java.lang.Object
  fi.joensuu.cs.tra.TraLinkedList<E>

All Implemented Interfaces:

Iterable<E>

public class TraLinkedList<E>
extends Object
implements Iterable<E>

TraLinkedList is a simple linked list composed of fi.joensuu.cs.tra.Listnodes. TraLinkedList acts as a wrapper that keeps track of the first and last ListNodes and provides methods for manipulating the list. Some methods like next(fi.joensuu.cs.tra.ListNode) and previous(fi.joensuu.cs.tra.ListNode) are basically just wrappers for ListNode.next() and ListNode.previous(). EOL is user to mark the end of the list, and belongs to one list only. It cannot be operated upon except when used in inserting a ListNode at the end of the list. Inserting a ListNode at the beginning of the list is done by calling insert with the first node as the position. In other words, the nodes are always inserted before the specified node. For example, reversing a list using two lists could be done like this

   TraLinkedList originalList = new TraLinkedList();
   for (int i = 20; --i >= 0; )
     originalList.insert(originalList.EOL, new Integer(i));

   ListNode tmp;

   TraLinkedList reversedList = new TraLinkedList();
   tmp = originalList.last();
   while (tmp != null) {
     reversedList.insert(reversedList.EOL, tmp.getElement());
     tmp = reversedList.previous(tmp);
   }
 

Of note is that the element references are the same here even though the node references are not. That means that modifying the elements in one list modifies those of the other one too, unless of course the elements are immutable (primitive wrappers, Strings et cetera.) Using the the same nodes in two different lists should be impossible and even if it is not, is highly unadvisable.

Nested Class Summary

class	TraLinkedList.ElementIteratorWrapper
class	TraLinkedList.NodeIteratorWrapper

Field Summary

ListNode<E>

EOL Denotes the end of the list.

Constructor Summary

TraLinkedList()
Creates an empty list.

TraLinkedList(String elements)
Creates an empty list and uses elements instead of "nodes" in iterator exceptions.

Method Summary

Iterator<E>	elementIterator() Returns an Iterator over the elements of this list.
Iterable<E>	elements() Returns an Iterable covering the elements of this list for use with the foreach-construct.
ListNode<E>	find(ListNode<E> node, E element) Returns the first ListNode with the specified element starting from the specified ListNode or null if none is found.
ListNode<E>	first() Returns the first node of this list.
ListNode<E>	insert(ListNode<E> node, E element) Inserts a new ListNode with the specified element in front of the specified ListNode.
boolean	isEmpty() Returns true if this list is empty.
Iterator<E>	iterator() Returns an Iterator over the elements of this list.
ListNode<E>	last() Returns the last node of this list.
ListNode<E>	next(ListNode<E> node) Returns the specified ListNode's next ListNode or EOL if none exists.
Iterator<ListNode<E>>	nodeIterator() Returns an Iterator over the nodes of this list.
Iterable<ListNode<E>>	nodes() Returns an Iterable covering the nodes of this list for use with the foreach-construct.
ListNode<E>	previous(ListNode<E> node) Returns the specified ListNode's previous ListNode or null if none exists.
E	remove(ListNode<E> node) Removes a ListNode from this TraLinkedList.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

EOL

public final ListNode<E> EOL

Denotes the end of the list.

Constructor Detail

TraLinkedList

public TraLinkedList()

Creates an empty list.

TraLinkedList

public TraLinkedList(String elements)

Creates an empty list and uses elements instead of "nodes" in iterator exceptions.

Parameters:

elements - name of elements for use in exceptions, plural.

Method Detail

isEmpty

public boolean isEmpty()

Returns true if this list is empty.

Returns:

true if this list has no ListNodes.

first

public ListNode<E> first()

Returns the first node of this list.

Returns:

the first ListNode of this list or EOL if this list is empty.

last

public ListNode<E> last()

Returns the last node of this list.

Returns:

the last ListNode of this list or EOL if this list is empty.

insert

public ListNode<E> insert(ListNode<E> node,
                          E element)

Inserts a new ListNode with the specified element in front of the specified ListNode. If node is EOL, the ListNode will be inserted at the end of the TraLinkedList.

Parameters:

node - the ListNode in front of which newNode will be inserted. If node is EOL, node will be inserted at the end of the TraLinkedList.

element - the element for the new ListNode

Returns:

the inserted ListNode

Throws:

TraLinkedListException - if node is null.

remove

public E remove(ListNode<E> node)

Removes a ListNode from this TraLinkedList.

Parameters:

node - the ListNode to be removed.

Returns:

the removed ListNode's element.

Throws:

TraLinkedListException - if node is null.

TraLinkedListException - if node is EOL.

next

public ListNode<E> next(ListNode<E> node)

Returns the specified ListNode's next ListNode or EOL if none exists.

Parameters:

node - the ListNode the next ListNode of which is to be returned.

Returns:

the next ListNode of node or EOL if none exists.

Throws:

TraLinkedListException - if node is null.

previous

public ListNode<E> previous(ListNode<E> node)

Returns the specified ListNode's previous ListNode or null if none exists.

Parameters:

node - the ListNode the previous ListNode of which is to be returned.

Returns:

the previous ListNode of node or null if none exists.

Throws:

TraLinkedListException - if node is null.

find

public ListNode<E> find(ListNode<E> node,
                        E element)

Returns the first ListNode with the specified element starting from the specified ListNode or null if none is found.

Parameters:

node - the node to start searching from.

element - the element to search for.

Returns:

the first ListNode with the specified element or null if none is found.

Throws:

TraLinkedListException - if node is null or EOL.

elements

public Iterable<E> elements()

Returns an Iterable covering the elements of this list for use with the foreach-construct.

Returns:

An Iterable covering the elements of this list.

nodes

public Iterable<ListNode<E>> nodes()

Returns an Iterable covering the nodes of this list for use with the foreach-construct.

Returns:

An Iterable covering the nodes of this list.

iterator

public Iterator<E> iterator()

Returns an Iterator over the elements of this list.

Specified by:

iterator in interface Iterable<E>

Returns:

an Iterator over the elements of this list.

elementIterator

public Iterator<E> elementIterator()

Returns an Iterator over the elements of this list.

Returns:

an Iterator over the elements of this list.

nodeIterator

public Iterator<ListNode<E>> nodeIterator()

Returns an Iterator over the nodes of this list.

Returns:

an Iterator over the nodes of this list.