Students in Prof. Baldwin's Intermediate Java Programming classes will be responsible for understanding all of the material in this lesson.
The watchword these days is reuse, don't reinvent. Therefore, this lesson is not provided to encourage you to reinvent data structures that can be found in class libraries. Rather, this lesson is provided primarily as a review of much of what you should have learned in the Introductory Java Programming course at ACC.
If you are enrolled in Prof. Baldwin's Intermediate Java Programming course and have difficulty with any of the material in this lesson, you probably are not well-prepared for the Intermediate course.
While the program in this lesson does review much of what you should have learned in the Introductory course, there is much more that you should have learned that it doesn't review (Java arrays for example). Therefore, a complete understanding of the material in this lesson does not provide assurance that you learned everything that you should have learned in the Introductory course. In other words, an understanding of the material in this lesson is a "necessary but not sufficient" indicator of your readiness for the Intermediate course.
Because of its poor random-access capabilities, a linked-list is not a particularly good underlying structure for an ordered list. However, the development of an ordered list using a linked-list does provide some good illustrations of important Java programming concepts (such as the use of interface types). Therefore, we will develop an ordered list using an upgraded version of our general-purpose linked list class (named RawList) that we developed in an earlier lesson.
This upgraded general-purpose linked-list is then subclassed to provide the ability to create objects that will manage an ordered list.
The data structures so produced operate with objects of the generic type Object and therefore, can be used to accommodate any type of Java object so long as that object is instantiated from a class that implements the required interface.
Note that the program in the previous lesson did not require implementation of an interface. This new requirement for an interface comes about as a result of the need to perform comparisons between objects to determine which is greater, less than, equal to, etc. The interface is used to require the class from which data objects are instantiated to provide methods by which objects of the class can compare themselves against other objects of the same class.
As I mentioned in the earlier lesson, in developing this program, I didn't give much thought to access control: public, private, protected, and package. It is not likely that you would want to use this code for any serious purpose, but if you do, you will need to review and probably upgrade the access control specifiers that were used.
This program did not receive the kind of exhaustive testing that should be applied to a program of this complexity, so if you do elect to use it for any serious purpose, you should test it thoroughly before using it.
The testing that was performed was performed using JDK 1.1.3 under Win95.
The purpose of this program is to upgrade the program named List02 to add the capability to create and maintain ordered lists. The upgraded version of the program is named List03.
In addition to methods carried forward from the earlier version of the program, methods are added to the RawList class to support the insertion and removal of nodes interior to the list on the basis of the value of the data object encapsulated in the node.
Insertion is done on an ascending alphanumeric basis.
The insertion of nodes having duplicate data values is not allowed. An attempt to insert a duplicate data object causes an exception to be thrown.
The RawList class is then subclassed to provide a specialized class for instantiating objects of type OrderedList.
The prior ability to create Stack and Queue objects was not removed from the program. In all cases, the data structures so produced operate with objects of the generic type Object, and can accommodate objects of any class that implements the interface named List03A.
For an understanding of how this degree of generality is accomplished, it is suggested that you review Lesson 46 in the Introductory tutorial which is a lesson on interfaces.
A test program is provided that tests only the OrderedList capability of the program. The output from running this program is shown in the comments of the complete program listing at the end of the lesson.
As mentioned above, this data structure can accommodate any object that
is instantiated from a class that implements the interface named List03A.
The first interesting code fragment is the definition of that interface.
public interface List03A{
boolean LTE(Object inObject);
boolean LT(Object inObject);
boolean GTE(Object inObject);
boolean EQ(Object inObject);
}//end List03A |
The names of the methods are indicative of the type of comparison required. For example the method named GTE should compare two objects to determine if the object on which the method is invoked is greater than or equal to the object passed as a parameter. (This is the point where C++ programmers will be wishing for overloaded operators which are not supported by Java).
In particular, this program depends on methods defined in the class of the object being maintained in the ordered list to compare two objects and report back which is greater, less than, etc..
As mentioned earlier, a more-detailed discussion of this kind of operation was provided in Lesson 46 on interfaces. If you have any confusion or questions in this regard, you should refer back to that lesson.
The next interesting code fragment shows the definition of the test class that was used to test this program. In particular note how this class implements the required interface.
This set of data structures is designed to accommodate objects of any class that implements the interface named List03A. This class named TestClass implements that interface. Therefore, objects of this class are appropriate for use with this set of data structures.
If you modify the definition of this class, you may need to redefine the methods in the new class to make them appropriate for your new class.
Note that the comparison methods in this class receive a parameter which is an object of type Object and then cast that object to type TestClass in order to be able to access the instance variable in the object. This methodology is explained more fully in Lesson 46 on Interfaces.
An object of this class contains only a single instance variable
that is an object of type String, but there is no reason that it
could not contain many instance variables such as first name, last name,
social security number, age, weight, height, marital status, etc.
class TestClass implements List03A{
String data;
TestClass(String data){//constructor
this.data = data;
}//end constructor
//Compare for less than or equal
public boolean LTE(Object inObject){
int result =
this.data.compareTo(((TestClass)inObject).data);
if(result <= 0) return true;//is LTE
else return false;//is not LTE
}//end LTE
//...
}//end TestClass |
For example, if the class contained both the last name and the age, it might be appropriate to use the last name variable to determine which is greater, and it might be just as appropriate to use the age variable for that purpose. It might be appropriate to combine two or more instance variables such as last name and first name for that purpose.
The designer of the class must decide. The linked-list program depends on the methods of the class to provide that kind of information whenever it is needed.
In this case, for the sake of simplicity, we use the single String data member to compare objects of the class, and we use the compareTo() method of the String class to assist us in that regard. Only one of the four comparison methods is shown here because they are all very similar.
The class also contains an overridden toString() method, but it is not shown here because there is nothing new about it.
That brings us to the new method that inserts a new node into the linked-list on the basis of the value of the data object encapsulated into the node. As mentioned earlier, nodes are inserted into the list in ascending order.
This is a large method so we will discuss it in parts. The first interesting part is the method signature and the initial test to determine if the list is empty. If it is determined that the list is empty, the node being inserted becomes the first node in the list.
Note that this method receives a new data object as type Object.
Note also that it throws an exception of type Excep.
void inByValue(Object dataObj) throws Excep{
if(isEmpty()) //List is empty, make this the first node
firstNode = lastNode = getNode(dataObj); |
The next interesting code fragment throws an exception if the new node matches the first or last nodes in the list.
Note the requirement to cast the incoming object of type Object to the type of the interface in order to make it possible to access the method named EQ which is declared in the interface and is an instance method of the incoming object.
You should recall that when the exception object is thrown, execution
of the code in the method is terminated immediately and the system starts
searching for an exception handler whose type matches the type of the exception.
Control is transferred directly to that exception handler, bypassing any
remaining code in the method.
else if(((List03A)dataObj).EQ(firstNode.dataObj))
throw new Excep("Duplicate key value: " + dataObj);
else if(((List03A)dataObj).EQ(lastNode.dataObj))
throw new Excep("Duplicate key value: " + dataObj); |
Also note that even though we used the GTE method to test for greater
than the last object in the list, the object cannot possibly be equal to
the last object because we eliminated that possibility earlier. If you
go back and review the interface definition, you will note that it doesn't
include a declaration for a greater than (GT) method. So, we saved a little
programming effort here, but that may have been false economy since
it definitely makes the code less self-documenting and possibly more difficult
to maintain.
else if(((List03A)dataObj).LT(firstNode.dataObj)) this.toFront(dataObj); else if(((List03A)dataObj).GTE(lastNode.dataObj)) this.toBack(dataObj); |
Along the way, we need to be watching out for duplicate values and throw an exception if a duplicate if found.
As in previous methods that needed to traverse the list, we will use a while loop to traverse the list until the appropriate spot is found. We will then insert it, rewiring the reference variables as required.
Recall that the occurrence of a null reference to the next node indicates that the end of the list has been reached. Since we have already tested to see if we could hook it onto either end, we should find an appropriate place to insert it before reaching the end of the list.
After encapsulating the new data object in a node object and saving a reference to the node object in newPtr, we drop into our while loop.
During each iteration of the loop, we first test for duplicate and throw an exception of a duplicate is discovered.
Then we test to see if we have found the spot to insert the new node so that it will be greater than one node and less than the next node. Again note that even though we are using GTE, it cannot be equal because we eliminated that possibility when we tested for the duplicate.
Once we find the correct spot, we rewire the reference variables
and break out of the loop. By now you should have no difficulty
understanding the rewiring process.
else {
Node newPtr = getNode(dataObj);//encapsulate object
Node currentRefToNode = firstNode;//temp reference
while(currentRefToNode.nextNode != null){
if((((List03A)dataObj).EQ(//test for duplicate
currentRefToNode.nextNode.dataObj)))
throw new Excep("Duplicate key value: "
+ dataObj);
if((((List03A)dataObj).GTE(//is this the spot?
currentRefToNode.dataObj)) &&
(((List03A)dataObj).LT(
currentRefToNode.nextNode.dataObj)))
{//Found the spot. Rewire the reference variables
newPtr.nextNode = currentRefToNode.nextNode;
currentRefToNode.nextNode = newPtr;
break; //terminate loop
}//end if
//Didn't find the spot. Update reference variable
// and go back to the top of the while loop.
else currentRefToNode = currentRefToNode.nextNode;
}//end while loop
}//end else have to find a spot and insert in middle
}//end inByValue() |
There should be no circumstance where the while loop in the above method would terminate naturally.
Before entering the loop, we confirmed that the value of the data object is bracketed by the values of the data objects encapsulated in the first and last nodes in the list. That means that we should either find a duplicate (in which case we throw an exception) or should find a spot to insert the new node (in which case we break out of the loop).
This finishes our discussion of the method that is used to insert data objects by value into the linked list.
The next interesting code fragment is the method that is used to remove a data object from the linked list by matching the value of a key data object with the value of a data object already encapsulated in a node in the list.
Obviously this method may fail to find a match in which case we will throw an exception.
Again, this is a fairly long method so we will discuss it in parts. The first interesting part is the signature and the test for an empty list. As usual, we will throw an exception if the list is empty.
To be repetitive, note that this method receives a data object as the
generic type Object.
Object removeByValue(Object dataObj) throws Excep{
if(this.isEmpty()) //List is empty
throw new Excep("Empty List in removeByValue"); |
It will be useful to point out that this code fragment makes use of
methods that were developed in the previous lesson (fetchFromFront
and fetchFromBack) so if you just tuned in at this point, you may
need to go back and review that lesson.
else{ //Test for a match on the front node
if(((List03A)dataObj).EQ(firstNode.dataObj)){
return fetchFromFront();//found match on front node
//Test for match on back node
}else if(((List03A)dataObj).EQ(lastNode.dataObj)){
return fetchFromBack();//found match on back node |
If we don't find a match at the front or the back, we will search for a match interior to the list. As usual, we will use a while loop to traverse the list searching for a match. This time, however, we could hit the end of the list indicated by lastNode if no match is found. (This possibility would have been eliminated if we had done the bracket thing described above.)
By now you should have no difficulty understanding how this code works.
There are two different ways that we can decide that there is no match.
If we pass the appropriate point in the list based on value and haven't found a match, we will throw an exception. This prevents us from searching the entire list when we can make an early determination that a match doesn't exist.
Also, if the value is not bracketed by the values of the end points of the list, we could hit the end of the list without finding a match, which will also cause us to throw an exception.
A more efficient approach would be to test for the bracket condition
before beginning the search of the interior of the list and throwing an
exception if the value were not bracketed by the end points of the list.
Node currentRefToNode = firstNode,tempRefToNode;
while( currentRefToNode.nextNode != lastNode){
//test to see if value of dataObj has been passed
if(((List03A)dataObj).
LT(currentRefToNode.dataObj))
//Can't find a match, throw exception
throw new Excep(
"No match found in removeByValue");
//Test to see if the dataObj in the next node
// matches. If so, delete next node.
if(((List03A)dataObj).
EQ(currentRefToNode.nextNode.dataObj)){
//Save ref to node being removed
tempRefToNode = currentRefToNode.nextNode;
//Wire around the next node to remove it.
currentRefToNode.nextNode =
((currentRefToNode.nextNode).nextNode);
//Return data object from saved node
return tempRefToNode.dataObj;
}//end if where match was found
//Adjust references to move to next node
currentRefToNode = currentRefToNode.nextNode;
//Test to see if the next node is the last node.
if( currentRefToNode.nextNode == lastNode ){
throw new Excep(
"No match found in removeByValue");
}}}}//end else
throw new Excep(
"Should never get this far before returning\n");
}//end function |
Once we determine that the next node is a match, we save a reference to that node in tempRefToNode for use later in our return statement. Then we wire around the node to remove it from the list and return a reference to the data object encapsulated in the node.
If the current iteration doesn't produce a match, we update the reference named currentRefToNode so as to move us to the next node on the next iteration.
However, before returning to the top of the while loop for the next iteration, we need to test to see if the next node is the last node, and if so we conclude that there is no match and throw an exception.
Finally, as a safety valve, we throw an exception if control ever reaches the end of the method without either returning the matching data object, or throwing an exception, because this should never happen.
And that concludes the discussion of the method to remove a node based on matching a key value.
The next interesting code fragment is the definition of the class used to subclass the RawList class in such a way as to create and maintain a list that keeps the data objects in ascending alphanumeric order in the list.
This is accomplished by using the methods of the RawList class
to insert new nodes by the value of the data encapsulated in the node and
removing nodes by value.
class OrderedList extends RawList{
public void add(Object obj) throws Excep{
//add a new object to the list by value
this.inByValue(obj);
}//end add()
public Object remove(Object obj) throws Excep{
//remove and return an object from the list by value
return this.removeByValue(obj);
}//end remove
public void printOrderedList(){
this.printRawList();//use the existing print capability
}//end printOrderedList()
public boolean isOrderedListEmpty(){
return this.isEmpty();//use the existing empty test
}//end isOrderedListEmpty
}//end OrderedList |
This class makes it possible to add and remove objects from the list based on their value, and also to print the list and to determine if it is empty. Except for the class header and the method signatures, only four lines of code were required to accomplish this.
We will note, however, that a significant programming effort was required to upgrade the RawList class to make this possible.
/*File List03.java
Copyright 1997, R.G.Baldwin
The purpose of this program is to upgrade the program named
List02.java to add the capability to create and maintain
ordered lists.
In addition to methods carried forward from the earlier
version of the program, methods are added to the RawList
class to support the insertion and removal of nodes
interior to the list on the basis of the value of the data
object encapsulated in the node.
Insertion is done on an ascending alphanumeric basis. The
insertion of nodes having duplicate data values is not
allowed. An attempt to insert a duplicate value causes
an exception to be thrown.
The RawList class is then subclassed to provide a
specialized data structures for creating Ordered List
objects.
The prior ability to create Stack and Queue objects was
not removed from the program.
In all cases, the data structures so produced operate
with objects of the generic type Object, and can
accommodate objects of any class that implements the
interface named List03A.
For an understanding of how this degree of generality is
accomplished, it is suggested that you review Lesson #46
which is a lesson on interfaces.
The test program provided in this program tests only the
Ordered List capability of the program. The output from
running this program is shown below:
//------------------------------------------
Test the ordered list
Put some data objects in an ordered list
Try to put duplicate object in ordered list
Exception: Duplicate key value: cd
The ordered list contains:
ab
cd
ef
gh
ij
kk
kl
Remove some objects from ordered list
Removed: kl
Removed: ab
Removed: gh
The ordered list now contains:
cd
ef
ij
kk
Try to remove object with no match, cf
Exception: No match found in removeByValue
Try to remove another object with no match, kj
Exception: No match found in removeByValue
End of test
//------------------------------------------
This program was tested using JDK 1.1.3 under Win95.
**********************************************************/
import java.awt.*;
import java.awt.event.*;
import java.util.*;
//=======================================================//
/*This program implements the following kinds of data
structures: unordered linked-list, ordered linked-list,
stack, and queue.
This set of data structures is designed to accommodate
objects of any class that implements the interface named
List03A.
This class named TestClass implements that interface.
Therefore, objects of this class are appropriate for use
with this set of data structures.
If you modify the definition of this class, you will need
to redefine the methods in the new class to make them
appropriate for your new class. The compare methods are
required for use by the methods in the data structures
that need to be able to compare two objects for less
than, equal, etc. Generally, these are the methods that
support the ordered list structure.
Note that the comparison methods in this class receive
a parameter which is an object of type Object and then
cast that object to type TestClass in order to be able
to access the instance variable in the object. This
methodology is explained more fully in Lesson #46 on
Interfaces.
---------------------------------------------------------*/
class TestClass implements List03A{
//An object of this class contains a single instance
// variable which is an object of type String.
String data;
//-----------------------------------------------------//
TestClass(String data){//constructor
this.data = data;
}//end constructor
//-----------------------------------------------------//
public String toString(){//overridden toString() method
return (data);
}//end toString()
//-----------------------------------------------------//
//Compare for less than or equal
public boolean LTE(Object inObject){
int result =
this.data.compareTo(((TestClass)inObject).data);
if(result <= 0) return true;//is LTE
else return false;//is not LTE
}//end LTE
//-----------------------------------------------------//
//Compare for less than
public boolean LT(Object inObject){
int result =
this.data.compareTo(((TestClass)inObject).data);
if(result < 0) return true;//is LT
else return false;//is not LT
}//end LT
//-----------------------------------------------------//
//Compare for greater than or equal
public boolean GTE(Object inObject){
int result =
this.data.compareTo(((TestClass)inObject).data);
if(result >= 0) return true;//is GTE
else return false;//is not GTE
}//end GTE
//-----------------------------------------------------//
//Compare for equal
public boolean EQ(Object inObject){
int result =
this.data.compareTo(((TestClass)inObject).data);
if(result == 0) return true;//is equal
else return false;//is not equal
}//end EQ
}//end TestClass
//=======================================================//
/*This class is the controlling class which is used to test
the data structures developed in this lesson. This
class contains a method named test() which designed to
exercise the capabilities of the unordered linked-list,
stack, queue, and ordered list.
---------------------------------------------------------*/
class List03{//controlling class
public static void main(String[] args){//main
List03 obj = new List03();//instantiate this object
obj.test();//invoke the method named test()
}//end main
//-----------------------------------------------------//
void test(){
System.out.println("\nTest the ordered list");
//Instantiate an OrderedList object
OrderedList myOrderedList = new OrderedList();
System.out.println(
"Put some data objects in an ordered list");
try{
myOrderedList.add(new TestClass("cd"));
myOrderedList.add(new TestClass("ij"));
myOrderedList.add(new TestClass("ab"));
myOrderedList.add(new TestClass("kl"));
myOrderedList.add(new TestClass("kk"));
myOrderedList.add(new TestClass("ef"));
myOrderedList.add(new TestClass("gh"));
System.out.println(
"Try to put duplicate object in ordered list");
myOrderedList.add(new TestClass("cd"));
}catch(Excep e){System.out.println("Exception: " + e);}
System.out.println("The ordered list contains:");
myOrderedList.printOrderedList();
System.out.println(
"\nRemove some objects from ordered list");
try{
System.out.println("Removed: "
+ myOrderedList.remove(new TestClass("kl")));
System.out.println("Removed: "
+ myOrderedList.remove(new TestClass("ab")));
System.out.println("Removed: "
+ myOrderedList.remove(new TestClass("gh")));
}catch(Excep e){System.out.println("Exception: " + e);}
System.out.println("The ordered list now contains:");
myOrderedList.printOrderedList();
try{
System.out.println(
"Try to remove object with no match, cf");
System.out.println("Removed: "
+ myOrderedList.remove(new TestClass("cf")));
}catch(Excep e){System.out.println("Exception: " + e);}
try{
System.out.println(
"Try to remove another object with no match, kj");
System.out.println("Removed: "
+ myOrderedList.remove(new TestClass("kj")));
}catch(Excep e){System.out.println("Exception: " + e);}
System.out.println("End of test");
}//end test()
}//end controlling class named class02
//=======================================================//
//=======================================================//
//This is the beginning of the classes that are used to
// instantiate several different kinds of data structures.
//=======================================================//
//=======================================================//
//This is a new exception class that is used to instantiate
// exception objects for a variety of different exceptional
// conditions within the data structure methods.
class Excep extends Exception{
String diagnosticData;//put diagnostic data here
Excep(){//NoArg constructor
diagnosticData = "No diagnostic data provided";
}//end NoArg constructor
Excep(String diagnosticData){//parameterized constructor
this.diagnosticData = diagnosticData;
}//end NoArg constructor
public String toString(){//override toString()
return diagnosticData;
}//end overridden toString()
}//end class Excep
//=======================================================//
//This class is used to instantiate a node in the data
// structure. It contains an embedded object of whatever
// type is passed in as a parameter. The test class
// provide with this program uses objects of the class
// namedTestClass.
class Node{
Object dataObj; //data object is stored here
Node nextNode;//reference to the next node in the RawList
//-----------------------------------------------------//
public Node(Object dataObj){//constructor
this.dataObj = dataObj;//store incoming dataObj
}//end constructor
}//end class Node
//=======================================================//
//Begin definition of the class used to create
//and maintain a raw list
class RawList{
private Node firstNode; //reference to first node
private Node lastNode; //reference to last node
//-----------------------------------------------------//
//Function to allocate memory and return a reference
// variable for a new node.
private Node getNode( Object dataObj) {
//get reference variable to new memory
Node newNode = new Node(dataObj);
return newNode;
}//end getNode()
//-----------------------------------------------------//
//Method to determine if The structure is empty
boolean isEmpty(){
return firstNode == null;//return true if empty
}//end isEmpty()
//-----------------------------------------------------//
//Attach a new node to the front of the RawList
void toFront(Object dataObj){
//Encapsulate the incoming object in an object of type
// node and assign it to a local reference variable.
Node newNode = this.getNode(dataObj);
//Now attach the new node to the front of the list
if(this.isEmpty()) //RawList is empty
firstNode = lastNode = newNode;
else{ //RawList is not empty
newNode.nextNode = firstNode;
firstNode = newNode;
}//end if
}//end toFront()
//-----------------------------------------------------//
//Attach a new node to the back of the RawList
void toBack(Object dataObj){
//Encapsulate the incoming object in an object of type
// node and assign it to a local reference variable.
Node newNode = this.getNode(dataObj);
//Now attach the new node to the back of the list
if(this.isEmpty()) //RawList is empty
firstNode = lastNode = newNode;
else { //RawList is not empty
lastNode.nextNode = newNode;
lastNode = newNode;
}//end if
}//end toBack()
//-----------------------------------------------------//
//This method inserts a new node into the linked-list
// on the basis of its value. Nodes are assembled into
// the list in ascending order.
void inByValue(Object dataObj) throws Excep{
if(isEmpty()) //List is empty, make this the first node
firstNode = lastNode = getNode(dataObj);
//Throw an exception if the new node matches the first
// or last nodes in the list. Duplicate values are
// not allowed in the list. Note the requirement to
// cast the incoming object of type Object to the
// type of the interface in order to make it possible
// to access the method named EQ which is declared in
// the interface and is an instance method of the
// incoming object
else if(((List03A)dataObj).EQ(firstNode.dataObj))
throw new Excep("Duplicate key value: " + dataObj);
else if(((List03A)dataObj).EQ(lastNode.dataObj))
throw new Excep("Duplicate key value: " + dataObj);
//If smaller than data in first node, attach to front.
// Note that this process uses the existing method
// to encapsulate the data object in a node object
// attach it to the front of the list.
else if(((List03A)dataObj).LT(firstNode.dataObj))
this.toFront(dataObj);
//if greater than or equal (can't possibly be equal
// because that possibility was eliminated above) to
// dataObj in last node, attach at the back.
else if(((List03A)dataObj).GTE(lastNode.dataObj))
this.toBack(dataObj);
//Didn't attach to either end. Must encapsulate the
// incoming data object in a node object, find a spot
// and insert the node somewhere in the middle of the
// list.
else {
//Encapsulate the incoming object in an object of
// type node and assign it to a local reference
// variable.
Node newPtr = getNode(dataObj);
//Create a temp reference and initialize it to
// reference the front of the list
Node currentRefToNode = firstNode;
//At this point, we have established that there is
// a spot somewhere in the list where the node should
// be inserted unless the data object is a duplicate
// of an existing data object in the list. Use a
// while loop to traverse the list until that spot
// is found. Then insert it, rewiring the reference
// variables as required. The occurrence of a null
// reference to the next node indicates that the end
// of the list has been reached. Since we have
// already tested to see if we could hook it onto
// either end, we should find an appropriate place
// to insert it before reaching the end of the list.
while(currentRefToNode.nextNode != null){
//Test for duplicate values and throw an exception
// if a duplicate is discovered.
if((((List03A)dataObj).EQ(
currentRefToNode.nextNode.dataObj)))
throw new Excep("Duplicate key value: "
+ dataObj);
//Test to see if this is the spot to insert the
// new node so that it will be greater than one
// node and less than the next node. Again note
// that even though we are using GTE, it cannot
// be equal because we eliminated that possibility
// above.
if((((List03A)dataObj).GTE(
currentRefToNode.dataObj)) &&
(((List03A)dataObj).LT(
currentRefToNode.nextNode.dataObj)))
{//Found the spot. Rewire the reference variables
newPtr.nextNode = currentRefToNode.nextNode;
currentRefToNode.nextNode = newPtr;
break; //terminate loop
}//end if
//Didn't find the spot. Update reference variable
// and go back to the top of the while loop.
else currentRefToNode = currentRefToNode.nextNode;
}//end while loop
}//end else have to find a spot and insert in middle
}//end inByValue()
//-----------------------------------------------------//
//This method is used to remove a node based on a match
// with a key value.
Object removeByValue(Object dataObj) throws Excep{
if(this.isEmpty()) //List is empty
throw new Excep("Empty List in removeByValue");
//List is not empty
else{ //Test for a match on the front node
if(((List03A)dataObj).EQ(firstNode.dataObj)){
return fetchFromFront();//found match on front node
//Test for match on back node
}else if(((List03A)dataObj).EQ(lastNode.dataObj)){
return fetchFromBack();//found match on back node
//No match on the front or back. Have to search for
// a match somewhere in the middle of the list.
} else{//have to find it in the middle of the list
//declare temp reference variables
Node currentRefToNode = firstNode,tempRefToNode;
//Use a while loop to traverse the list searching
// for a match. This time, we could hit the end
// of the list indicated by lastNode if no
// match is found.
while( currentRefToNode.nextNode != lastNode){
//test to see if value of dataObj has been passed
if(((List03A)dataObj).
LT(currentRefToNode.dataObj))
//Can't find a match, throw exception
throw new Excep(
"No match found in removeByValue");
//Test to see if the dataObj in the next node
// matches. If so, delete next node.
if(((List03A)dataObj).
EQ(currentRefToNode.nextNode.dataObj)){
//Save ref to node being removed
tempRefToNode = currentRefToNode.nextNode;
//Adjust ref variable to wire around the next
// node which is being removed.
currentRefToNode.nextNode =
((currentRefToNode.nextNode).nextNode);
//Return the saved node
return tempRefToNode.dataObj;
}//end if where match was found
//Adjust references to move to next node
currentRefToNode = currentRefToNode.nextNode;
//Test to see if the next node is the last node.
// If so, this means that we can't find a match
// and should throw an exception without letting
// the while loop terminate.
if( currentRefToNode.nextNode == lastNode ){
throw new Excep(
"No match found in removeByValue");
}//end if
}//end while loop
}//end else
}//end else
throw new Excep(
"Should never get this far before returning\n");
}//end function
//-----------------------------------------------------//
//This method is used to fetch and delete a node from
// the front of the RawList. Note that all objects are
// treated as objects of the generic type Object.
Object fetchFromFront() throws Excep{
if(this.isEmpty()) //RawList is empty
throw new Excep("Empty list in fetchFromFront");
else { //RawList is not empty
//declare and initialize a local reference variable
Node tempRefToNode = firstNode;
if(firstNode == lastNode)//only one node in the list
firstNode = lastNode = null; //set both to null
else//more than one node in the list
//Wire around the first node and return it
firstNode = firstNode.nextNode;
return tempRefToNode.dataObj; //fetch successful
}//end else
}//end fetchFromFront()
//-----------------------------------------------------//
//This method is used to fetch and delete a node from the
// back of the RawList
Object fetchFromBack() throws Excep{
if(this.isEmpty()) //RawList is empty
throw new Excep("Empty list in fetchFromBack");
else { //RawList is not empty
//declare and initialize a local reference variable
Node tempRefToNode = lastNode;
if(firstNode == lastNode)//only one node in the list
firstNode = lastNode = null; //set both to null
else {//more than one node in the list
//Declare and initialize another local
// reference variable
Node currentRefToNode = firstNode;
//The list is a one-way street. The last node can
// only be removed by starting at the front and
// walking to the end touching each node along the
// way. Use a while loop to traverse the list,
// stopping at the node immediately before the
// last one.
while(currentRefToNode.nextNode != lastNode)
currentRefToNode = currentRefToNode.nextNode;
//Cut the last node loose and set the reference
// to the next node in the new last node to null
// to indicate the new end of the list.
lastNode = currentRefToNode;
currentRefToNode.nextNode = null;
}//end else
//Return the data object from the saved last node.
return tempRefToNode.dataObj; //fetch successful
}//end else
}//end fetchFromBack()
//-----------------------------------------------------//
//This method is used to display the contents of the
// RawList object.
void printRawList(){
if(this.isEmpty()){
System.out.println("Empty");
return;
}//end if
//Not empty. Declare and initialize a local
// reference variable to the first node in the list
Node currentRefToNode = firstNode;
//Use a while loop to traverse the list displaying
// the data object in each node along the way.
while(currentRefToNode != null){
System.out.println("" + currentRefToNode.dataObj);
currentRefToNode = currentRefToNode.nextNode;
}//end while
}//end printRawList()
}//end class RawList
//=======================================================//
//The above class was used to provide the raw list which
// serves as a superclass for the following specialized
// subclasses.
//=======================================================//
//This class subclasses the class named RawList in such
// a way as to provide queue behavior. A queue is a
// first-in/first-out structure. This can be accomplished
// by entering data into the back of a RawList object and
// removing it from the front of the object.
//As you can see, this is a very simple class. It simply
// invokes the methods of the RawList class on a selective
// basis.
class MyQueue extends RawList{
public void enqueue(Object obj){
this.toBack(obj);//enqueue data to the back of the list
}//end enqueue()
public Object dequeue() throws Excep{
//dequeue data from the front of the list
return this.fetchFromFront();
}//end dequeue()
public void printQueue(){
this.printRawList();//use the existing print capability
}//end printQueue()
public boolean isQueueEmpty(){
return this.isEmpty();//use the existing empty test
}//end isQueueEmpty
}//end class MyQueue
//=======================================================//
//This class is used to subclass the RawList class in
// such a way as to provide stack behavior. A stack is a
// last-in/first-out structure. This can be accomplished
// by attaching data to the front of the list and
// removing it from the front of the list.
class MyStack extends RawList{
public void push(Object obj){
this.toFront(obj);//attach new data to front of list
}//end push
public Object pop() throws Excep{
//remove new data from the front of the list
return this.fetchFromFront();
}//end pop()
public void printStack(){
this.printRawList();//use existing print capability
}//end printStack()
public boolean isStackEmpty(){
return this.isEmpty();//use the existing empty test
}//end isStackEmpty
}//end class MyStack
//=======================================================//
//This class is used subclass the RawList class in such
// a way as to to create and maintain a list that
// keeps the data objects in ascending alphanumeric
// order in the list. This can be accomplished by using
// the existing methods to insert new nodes by the value
// of the data encapsulated in the node and removing
// nodes by value.
class OrderedList extends RawList{
public void add(Object obj) throws Excep{
//add a new object to the list by value
this.inByValue(obj);
}//end add()
public Object remove(Object obj) throws Excep{
//remove and return an object from the list by value
return this.removeByValue(obj);
}//end remove
public void printOrderedList(){
this.printRawList();//use the existing print capability
}//end printOrderedList()
public boolean isOrderedListEmpty(){
return this.isEmpty();//use the existing empty test
}//end isOrderedListEmpty
}//end OrderedList
//=======================================================// |
As before, the solution is a simple one: change the relationship of OrderedList and RawList from one of inheritance to one of composition. In other words, change from an "is a" relationship to a "has a" relationship.
What this means is to eliminate the inheritance relationship, and to make an instance variable in the OrderedList class of type RawList. This will hide the methods of the RawList class from other code within the scope of an OrderedList object, but make those methods available to code within the methods of the OrderedList class.
Hopefully you now understand the distinction between an inheritance relationship ("is a") and a composition relationship ("has a"). Correcting the flaw in this program will be left as an exercise for the student.
-end-