You are all familiar with the use of arrays to keep a set of elements in memory. There are many good things about arrays--they allow us to randomly access cells, thats vital in some applications, addressing cells is also easy since each cell has a nice numeric address and each comes after the other. There are applications where we need dynamic space allocation and that is why we introduce you to linked lists.
Here are few reasons for why arrays might not meet our storage needs perfectly:
Linked lists can be implemented with arrays, but typically in languages like Java that support dynamic allocation, they are not. You can create cells as you need them, and can remove them when you wish. But, you don't have a nice numeric address like you do with arrays. The address of cells are NOT in sequence nicely like they are in arrays, in fact, we don't refer to them as cells, we call them nodes. You have to get each element of the sequence to remember the address of the next. In the object oriented paradigm, we say that each node keeps a reference to the next node. sometimes, we design our nodes to even keep a reference to a previous node, we refer to linked lists with such nodes as doublely-linked lists. Other times we design the linked list, so that the last node points to the first one. Such linked lists are referred to as circular linked lists. Linked lists are a tremendous asset. We add nodes as we need to, we can put a node between two other nodes by changing their references. In java, we can delete a node by simply making their previous node reference their next node, if we have a doublely linked list, their next node will now reference their previous node also. Java's Garbage Collector will collect any space that is left unreferenced. So, by simply not referencing a node we have effectively deleted it. Lets look dynamicQueue implementation of Queue as an example.
This example will help us see how such implementation can allow our
data structure to grow and shrink as it needs to; you gain
flexibility in space allocation when you implement a queue this way.
Let us consider
the dynamic Queue class that implements
the Queue Interface.
First of all, it uses a simple linked list concept to implement a queue.
Two fields are defined for each dynamicQueue object, one to reference to
an object being kept on the queue (element_;) and a second variable
to reference the rest of the queue (rest_). Both variables start
as null so the constructor doesn't have any code.
Just checking element_ should determine if queue is empty. As
you will see Dequeue could return a null reference which should also
be considered in an application.full always returns
false as you can't get full in this implementation.
Lets take a careful look at enqueue and dequeue.
public Queue enqueue(Object x) throws Exception {
if (full())
throw new Exception();
if (element_ == null) //empty queue
element_=x;
else if (rest_==null) { //last element in queue
rest_=new dynamicQueue();
rest_.element_=x;
}
else
rest_=(dynamicQueue)rest_.enqueue(x); //go find the last element
return this;
}
We first check for full which can't happen. Then, we check to see if
we are empty, this only happens in this implementation when we 1st create
our queue. If element_ is empty, we will simply set put the x
in element_. If rest_ is null, we simply create a new
dynamicQueue and place x in the element_ of that queue; keep in
mind that in this case, the rest_ of the new queue will be null
when constructed. If none of the previous conditions are met, this queue
is unable to deal with adding x ad needs to delegate the task its
rest_, this was the statement
rest_= (dynamicQueue)rest_.enqueue(x); accomplishes. The casting
is needed because enqueue returns a Queue and we need to cast it
as what it is, which in this case is a dynamicQueue.
Consider the following list:
q---> jones ---> fair ---> mary ---> leo --->||
Here is what happens when we enqueue mark:
q---> jones ---> fair ---> mary ---> leo --->mark --->||
Let use consider dequeue:
public Queue dequeue() throws Exception {
if (empty())
throw new Exception();
return rest_;
}
We throw an exception if queue is empty, otherwise, by executing return test_; we are effectively saying what used to be in front is no longer in front and the Queue object referenced by rest_ is now in front. What used to be in front is no longer in the queue.
test.java is designed to test either version of queue. As you recall, queue itself is an interface with no implementation of its own. We extended it to have a fixed (array) and a dynamic (linked list) implementation. It is designed so that user can specify a datafile, the version to test, and if necessary, the number of cells for the array in the "fixed" version. This information is taken from the command line. Here are two examples of running this program:
java test test.dat fixed 10 will test the fixed version using test1.dat as the data file. Also, the size 10 is chosen here for the array that keeps the queue elements.
java test test.dat dynamic will test the dynamic version using test.dat as the data file. Notice that no size is specified, as it is not relevant in the dynamic case.
Processing of command line parameters is mostly useful in utility programs, such as, mv and ls. In test.java, it helps to test the different versions queue quickly, without engaging in long dialog with the program to set things up.
In test.java, the main method has an array of strings as a parameter (arg). This array is filled with the space separated strings on the command line that appear after the program name. arg[0] in the examples shown above is test.dat. When looking at the code for this program, you will notice that the file opened for input gets its name from arg[0].
One of the things that I like you to notice is the use of the equals method when trying to figure out which version is being tested. You ask yourself, why couldn't we simply say if (arg[1] == dynamic). The reason is simple, "==" testes equality of the references and not what the objects contain. In other words, we can only find out if arg[1] and dynamic are both referencing the same memory cell.
Note that the declaration of q occurs before we know which kind the user is testing. Recall that you can't make objects of queue, it is an abstract class. Once the program figures out which version is to be tested, either q = new dynamicQueue();, or q = new fixedQueue(size); are used to create the right version of the queue.
Consider the code segment:
while(!q.empty()) {
text = q.dequeue();
System.out.println(text+" was removed from the queue");
}
What if we want to take this out of the main method and put in its own
method, say, named out. It would be invoked from main with a call
like out(q);. Here is the catch, what kind parameter, do you
think, out needs to accept? It needs to be queue,
as you don't know which implementation is used, so how can you use
either of its subclasses. But, this not a problem, as this is
one of the fundamental advantages for Object Orientation which we call
Polymorphism. Here is a look at the out method:
static void out(queue q) {
while(!q.empty()) {
String text = q.dequeue();
System.out.println(text+" was removed from the queue");
}
}