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 those 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 you 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.
Some college professors have made a career of studying data structures and hundreds of books on data structures have been written. This lesson will not attempt to compete in that arena. Rather, this lesson will use three classical types of data structures to illustrate object-oriented programming concepts in Java.
A node, as used in this lesson, is an object that can be used to contain data.
A linked-list is commonly thought of as a data structure consisting of one or more nodes, deposited somewhere in memory, with links connecting each node to the next node. Sometimes, links are also provided to connect each node to the previous node. You can think of the structure as something like a string of beads where each bead contains some data, and they are linked together by the string.
However, the physical locations of the nodes in memory may be very haphazard and not nearly as neat as the physical arrangement of a typical string of beads.
A picture of the locations of the nodes in memory might look something like what you would get if you put the beads on a very long, very flexible string (with a lot of extra string between each pair of beads) and dropped the whole thing on the floor.
The physical arrangement of the beads on the floor would probably be very haphazard, but it would still be possible to find any particular bead by following the string.
Linked lists come in the singly-linked and doubly-linked varieties.
With a singly-linked list, you can only access a node in the middle of the string by starting at the first node and working your way from node-to-node until you get to the one that you want. A singly-linked list is a one-way street and you cannot go backwards in it.
With a doubly-linked list, each node is linked to both the next and the previous nodes so that it is possible to start at either end and work your way toward the other end. A doubly-linked list is a two-way street.
In this lesson, we will confine ourselves to singly-linked lists.
In either case, data in the middle can only be accessed by starting at one of the ends and moving to the desired data on a node-by-node basis. Therefore, a linked-list is not a very good structure for accessing data in a random order. However, it is a good structure for implementing stacks and queues as we will see below.
In this lesson, we will develop a general-purpose singly-linked list from which we can subclass a stack class and a queue class.
Putting data into a stack is commonly referred to as pushing data onto the stack. Retrieving data from a stack is commonly referred to as popping data from the stack. Popping data from a stack physically removes it from the stack. A given data item can only be popped once unless you push it back onto the stack.
The analogy often used for a stack is the stack of trays at a cafeteria. The dishwasher person pushes clean trays onto the top of the stack and customers pop them off.
A linked-list is a reasonably good structure for implementing a stack. To implement a stack with a linked-list, we simply need to attach new nodes to and remove nodes from the same end of the list, thus achieving the LIFO behavior that we need.
The use of a linked-list as the underlying implementation of a stack also provides a good illustration of the benefits of inheritance in object-oriented programming. We will show that once we have developed a class for the linked list, we can subclass that list with only a few lines of code to produce the desired stack class.
Putting data into a queue is commonly referred to as enququeing data and retrieving data from a queue is often referred to as dequeueing data.
The common analogy used for a queue is the checkout line at the supermarket. Assuming that no one "cuts the line", the person who has been in line the longest will be the next person served by the cashier.
A linked-list is also a reasonably good structure for implementing a queue. To implement a queue with a linked-list, we simply need to attach new nodes at one end and remove them from the other end. This provides the FIFO behavior that we need.
As with the stack, the use of a linked-list as the underlying implementation of a queue provides a good illustration of the benefits of inheritance in object-oriented programming. We will show that once we have developed the class for the linked list (the same class used earlier to implement the stack), we can subclass that list with only a few lines of code to produce the desired queue class. Thus, we get two useful data structures with only slightly more effort than is required for one.
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 in the next lesson using an upgraded version of our general-purpose linked list.
Unlike the stack and queue described above, we won't get a lot of advantage here (such as two for the price of one) because the upgraded linked-list required to support the ordered list is much more complex than the one required to support the stack and the queue. Therefore, in this lesson we will develop the simple version. We will upgrade it to the more-complex version in the next lesson.
This general-purpose linked-list is then subclassed to provide two more-specialized data structures:
By the way, let me point out at this time that 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.
Also let me point out that 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.
Our first interesting code fragment is the definition of a new exception class that will be used to instantiate and throw exception objects whenever exceptional conditions arise within the program.
This class extends Exception. This might not be the best place to connect a new exception class into the class hierarchy. I simply connected it there because I didn't want to spend the time and effort required to find the ideal spot to connect it.
Actually, there might already be an exception class in the standard API that would be suitable for this purpose. However, for purposes of illustration, I wanted to include the definition and use of a new exception class because this is something that you should already be familiar with.
This class contains a single instance variable of type String that can be used to encapsulate diagnostic information about the nature of the exceptional condition. While string data is good for human consumption, it isn't very good if you plan for your program to attempt to recover. Therefore, you might want to define a set of numeric symbolic constants to use for diagnostic information instead of using strings for this purpose.
As you can see, the class provides a NoArg constructor as well as a parameterized constructor. The parameterized constructor allows you to instantiate a new object and initialize its instance variable with a string describing the exceptional condition.
It also provides an overridden version of the toString() method
that can be used to display the encapsulated diagnostic information on
the standard output device (or can be used for any other purpose where
a String representation of the exceptional condition might be useful).
class Excep extends Exception{
private 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 parameterized constructor
public String toString(){//override toString()
return diagnosticData;
}//end overridden toString()
}//end class Excep |
Note that the incoming parameter to the constructor is a reference to an object of the generic type Object and it is stored in an instance variable that is a reference variable of type Object.
You should recall that the generic type Object can be used as the type for a reference variable that refers to an object of any type in Java. In this particular program, we tested the data structures using objects of a class named TestClass. The definition of TestClass can be found in the program listing near the end of this lesson.
This Node class contains two instance variables, both of which refer to objects that (may) exist somewhere else in memory (a reference variable with a value of null doesn't refer to an object). The first instance variable named dataObj is used to refer to the data object passed in as a parameter to the constructor for the node.
The second instance variable is a reference to an object of the Node type (this sometimes leads to a description of classes of this type as self-referential classes) which will later be used to refer to the next node in the linked-list. In other words, this reference variable can refer to an object of the same type as the object that contains the reference variable.
Even though this reference variable doesn't initially refer to an object
(and therefore should contain null), it is not explicitly initialized
to null. Instance variables in java (which are references to objects)
are automatically initialized to null if you don't explicitly assign
them to an object when you instantiate the object that contains the instance
variable.
class Node{
Object dataObj;//ref to data object is stored here
Node nextNode;//ref to the next node in the RawList
public Node(Object dataObj){//constructor
this.dataObj = dataObj;
}//end constructor
}//end class Node |
If the new node is attached to the front of the list, this reference variable will be assigned a reference to the node that was previously the first node in the list.
Another thing to notice is the use of the this reference in the constructor to refer to the object being constructed. Hopefully you completely understand the concept of the this reference. In particular, note that the this reference is used in this case to differentiate between an instance variable of the class and a method parameter to the constructor that has the same name, dataObj.
These are important concepts. Make certain that you understand them before going on.
The next interesting code fragment is the class used to manage the list, named RawList. This is a large class containing several methods, so we will discuss this class in parts.
You might think of an object of the RawList class as being a manager object. In particular, an object of this class contains the methods necessary to manage the linking of objects of the Node class in such a way as to maintain a linked list of those objects.
We will begin our discussion with the instance variables of the RawList class.
There are two instance variables in an object of this class, both of which are references to objects of type Node. When an object of this class is instantiated, these two instance variables are automatically initialized to null.
In operation, these two variables refer to the first node in
the list and the last node in the list. Therefore, at any point
in time, the manager object knows where the list starts, and where
it ends. However, except for the trivial case of a list containing only
one object, the manager object has no knowledge of how the list
snakes through memory (recall the image of the string of beads laying on
the floor in a haphazard fashion with lots of string between the individual
beads).
class RawList{
private Node firstNode; //reference to first node
private Node lastNode; //reference to last node |
Because the two instance variables are automatically initialized to null, which is the desired state for a RawList object with no nodes to manage, this class doesn't need an explicit constructor definition.
The method in the next code fragment is used to instantiate a new object of type Node and to encapsulate in that object a reference to another object somewhere in memory that contains the data for the node. This method returns a reference to the new node.
By now you may be thinking that a linked list in Java consists of a network of references, and if so, you are probably correct in your thinking. Somewhere in memory there is some data, and that data is accessible by traversing the references that link things together. Sometimes the code required to traverse the links can be rather complicated (as we will see in the ordered list example in the next lesson).
This method is invoked by other methods in our program that need to
create new nodes and attach them to the front or the back of our linked
list. Since it is a utility method that is not needed outside the class,
it was made private.
private Node getNode( Object dataObj) {
Node newNode = new Node(dataObj);
return newNode;
}//end getNode() |
This method tests for that condition and returns true if empty,
and false if not empty. Obviously it wouldn't be difficult to make
this inline code whenever it is needed, but the use of the method with
the descriptive name causes the code to be more self-documenting.
boolean isEmpty(){
return firstNode == null;//return true if empty
}//end isEmpty() |
Note that it receives an incoming data object as the generic type Object so it can accommodate any type of object.
A call is made to the method discussed above named getNode() to get a new node and to encapsulate the reference to the actual data object in that node. The method named getNode() returns a reference to the new Node object which is saved in a local variable named newNode.
Following this, the method must attach the new node to the front of the list. For the case of an empty list, this is a trivial operation. The list is tested for empty, and if it is empty, the reference to the new node is assigned to the instance variables of the RawList object named firstNode and lastNode. In this case, the new node becomes both the first and the last node in the list.
If the list is not empty, some rewiring of the references is required. (You need to get used to this rewiring because it becomes more complicated as we go on, particularly in the lesson on the ordered list.)
In this case, we need to cause the instance variable named nextNode
of the new Node object to refer to the object that was previously
the first node in the list. A reference to this object can be obtained
from the instance variable of the RawList object named firstNode.
So we obtain that reference and assign it to newNode.nextNode.
void toFront(Object dataObj){
Node newNode = this.getNode(dataObj);
if(this.isEmpty()) //RawList is empty
firstNode = lastNode = newNode;
else{ //RawList is not empty
newNode.nextNode = firstNode;
firstNode = newNode;
}//end if
}//end toFront() |
On top of all that, the new object of type Node that we are referring to contains a reference variable that refers to another object somewhere in memory that contains our data (possibly involving some more indirection handled by the virtual machine that we don't need to worry about).
It gets much worse. If you are uncomfortable with indirection, perhaps you might consider a career in Pascal programming (but not ObjectPascal, because that may be almost as bad).
After we accomplish all of the above, we need to assign a reference to the new node to the reference variable named firstNode in order to cause the new node to become the first node in the list.
The next interesting code fragment is the method that attaches a new node to the back of the list. The operation is very similar to the previous method. The primary difference is that in this case, we need to cause reference variables in both the last node in the list and in the RawList object to refer to the new node object. So, we assign a reference to the new node to both lastNode.nextNode and lastNode.
The nextNode reference variable in the new node was set to null when the object was instantiated so we don't need to do anything with it in this case. It already has the required value for the last node in the list.
Note that in this method and the previous method, the order in which
we assign references is critical to proper operation of the program. We
don't want to be standing on a limb and saw the limb off between our feet
and the trunk of the tree, which is just about what we will do if we don't
do the rewiring in the correct order.
void toBack(Object dataObj){
Node newNode = this.getNode(dataObj);
if(this.isEmpty()) //RawList is empty
firstNode = lastNode = newNode;
else { //RawList is not empty
lastNode.nextNode = newNode;
lastNode = newNode;
}//end if
}//end toBack() |
To begin with, note that this method throws an exception of type Excep, and this happens if the method is invoked on an empty list. We leave decisions regarding what to do about the problem to the application program that is using this class. We simply throw an exception to notify the application program of the problem.
Once we determine that the list is not empty, we declare a reference variable of type Node and initialize it with a reference to the first node in the list. We will use this variable to return the reference to the data object when the method terminates.
Recall that in Java, the garbage collector does not reclaim objects until all references to those objects either cease to exist, or are set to null. In this case, even though we are going to remove the node object from the list, the data object will continue to exist and be accessible through the reference that we are going to return to the calling method. The data object will cease to exist only when the calling method ceases to refer to it with an active reference variable.
Note however, that the node object will become eligible for garbage collection as soon as the method terminates because there will no longer any active references to that object.
Having disposed of the trivial case of an empty list, we need to also
consider another almost-trivial case: a list having only one node.
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() |
That takes care of the trivial cases. Having determined that there are at least two nodes in the list, we need to do some rewiring.
In this case, we need to cause firstNode to refer to the second node in the list (because we need to remove the first node in the list). We can obtain a reference to the second node as firstNode.nextNode. (Hopefully all this indirection is making sense to you at this point. If not, you might need to review some of the material in the introductory course.)
Once we cause firstNode to refer to the second node in the list, the second node becomes the first node, the previous first node is no longer a part of the list, and our job is almost complete.
However, we must return a reference to the data object encapsulated in the Node object that was removed, and we do so by returning tempRefToNode.dataObj that we discussed earlier.
What we actually return is a copy of the reference to the data object, but that is OK. If a burglar has your address or a copy of your address, he or she can still find your house to burglarize.
So even though we return a copy of the reference to the data object, the calling method can use the copy to access the object. Also, the existence of the copy of the reference is sufficient to keep the garbage collector at bay for a little longer because we still have an active reference to the data object.
However, once this method terminates, there are no more active references to the Node object that was removed from the list, so the Node object becomes eligible for garbage collection.
If this discussion of garbage collection sounds like just so much garbage to you, consider going back and reviewing the material on garbage collection in the introductory course.
You might also want to take a look at the on-line book, Thinking in Java, by Bruce Eckel which, as of this writing on 12/17/97 is available for free downloading at www.eckelobjects.com. Eckel has a lot to say about garbage collection and related matters.
Because our linked list is a singly-linked list and is therefore a one-way street, removal of a node from the back of the list is more complex than removal from the front. In fact, it is so complex and inefficient that we are going to avoid using it when we subclass the linked list to create our stack and queue classes. However, since this program is here primarily to illustrate important programming concepts, we will discuss a method for removing an object from the back of the list.
Before getting into that degree of complexity, lets take a look at another method which is more complex than anything that we have seen so far, but not quite as complex as removing an object from the back of the list.
The following method named printRawList() is used to traverse the list from front to back and to display the contents of the data objects encapsulated in the individual nodes.
Again we have the trivial case of the empty list where we simply display the string "Empty" and terminate the method.
Once we decide that the list is not empty, we need to execute the code to traverse the list, one node at a time, and display what we find there.
People who write books on data structures often talk about iterators. In a nutshell, an iterator provides the capability to traverse all the nodes in a data structure and take some specific action at each node (such as squaring the value stored in the node, or displaying that value).
Usually the design of iterators makes it possible for the iterator method to make a call to another user-specified method when it arrives at a node so that the user can design the desired behavior into that user-specified method.
In a crude sense, our method for printing the contents of the nodes in our list is an extremely simple iterator. However, it does not provide the ability for the user to define the behavior at each node. Rather, that behavior is hard-coded into the method. (Some data-structures authors might object to referring to this as an iterator, even an extremely simple one.)
In any event, whatever we choose to call it, the method named printRawList
has the ability to traverse the list from front to back and to display
the contents of each data object referred to by the reference variable
named dataObj that is encapsulated in each Node 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() |
To accomplish this, we declare a local reference variable of type Node named currentRefToNode and initialize it to refer to the first node in the list.
We then drop into a while loop which will terminate when the value of currentRefToNode becomes null.
While we are in the loop, we use the currentRefToNode to extract a reference to the data object that is stored in the instance variable named dataObj.
We use the overloaded concatenation form of the "+" operator to convert our data object to a String object and pass that String object to the println() method.
We have overridden the toString() method in the definition of the class from which our data object was instantiated, so this causes the data object to be converted to a String object according to our specifications (otherwise the concatenation operator would cause it to be converted to a String object according to some default specification). The String object is then passed to the println() method that displays it on the standard output device.
If it is not absolutely clear to you what is happening here, you will need to go back and review some of the material in the introductory course.
The last thing that we do inside the loop (before returning to the top of the loop and testing the conditional expression again) is to update the conditional variable (currentRefToNode) to cause it to contain the value of the reference variable named nextNode in the current node.
The reference variable named nextNode in the last node in the list contains a value of null. When we finish displaying the data in the last node and perform this update, we will assign a value of null to currentRefToNode causing the loop to terminate when the conditional expression in the while loop is next evaluated.
Well, that brings us to the most complicated method in our program: a method named fetchFromBack() that removes a node from the back of the list and returns a reference to the data object encapsulated in that node.
In a nutshell, what we have to do is start at the front of the list and walk the nodes until we reach the next-to-last node. While standing on the next-to-last node, we cut the wires that attach the node we are standing on to the last node.
This method starts out like previous methods; by testing to see if the list is empty, and throwing an exception if it is empty.
If the list is not empty, a test is made to see if there is only one node, and if so, we simply set firstNode and lastNode to null and return a reference to the data object encapsulated in the node that occupied the list prior to that action.
Things begin to get interesting when it is determined that the list is not empty and it contains more than one node.
Here we create another reference variable and point it at the first node, giving us two local working variables.
One variable refers to the first node. We will use it as a working variable to traverse the list.
The other variable refers to the last node. We will save it to use at
the end of the method when we return the reference to the data object encapsulated
in the last node.
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;
while(currentRefToNode.nextNode != lastNode)
currentRefToNode = currentRefToNode.nextNode;
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() |
(currentRefToNode.nextNode != lastNode) |
When the while loop terminates, we need to cut the last node loose and set the nextNode reference in the current node to null to indicate that it is now the last node in the list.
We cut the last node loose by setting lastNode to refer to the next-to-the-last node. This reference is contained in the variable named currentRefToNode.
We then set the nextNode reference variable in the node referred to by currentRefToNode to null causing it to be the last node insofar as some of our algorithms are concerned.
All we have left to do at this point is to return a reference to the data object encapsulated in the node that we just finished cutting loose.
A reference to this node is stored in the reference variable named tempRefToNode,
so we use that reference variable to access and return a reference to the
data object using the following syntax:
return tempRefToNode.dataObj; |
In this program we have illustrated two different ways to detect the end of the list. One way is to use the null reference and the other is to use the reference stored in the reference variable named lastNode. This latter approach is more self-documenting and slightly less complicated.
That brings us to the end of the class definition for the class named RawList. We now have a class that defines a general-purpose linked-list class that we can use for a variety of purposes.
In this lesson, we are going to use the RawList class for two purposes. In particular, we will extend this class into two new classes. One of the new classes can be used to instantiate objects that exhibit the LIFO behavior of a stack. The other can be used to instantiate objects that exhibit the FIFO behavior of a queue.
It is very important to note that these are completely general data structures insofar as the type of data that they can accommodate is concerned (as long as the data is object data).
Objects of any type (including mixed types) can be accommodated by these structures. If you need to use them to accommodate the primitive types, such as int, you can use the wrapper classes to turn those primitive variables into objects. Hopefully you remember what the wrapper classes are.
The next code fragment is the class that extends the RawList class to produce a queue class named MyQueue. This class subclasses the class named RawList in such a way as to provide queue behavior for objects instantiated from the class.. A queue is a FIFO structure. FIFO behavior 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. Except for the class header line and the required method signatures, there are only four lines of code in the entire class definition. Those four lines of code invoke the methods of the RawList class on a selective basis to provide methods to enqueue, and dequeue objects, to print the contents of the queue, and to inquire if the queue is empty.
As an exercise for the student, explain why we elected to add to the back and remove from the front instead of adding to the front and removing from the back. Either approach would have provided the required FIFO behavior.
Again, note that this class works exclusively with objects of the generic
type Object, and can therefore accommodate objects of any type,
or possibly of mixed types.
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 |
As with the queue class, exclusive of class header and method signatures, only four lines of code were required to give us the ability to push and pop objects, to display the objects, and to inquire if the stack is empty.
Again, the class works exclusively with objects of the generic type
Object meaning that it will accommodate objects of any type.
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{
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 |
In the next lesson, we will add more methods to the RawList class to make it suitable for extending it into an ordered list class. This class can be used to instantiate ordered list objects which will manage a list of other objects in an ordered fashion.
That will be a fairly complex programming task, but will be a good illustration of additional programming concepts such as the use of interface types and the oft-used requirement to cast objects of type Object into specific types in order to access their instance members..
/*File List02.java
Copyright 1997, R.G.Baldwin
This program develops a general-purpose linked-list that
supports the addition and removal of new nodes at either
the front or the back.
This general-purpose linked-list is then subclassed to
provide two more-specialized data structures:
Queue
Stack
In all cases, the data structures so produced operate
with objects of the generic type Object.
The output from running this program is shown below:
//------------------------------------------
Test the unordered list
Put some data objects in the unordered list
The unordered list contains:
One
Two
Three
Four
Remove data objects from the unordered list
Removed One
Removed Four
Removed Two
The unordered list now contains:
Three
Removed Three
The unordered list now contains:
Empty
Remove another object from the unordered list
Exception: Empty list in fetchFromFront
Test the queue
Put some data objects in the queue
The queue contains:
One
Two
Three
Four
Try to remove 5 data objects from the queue
Dequeued One
Dequeued Two
Dequeued Three
Dequeued Four
Exception: Empty list in fetchFromFront
Test the stack
Push some data objects on the Stack
The stack contains:
Four
Three
Two
One
Try to pop 5 data objects from the Stack
popped Four
popped Three
popped Two
popped One
Exception: Empty list in fetchFromFront
End of test
//------------------------------------------
This program was tested using JDK 1.1.3 under Win95.
**********************************************************/
import java.awt.*;
import java.awt.event.*;
import java.util.*;
//=======================================================//
class TestClass{
//This class is used to test the data structures.
//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()
//-----------------------------------------------------//
}//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 List02{//controlling class
public static void main(String[] args){//main
List02 obj = new List02();//instantiate this object
obj.test();//invoke the method named test()
}//end main
//-----------------------------------------------------//
void test(){
System.out.println("Test the unordered list");
RawList theList = new RawList();//instantiate list obj
System.out.println(
"Put some data objects in the unordered list");
theList.toFront(new TestClass("Two"));
theList.toBack(new TestClass("Three"));
theList.toFront(new TestClass("One"));
theList.toBack(new TestClass("Four"));
System.out.println("The unordered list contains:");
theList.printRawList();
System.out.println(
"\nRemove data objects from the unordered list");
try{//because an exception of type Excep can be thrown
System.out.println("Removed "
+ theList.fetchFromFront());
System.out.println("Removed "
+ theList.fetchFromBack());
System.out.println("Removed "
+ theList.fetchFromFront());
System.out.println(
"The unordered list now contains:");
theList.printRawList();
System.out.println("Removed "
+ theList.fetchFromBack());
System.out.println(
"The unordered list now contains:");
theList.printRawList();
System.out.println(
"Remove another object from the unordered list");
System.out.println("Removed "
+ theList.fetchFromFront());
}catch(Excep e){System.out.println("Exception: " + e);}
System.out.println("\nTest the queue");
//instantiate a MyQueue object
MyQueue theQueue = new MyQueue();
System.out.println(
"Put some data objects in the queue");
theQueue.enqueue(new TestClass("One"));
theQueue.enqueue(new TestClass("Two"));
theQueue.enqueue(new TestClass("Three"));
theQueue.enqueue(new TestClass("Four"));
System.out.println("The queue contains:");
theQueue.printQueue();
System.out.println(
"\nTry to remove 5 data objects from the queue");
try{
for(int cnt = 0; cnt < 5; cnt++)
System.out.println("Dequeued "
+ theQueue.dequeue());
}catch(Excep e){System.out.println("Exception: " + e);}
System.out.println("\nTest the stack");
//instantiate a MyStack object
MyStack theStack = new MyStack();
System.out.println(
"Push some data objects on the Stack");
theStack.push(new TestClass("One"));
theStack.push(new TestClass("Two"));
theStack.push(new TestClass("Three"));
theStack.push(new TestClass("Four"));
System.out.println("The stack contains:");
theStack.printStack();
System.out.println(
"\nTry to pop 5 data objects from the Stack");
try{
for(int cnt = 0; cnt < 5; cnt++)
System.out.println("popped " + theStack.pop());
}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{
private 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 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
//=======================================================// |
| C++ has a way of dealing with this situation involving a second-level specification of access control at the inheritance interface. However, that capability does not exist in Java. |
Once you do this, the code in the methods of MyQueue and MyStack have access to the methods of the RawList object, but those methods are hidden from code outside the two classes. This requires minimal modifications to the program code, and will be left as an exercise for the student.
The hard way assumes that for some reason, you need to continue to extend RawList into MyQueue and MyStack (to maintain the "is a" relationship). In this case, you can override the methods of the RawList class in the subclasses and cause an exception to be thrown whenever the overridden versions of those methods are accessed. Then in order to make these methods available to the code in the subclasses, you can invoke those methods using the super keyword ahead of the method invocation. This will cause the superclass version, as opposed to the overridden version to be invoked. This involves considerably more modifications to the program code, and will also be left as an exercise for the student.
-end-