Java Data Structures - Contents
A D V E R T I S E M E N T
The next step up in complexity is a list. Most
people prefer to implement a list as a linked list (and I'll show how to do that later),
but what most people miss, is that lists can also be implemented using arrays. A list has
no particular structure; it just has to allow for the insertion and removal of objects
from both ends, and some way of looking at the middle elements.
A list is kind of a stack combined with a queue;
with additional feature of looking at the middle elements. Preferably, a list should also
contain the current number of elements. Well, lets not just talk about a list, but write
one!
public class pArrayList{
protected Object[] array;
protected int start,end,number;
public pArrayList(int maxsize){
array = new Object[maxsize];
start = end = number = 0;
}
public boolean isEmpty(){
return number == 0;
}
public boolean isFull(){
return number >= array.length;
}
public int size(){
return number;
}
public void insert(Object o){
if(number < array.length){
array[start = (++start % array.length)] = o;
number++;
}
}
public void insertEnd(Object o){
if(number < array.length){
array[end] = o;
end = (--end + array.length) % array.length;
number++;
}
}
public Object remove(){
if(isEmpty())
return null;
number--;
int i = start;
start = (--start + array.length) % array.length;
return array[i];
}
public Object removeEnd(){
if(isEmpty())
return null;
number--;
return array[end = (++end % array.length)];
}
public Object peek(int n){
if(n >= number)
return null;
return array[(end + 1 + n) % array.length];
}
}
The class contains four data elements: array,
start, end, and number. The number is
the number of elements inside the array. The start is the starting pointer,
and the end is the ending pointer inside the array (kind of like
the queue design).
The constructor, pArrayList(), and
methods isEmpty(), isFull(), and size(), are pretty
much self explanatory. The insert() method works exactly the same way as an
equivalent queue method. It just increments the start pointer, does a mod
(the % symbol), and inserts into the resulting position.
The insertEnd(Object) method, first
checks that there is enough space inside the array. It then inserts the
element into the end location. The next trick is to decrement the end
pointer, add the array.length, and do a mod with array.length.
This had the effect of moving the end pointer backwards (as if we had
inserted something at the end).
The Object remove() method works on a
very similar principle. First, it checks to see if there are elements to remove, if not,
it simply returns a null (no Object). It then decrements number.
We're keeping track of this number inside all insertion and removal methods,
so that it always contains the current number of elements. We then create a
temporary variable to hold the current position of the start pointer. After
that, we update the start pointer by first decrementing it, adding array.length
to it, and doing a mod with array.length. This gives the appearance of
removing an element from the front of the list. We later return the position inside the
array, which we've saved earlier inside that temporary variable 'i'.
The Object removeEnd() works similar to
the insert() method. It checks to see if there are elements to remove by
calling isEmpty() method, if there aren't, it returns null. It
then handles the number (number of elements) business, and proceeds with
updating the end pointer. It first increments the end pointer,
and then does a mod with array.length, and returns the resulting position.
Simple?
This next Object peek(int n) method is
the most tricky one. It accepts an integer, and we need to return the number which this
integer is pointing to. This would be no problem if we were using an array
that started at 0, but we're using our own implementation, and the list
doesn't necessarily start at array position 0. We start this by
checking if the parameter 'n' is not greater than the number of
elements, if it is, we return null (since we don't want to go past the bounds
of the array). What we do next is add 'n' (the requesting
number) to an incremented end pointer, and do a mod array.length.
This way, it appears as if this function is referencing the array from 0
(while the actual start is the incremented end pointer).
As I've said previously, the code you write is
useless, unless it's working, so, lets write a test driver to test our list class. To
write the test driver, I've converted that really cool Queue test driver, and added some
features to test out the specifics of lists. Well, here it is:
import java.io.*;
import pArrayList;
class pArrayListTest{
public static void main(String[] args){
pArrayList l = new pArrayList(10);
Integer j = null;
int i;
System.out.println("starting...");
for(i=0;i<5;i++){
j = new Integer((int)(Math.random() * 100));
l.insert(j);
System.out.println("insert: " + j);
}
while(!l.isFull()){
j = new Integer((int)(Math.random() * 100));
l.insertEnd(j);
System.out.println("insertEnd: " + j);
}
for(i=0;i<l.size();i++)
System.out.println("peek "+i+": "+l.peek(i));
for(i=0;i<5;i++)
System.out.println("remove: " + ((Integer)l.remove()));
while(!l.isEmpty())
System.out.println("removeEnd: " + ((Integer)l.removeEnd()));
System.out.println("Done ;-)");
}
}
The test driver is nothing special, it inserts (in
front) five random numbers, and the rest into the back (also five). It then prints out the
entire list by calling peek() inside a for loop. It then
continues with the removal (from front) of five numbers, and later removing the rest (also
five). At the end, the program prints "Done" with a cute smiley face ;-)
The output from this test driver is given below. I
suggest you examine it thoroughly, and make sure you understand what's going on inside
this data structure.
starting...
insert: 14
insert: 72
insert: 71
insert: 11
insert: 27
insertEnd: 28
insertEnd: 67
insertEnd: 36
insertEnd: 19
insertEnd: 45
peek 0: 45
peek 1: 19
peek 2: 36
peek 3: 67
peek 4: 28
peek 5: 14
peek 6: 72
peek 7: 71
peek 8: 11
peek 9: 27
remove: 27
remove: 11
remove: 71
remove: 72
remove: 14
removeEnd: 45
removeEnd: 19
removeEnd: 36
removeEnd: 67
removeEnd: 28
Done ;-)
Well, if you really understand everything up to this
point, there is nothing new anybody can teach you about arrays (since you know all the
basics). There are however public tools available to simplify your life. Some are good,
some are bad, but one that definitely deserves to have a look at is the java.util.Vector
class; and that's what the next section is about!
Back to Table of Contents
A D V E R T I S E M E N T
|
Subscribe to SourceCodesWorld - Techies Talk |
| 
Add to Favorites
Make Home Page
