String List package enables us to maintain a linked list of strings.
List Node Class enables us to maintain one node in our linked list.
public class ListNode
{
String element_;
ListNode next_;
ListNode( String e, ListNode n)
{
element_ = e;
next_ = n;
}
}
A node contains a reference to a string (element_) as well as a reference to the next node in the list (next_). The constructor is designed to set both. No methods are provided as the fields in this class are accessible to all other classes in this package. Note that no qualifiers (public, private, or protected) are identified for the constructor or the fields in this class.
String Linked List Class enables us to maintain the chain of nodes that form our linked list.
public class stringLinkedList
{
ListNode header_;
public stringLinkedList( )
{
header_ = null;
}
public boolean isEmpty( )
{
return header_ == null;
}
public void makeEmpty( )
{
header_ = null;
}
As it should be obvious, this class by itself is not very interesting. It maintains the header to the linked list (header_), provides a simple constructor and a couple of methods with the obvious intent.
String Linked List Iterator Class enables us to maintain the concept of current node for a linked list.
public class stringLinkedListItr {
protected stringLinkedList myList_;
protected ListNode current_;
public stringLinkedListItr( stringLinkedList anyList )
public void insert( String x ) throws Exception
public void insertAtBeginning( String x )
public boolean find( String x )
public void remove( String x ) throws Exception
public boolean validCurrent( )
public String retrieve( )
public void first( )
public void advance( )
public String dump ()
}
The two fields in this class are myList_ and current_; they are both protected components. myList_ refers to the to the list that the iterator is bound to and current refers to the current node in the list. With the exception of the dump method, all methods in this class either affect current or use it to respond to a request. The header_ of myList_ is occasionally changed when either adding or removing the elements at the beginning of the list.
Notice that here the methods and the constructor are qualified as public. These components are accessible outside of the class. The constructor simply sets the two fields. Keep in mind that there is nothing that prevents the list from already existing when an iterator is created for it. current_ starts at the header of the list which may be null.
The following method simply lets the application check to see if current is null; it is only valid iff it is not null.
public boolean validCurrent( ) {
return current_ != null;
}
These three methods let us get the string in the current node, and navigate through the list by initially setting current to the 1st node and then advancing it from node to node. this enables an application to respond to quaries such as find all strings that start with the letter 'h'. As you can see, these types of quaries do require visiting each node and there is no way in a generic class such as stringLinkedList that you could anticipate all the different ways it is going to be used. the iterator gives us flexibility in solving many types of problems.
public String retrieve( ) {
//return the element in the current node or return null
return validCurrent( ) ? current_.element_ : null;
}
public void first( ) {
//set current to the header node, it could obviously be null
current_ = myList_.header_;
}
public void advance( ) {
//advance to the next node if current is valid, otherwise, do nothing
if( current_ != null )
current_ = current_.next_;
}
The insert method is designed to add after the current node, an exception may be thrown if current is null.
public void insert( String x ) throws Exception {
if( current_ == null )
throw new Exception( "Insertion error; invalid current" );
//create a new node, its element set to x and its next set to current's next.
ListNode newNode = new ListNode( x, current_.next_ );
//current's next needs to reference the new node.
current_.next_ = newNode;
//current needs to be set to the new node.
current_ = newNode;
}
The insertAtBeginning creates a new node and places it at the beginning of the list, no exception may occur here.
public void insertAtBeginning( String x ) {
myList_.header_= new ListNode( x, myList_.header_ );
current_ = myList_.header_;
}
The find method search the list for a particular string and returns true if the string is found, and false otherwise.
public boolean find( String x ) {
//start itr (a temporary reference) at the header
ListNode itr = myList_.header_;
//as long as long there are elements in the list, keep going
while( itr != null) {
//if the string being searched for is found, set current to the node
// that has it and return true
if(itr.element_.equals( x ) ) {
current_ = itr;
return true;
}
//advance to the next node with itr and continue with the loop; this
//instruction can't be reached if the element is found.
itr = itr.next_;
}
//if this instruction is reached, the element was not found, so return
//false.
return false;
}
The remove method searches for an element and removes it from the list. This method throws an exception if the element is not found.
public void remove( String x ) throws Exception {
//if list is empty, throw an exception
if( myList_.header_ == null )
throw new Exception( "Remove fails; empty list" );
//if the element is in the 1st node, make header reference the node
//after the 1st node, set current to the new 1st node in the list and
//return from the method.
if (myList_.header_.element_.equals(x)) {
myList_.header_ = myList_.header_.next_;
current_ = myList_.header_;
return;
}
//start itr (a temporary reference) at the header
ListNode itr = myList_.header_;
//as long as long there is a next node execute the loop.
while( itr.next_ != null) {
//if the string being searched for is found in the next node,
//remove the node containing it by having the next field of itr
//reference that node's next field.
if (itr.next_.element_.equals( x ) ) {
itr.next_ = itr.next_.next_;
current_ = myList_.header_;
return;
}
//advance to the next node with itr and continue with the loop; this
//instruction can't be reached if the element is found.
itr = itr.next_;
}
//if this instruction is reached, the element was not found, so throw
//an exception.
throw new Exception( "Remove fails; element not in list" );
}
The dump method returns a string containing all strings in the list separating them with "-->". This method is designed to help in debugging by returning the content of the list in a form that is easyly displayable.
public String dump () {
String text;
//simply store "List is Empty" in text if the list is empty.
if (myList_.header_ == null)
text = new String ("List is Empty");
else {
//store the characters "head-> " in text.
text= new String("head-> ");
//loop and concatenate all strings in the list to the end of text.
// + "--> " ensures that they are separated with -->
ListNode temp;
int last;
for (temp=myList_.header_;temp != null;temp=temp.next_)
text=text.concat(temp.element_ + "-> ");
}
//return the string that contains all strings in the list.
return text;
}