As many
CS departments around the
US are moving to
Java for their
teaching
language, I feel that it's time for me to share the Linked List I (and with help from a friend) developed recently. Note: this list takes
objects; not
primitive types.
//************************************************************
// This class used to define a Doubly Linked List.
//************************************************************
public class ListClass
{
//************************************************************
// Declares Nodes for the starting position, the current
// position, and the end position of the list.
//************************************************************
protected Node start;
protected Node current;
protected Node end;
//************************************************************
// This is the default constructor for the List.
// It assigns all omnipresent Nodes to null.
//************************************************************
public ListClass()
{
start = current = end = null;
}
//************************************************************
// This method, firstnode() takes an object and puts it in
// a new Node in the list.
//************************************************************
private void firstNode(Object oneObject)
{
start = current = end = new Node(oneObject, null, null);
}
//************************************************************
// This method, addBefore() takes an object and puts it in
// a new Node in the list, which is then added before other
// nodes in the list.
// This is the method which should be used when implementing
// a Stack with this List class.
//************************************************************
public void addBefore(Object twoObject)
{
if(start==null)
firstNode(twoObject);
else
{
Node dummy = new Node(twoObject, current, current.getPrev());
if(current.getPrev()==null)
start = dummy;
else
{
Node prevNode = current.getPrev();
prevNode.setNext(dummy);
}
current = dummy;
}
}
//************************************************************
// This method, addAfter() takes an object and puts it in
// a new node in the list, which is then added after other
// nodes in the list.
// This is the method which should be used when implementing
// a Queue with this List class.
//************************************************************
public void addAfter(Object newObject)
{
if(start == null)
firstNode(newObject);
else
{
Node dummy = new Node(newObject, null, current);
current.setNext(dummy);
end = current = dummy;
}
}
//************************************************************
// This method, conCat() takes a node and concatenates its
// contents to a String. It is used by the toString() method
// in this class.
//************************************************************
private String conCat(Node foo)
{
if(foo != null)
return("" + foo.getObject().toString() + "\n" + conCat(foo.getNext()));
else
return("");
}
//************************************************************
// This method, toString() provides a string representation
// of the contents of a node. It works by calling the conCat()
// method.
//************************************************************
public String toString()
{
return(conCat(start));
}
}
Of course, you might want to use a node class with the following fields and methods when you implement the above list:
//************************************************************
// This class provides a comprehensive definition
// of a Node that can be used in Linked Lists,
// and all derived data structures.
//************************************************************
public class Node
{
//************************************************************
// Declares an object to hold the contents of the node,
// as well as neighboring nodes next and previous.
//************************************************************
public Object contents;
public Node next;
public Node previous;
//************************************************************
// This is the default constructor for the Node class.
// It takes an object and assigns it to the contents field,
// and also takes a neighboring node next.
//************************************************************
public Node(Object nodeValue, Node next)
{
contents = nodeValue;
this.next = next;
}
//************************************************************
// This is the overridden constructor for the Node class.
// It takes an object and assigns it to the contents field,
// and also takes two neighboring nodes, next and previous.
//************************************************************
public Node(Object nodeValue, Node nnext, Node prev)
{
contents = nodeValue;
next = nnext;
previous = prev;
}
//************************************************************
// This method, setNext() assigns a node to the next node
// available in the list.
//************************************************************
public void setNext(Node tempNext)
{
next = tempNext;
}
//************************************************************
// This method, getObject() returns the contents of the
// current node to the calling object.
//************************************************************
public Object getObject()
{
return contents;
}
//************************************************************
// This method, getNext() returns the next node available
// in the list to the calling object.
//************************************************************
public Node getNext()
{
return next;
}
//************************************************************
// This method, getPrev() returns the previous node
// available in the list to the calling object.
//************************************************************
public Node getPrev()
{
return previous;
}
//************************************************************
// This method, setPrevious assigns a node to the previous
// node available in the list.
//************************************************************
public void setPrevious(Node tempPrevious)
{
previous = tempPrevious;
}
}