C# Data Structures
  home | services | products | resources | forum
 
about us | contact   
Particle
March 27th, 2017



www.theparticle.com
Main
Services
Products
Resources
Forum
About Us
Contact

Particle Revelation
Hardware Destruction
Quotes
Humor [alpha]
Murphy's Laws

Programming
Java
Java Data Structures
C# Data Structures
Database Design
Graphics Tutorial
Artificial Intelligence

Downloads
SQLRunner
Graphics Tutorials
Hacking Tutorials
Java Applets
MIDI Music
Gov & Misc Docs

Games
Chess Game
Asteroids
Tic-Tac-Toe
Tetris

Applets
DRAW!
FlightBox
pWobble 3D
pRunner
NYU HWs
Swarms
Geometry
Chaos
Machine Learning

Academic
CISC 751[02]X
Networks (old)
OS (old)
AI (old)
App Dev (old)
C++ (old)
OOP (old)
Web (old)
Perl (old)
DBMS (old)
Perl (old)
ProgLangs (old)
PHP (old)
MltMedia (old)
Oracle (old)

Misc
Privacy Policy
Publications
profphreak.com



C# Data Structures (beta)

© 2002, Particle

[Note, this is mostly a copy of Java Data Structures]

Introduction...

Welcome to C# Data Structures! C# (pronounced C-Sharp) is a new language created by Microsoft for their .NET Framework. It has been standardized by ECMA (http://www.ecma.ch) and is well on its way of becoming a mainstream programming language.

C# has similar syntax to both C/C++ and Java, and is generally quite easy to learn (if you know any of the above). Like Java, it also comes with a free compiler, but from Microsoft, which you can download from their website (just download .NET Framework SDK). It is also part of Visual Studio .NET.

This document was created to expose the world of Data Structures to software developers. Programming doesn't involve C/C++, C# or Java; it involves data structures, algorithms, and other high level concepts. Knowing these basics will allow you to be a great programmer in any language. So, while examples will be implemented in C#, this document should be considered a Data Structures tutorial rather than a C# tutorial.

This is a growing document; as new features are added to the language, new techniques are discovered or realized, this document shall be updated to try to accommodate them all. If you have suggestions, or requests, (or spelling/grammar errors) just e-mail them, and I'll try to add the suggested items into the subsequent releases.

Of course, this document is free, and I intend to keep it that way. Selling of this document is NOT permitted. You WILL go to hell if you do (trust me). (Not that anybody would want to buy it...) You may distribute this document (in any form), provided you don't change it. (Yes, you CAN include it in a book provided you notify me and give me credit [and one free copy of the book])

I take no responsibility for ANYTHING. I am only responsible for all the good things you like about the article.

Before Starting...

Before starting however, you need to be a bit familiar with the general syntax of C#. It would also help if you know some other programming language. The ECMA website has a complete C# Language Specification (Standard ECMA-334, December 2001) In any case, if you find this material hard to follow, go read a startup book, but if everything is clear, you're in good shape.

How to Compile and Run C# Programs...

C# programs are simply text files with C# source code in them. All the examples in this document can be compiled by placing them in a text file. The file needs to have a .cs extension. Once that is done, you're ready to compile it. For example, let's say you have a Hello.cs file, you'd compile it by doing:

csc Hello.cs

This command compiles the file, and creates a file named Hello.exe. This Hello.exe is your compiled output. You cannot really call it an executable, because it is not directly executed by your computer, but by a Virtual Machine. However, that step is usually hidden, so if everything is setup correctly, all you need to do is simply run the executable:

Hello.exe

This will run the code that is part of the Hello file (starting with the Main() method). There are many other more advanced features of the process, and we will mention them as we come upon them. Refer to the .NET Framework Documentation if you're having problems with these steps.

Although this document should be read in sequence, it is divided into several major sections, here they are:

Variables

Arrays
Array Stack
Array Queue
Array List

Contact Info


Variables...

Variables are the key to any program. There are variables called registers inside every CPU (Central Processing Unit). Every program ever written uses some form of variables. Believe it or not, the way you use variables can significantly impact your program. This section is a very simple introduction to what variables are, and how they're used in programs.

Usually, a variable implies a memory location to hold one instance of one specific type. What this means is that if there is an integer variable, it can only hold one integer, and if there is a character variable, it can only hold one character.

There can be many different types of variables, including of your own type. A sample declaration for different variable types is given below.

bool t;
byte b;
char c;
int i;
long l;

I believe the above is straight forward, and doesn't need much explanation. Variable 't' is declared as bool (true/false) type, and 'b' as of byte type, etc.

The above variables are what are known as simple value types in C#. Simple types in C# are quite different from primitive types in Java or C/C++. In fact, they are themselves structures and keywords like int are just aliases to structures like System.Int32. This means that in a sense, simple types are objects.

The other types of variables are instances of classes or objects. An object is an instance of a class. Your C# programs consist of classes, in which you manipulate objects, and make the whole program do what you want. This concept will be familiar to you if you've ever programmed C++ or Java, if not, think of objects as structures. An example of a simple class would be:

/**
 * simple object definition
 */
class pSimpleObject{

    // define a single int property
    int i;

    /**
     * constructor initializes i to 0
     */
    public pSimpleObject(){
        i = 0;
    }

    /**
     * accessor method for i
     */
    public int get(){
        return i;
    }

    /**
     * mutator (change) method for i
     */
    public void set(int n){
        i = n;
    }
}

You can compile this code via:

csc /t:library pSimpleObject.cs

This creates pSimpleObject.dll. We need to compile it as a library because we did not specify the Main() method (the entry point) for our program. All we have is a class, not a program.

As you can see, the definition of a class is rather straight forward. We give the class its name, which in this case is pSimpleObject. Inside the class, we have an integer named 'i', and three functions. The first function named pSimpleObject(), is the constructor. It is called every time an object is created using this class. The set() and get() functions set and get the value of 'i' respectively. One useful terminology is that functions in objects are not called functions, they're called methods. So, to refer to function set(), you'd say "method set()." That's all there is to objects! Kind of.

The way you declare a variable, or in this case, an object of that class, is:

pSimpleObject myObject;
myObject = new pSimpleObject();

or

pSimpleObject myObject = new pSimpleObject();

The first example illustrates how you declare an object named myObject, of class pSimpleObject, and later instantiate it (a process of actual creation, where it calls the object's constructor method). The second approach illustrates that it all can be done in one line. The object does not get created when you just declare it; it is only created when you do a new on it.

If you're familiar with C/C++/Java, think of objects as pointers or references. First, you declare it, and then you allocate a new object to that pointer.

There is actually quite a bit more to C# types that we haven't covered. Briefly, there are two major type systems, the value types and reference types. Value types include simple types, enum types, and struct types. Reference types include class types, interface types, delegate types, and array types.

Using variables is really cool, and useful, but sometimes we'd like to have more. Like the ability to work with hundreds or maybe thousands of variables at the same time. And here's where our next section starts, the Arrays!


Arrays...

One of the most basic data structures is an array. An array is just a number of items, of same type, stored in linear order, one after another. Arrays have a set limit on their size; they can't grow beyond that limit. Arrays usually tend to be easier to work with and generally more efficient than other structural approaches to organizing data; way better than a no formal structure approach.

For example, let's say you wanted to have 100 numbers. You can always resort to having 100 different variables, but that would be a pain. Instead, you can use the clean notation of an array to create, and later manipulate those 100 numbers. For example, to create an array to hold 100 numbers you would do something like this:

int[] myArray;
myArray = new int[100];

or

int[] myArray = new int[100];

The three notations above do exactly the same thing. The first declares an array, and then it creates an array by doing a new. The second example shows that it can all be one in one line.

Working with arrays is also simple, think of them as just a line of variables, we can address the 5th element (counting from 0, so, it's actually the 6th element) by simply doing:

int i = myArray[5];

The code above will set integer 'i' to the value of the 5th (counting from 0) element of the array. Similarly, we can set an array value. For example, to set the 50th element (counting from 0), to the value of 'i' we'd do something like:

myArray[50] = i;

As you can see, arrays are fairly simple. The best and most convenient way to manipulate arrays is using loops. For example, let's say we wanted to make an array from 1 to 100, to hold numbers from 1 to 100 respectively and later add seven to every element inside that array. This can be done very easily using two loops. (Actually, it can be done in one loop, but I am trying to separate the problem into two.)

int i;
for(i=0;i<100;i++)
    myArray[i] = i;
for(i=0;i<100;i++)
    myArray[i] = myArray[i] + 7;

In C#, just as in Java, we don't need to remember the size of the array as in C/C++. Here, we have the Length variable in every array, and we can check its length whenever we need it. So to print out any array named: myArray, we'd do something like:

for(int i=0;i<myArray.Length;i++)
    System.Console.WriteLine(myArray[i]);

One of the major limitations on arrays is that they're fixed in size. They can't grow or shrink according to need. If you have an array of 100 max elements, it will not be able to store 101 elements. Similarly, if you have fewer elements, then the unused space is being wasted (doing nothing).

Multi-Dimensional arrays are also possible, however, there are 2 versions supported by C#: Plain arrays and jagged arrays.

Plain multi-dimensional arrays are what you'd expect if you're coming from a C/C++ background. When you declare an array, you're declaring a box in memory to be used as that array. These arrays are declared by:

int[] a1;     // single-dimensional array of int
int[,] a2;    // 2-dimensional array of int
int[,,] a3;   // 3-dimensional array of int

To actually create these arrays, you'd do this:

int[] a1 = new int[] {1, 2, 3};
int[,] a2 = new int[,] {{1, 2, 3}, {4, 5, 6}};
int[,,] a3 = new int[10, 20, 30];

Note that the size of the array can be calculated by multiplying the dimensions. For example, the size of 'a3' array is 10 * 20 * 30 or 6000. We know there are this many places in the array.

The second type of array is jagged arrays. These are what you'd expect if you come from a Java background. These are basically one dimensional array that has other arrays as its elements. They are declared like this:

int[][] j2;     // "jagged" array: array of (array of int)
int[][][] j3;   // array of (array of (array of int))

These are created via:

int[][] j2 = new int[3][];
j2[0] = new int[] {1, 2, 3};
j2[1] = new int[] {1, 2, 3, 4, 5, 6};
j2[2] = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9};

Notice that the array elements are themselves arrays. That's the key here. These arrays are different from Java ones though. You cannot create the entire jagged array in 1 step, for example, the below code would fail:

int[][] j2 = new int[3][3];        // bad code

There are a few other things about arrays and types in general, but I believe we've covered all the basics. If you need a more thorough description, refer to the C# Language Speciation.

Arrays are powerful storage constructs. Sometimes, however, we'd like to have more than just a plain vanilla array.


Array Stack...

The next and more serious data structure we'll examine is the Stack. A stack is a FILO (First In, Last Out), structure [or LIFO - as some of my students corrected me]. For now, we'll just deal with the array representation of the stack. Knowing that we'll be using an array, we automatically think of the fact that our stack has to have a maximum size.

A stack has only one point where data enters or leaves. We can't insert or remove elements into or from the middle of the stack. The only methods we can provide are push(...), pop(), and isEmpty().

Before moving on, I'd like to say a word or two about my naming convention. More often than not, my naming convention is very Java like, where variables and methods start with a lower case letter. This is very uncommon in the Windows programming world (and thus, also very uncommon in the C# world, where even Java's toString() method has been turned into ToString() for no apparent reason). [yet totally unlike Microsoft, they turned String into string (so the ToString() method returns a string not a String :-)]

With that, let us move on, and write a stack object that implements the abstract type stack.

/**
 * Array implementation of a stack.
 */
public class pArrayStack {

    // declare some properties
    protected object[] data;
    protected int pointer;

    /**
     * construct a new stack given the capacity
     */
    public pArrayStack(int capacity){

        // initialize data array with given capacity
        data = new object[capacity];

        // start with an empty stack
        pointer = 0;
    }

    /**
     * check whether this stack is empty
     */
    public bool isEmpty(){
        return pointer == 0;
    }

    /**
     * push an object onto the stack
     */
    public void push(object o){

        // check if there is enough space
        if(pointer < data.Length)
            data[pointer++] = o;
    }

    /**
     * pop an object from the stack
     */
    public object pop(){

        // check if stack is empty
        if(isEmpty())
            return null;

        // get object to be returned
        object o = data[--pointer];

        // null out memory location
        data[pointer] = null;

        // return object we got
        return o;
    }
}

As you can see, that's the stack class. The constructor named pArrayStack() accepts an integer. That integer is to initialize the stack to that specific size. If you attempt to push() more integers onto the stack than this capacity, it won't work.

This code is not a program. It is simply a data structure: a library. We thus need to compile it as a library.

csc /t:library pArrayStack.cs

The procedure creates a pArrayStack.dll file, which is a Dynamic Link Library of our code.

We are not coding until we are done testing, so, lets write a test driver class to test this stack.

using System;

/**
 * array stack test class; just runs a few
 * simple iterations on the array stack.
 */
public class pArrayStackTest {

    /**
     * main method to test the stack
     */
    public static void Main(){

        // create a stack with maximum capacity 10
        pArrayStack stack = new pArrayStack(10);

        // push 10 elements onto the stack
        for(int i=0;i<10;i++){

            // make a string "objN" where N ranges 0 to 9
            string objToPush = "obj" + i;

            // display what we're doing
            Console.WriteLine("pushing: {0}",objToPush);

            // push the object on the stack
            stack.push(objToPush);
        }

        // pop all elements from the stack
        while(!stack.isEmpty()){

            // pop an object from the stack
            string objPoped = (string)stack.pop();

            // display what we're doing
            Console.WriteLine("poping: {0}",objPoped);
        }
    }
}

The test driver does nothing special; it inserts ten numbers onto the stack, and then pops them off. Writing to standard output exactly what it's doing. To compile this test driver you need to reference our pArrayStack.dll that we've created earlier.

csc /r:pArrayStack.dll pArrayStackTest.cs

The output, after executing pArrayStackTest.exe is:

pushing: obj0
pushing: obj1
pushing: obj2
pushing: obj3
pushing: obj4
pushing: obj5
pushing: obj6
pushing: obj7
pushing: obj8
pushing: obj9
poping: obj9
poping: obj8
poping: obj7
poping: obj6
poping: obj5
poping: obj4
poping: obj3
poping: obj2
poping: obj1
poping: obj0

As you can see, the first numbers to be pushed on, are the last ones to be popped off; a perfect example of a FILO structure. The output assures us that the stack is working properly.

Another note is in order. In real software development you'd test code a lot more thoroughly than just running through the best case.

Now that you've had a chance to look at the source, let's look at it more closely.

The pArrayStack class is using an array to store its data. The data is of object type, which for C# means it can store anything (simple types like integers, and object types like strings).

There is a C# concept known as boxing and unboxing. Boxing means we 'box' (or wrap) a simple type like 'int' into a reference type like object. For example, we can assign an integer to an object type:

int number = 12345;
object obj = number;

Unboxing is the opposite procedure, returning the object to its original type. For example:

int anotherNumber = (int)obj;

This is precisely the concept that allows our stack to work with any type; something languages like C/C++ and Java are not capable of. [Note: in C++, you can use templates to simulate the effect of any type stack; but that is not quite the same thing - you cannot store various types in a single stack; you can also use void pointers, but that's usually a pain and is not type safe].

Ok, back to the stack...

Because we're using an array with limited size, we need to constantly keep track of the size, so that we don't overflow it; we always look at data.Length to verify that we're not going over the limit.

The second data member is pointer. Pointer, in here, points to the top of the stack. It always has the position which we will use next or 0 if the stack is empty.

The constructor: pArrayStack(), accepts the maximum size parameter to initialize the size of the stack. The rest of the method is just routine initialization. Notice that pointer is initialized to 0, thus making the next position to be filled in an array, 0.

The isEmpty() method is self explanatory, it returns true if the stack is empty (pointer is 0), and false otherwise. The return type is bool.

The push(object) method is fairly easy to understand too. First, it checks to see if the next insertion will not overflow the array. If no danger from overflow, then it inserts. It first inserts, and then increments pointer variable for next insertion. It could easily be modified to actually make the array grow, but then the whole point of "simplicity" of using an array will be lost.

The object pop() function is also very simple. First, it checks to see if stack is not empty, if it is empty, it will return null. In general, this is a really bad error to pop of something from an empty stack. You may want to do something more sensible than simply returning a null (an exception throw would not be a bad choice). I did it this way for the sake of simplicity. Then, it decrements the pointer, and returns the value of the array element pointed to by the decremented pointer. This way, it is ready for the next push or pop.

Before pop() method returns however, it nulls out the array location where it got the object. This is to erase the reference. In C#, object arrays may reference boxed value types (like structures), so it could be the case that by not freeing up (null out) that memory, you're not just wasting 1 reference, but a whole lot of memory which could be freed.

I guess that just about covers it. A stack is a very basic and simple data structure. There are tons of useful algorithms which take advantage of this FILO structure.

And now, without further interruption, we move onto the array relative of Stack: the Queue.


Array Queues...

A queue is a FIFO (First In, First Out) structure. Anything that is inserted first will be the first to leave (kind of like the real world queues - in a super market and such). This is totally the opposite of what a stack is. Although that is true, the queue implementation is quite similar to the stack one. It also involves pointers to specific places inside the array.

The idealized or abstract queue has at least three operations, the isEmpty, inset, and remove. Just as with the stack, there are no methods to access the middle of the queue.

With a queue, we need to maintain two pointers, the start and the end. We determine when the queue is empty if start and end point to the same element. To insert, we add one to the start, and mod (the % operator) with the size of the array. To remove, we'll add one to the end, and mod (the % operator) with the size of the array. Notice that the insert and remove operations are virtually doing the same thing; except while one is setting an element in the array, the other one is returning it.

Sounds simple? Well, let's write it.

/**
 * Array implementation of Queue.
 */
public class pArrayQueue{

    // declare some properties
    protected object[] data;
    protected int start, end;

    /**
     * construct a new queue given the capacity
     */
    public pArrayQueue(int capacity){

        // actual capacity is 1 more than required
        // this makes it easier to detect if queue is full.
        data = new object[capacity + 1];

        // start and end both point to 0 (queue is empty)
        start = end = 0;
    }

    /**
     * check whether this queue is empty
     */
    public bool isEmpty(){

        // a queue is empty if both start and
        // end point to the same location
        return start == end;
    }

    /**
     * insert an object into the queue
     */
    public void insert(object o){

        // get next insert position
        int n = (start + 1) % data.Length;

        // will this insert overflow the queue?
        if(n != end)
            data[start = n] = o;
    }

    /**
     * remove an object from the queue
     */
    public object remove(){

        // check if queue is empty
        if(isEmpty())
            return null;

        // adjust end of queue pointer
        end = (end + 1) % data.Length;

        // get object to be returned
        object o = data[end];

        // null out memory location
        data[end] = null;

        // return object we got
        return o;
    }
}

Well, that's the queue class. In it, we have three variables, the data, the start and the end. Just as with the stack, the queue constructor pArrayQueue(...) initializes the queue's capacity.

The isEmpty() method is self explanatory, it checks to see if start and end are equal, if they are, then the queue is empty.

We allocate capacity + 1 memory in the constructor because this type of queue is full when both start and end point to the same element - which is the same condition for whether the queue is empty or not. Wasting 1 array location enables us to store capacity elements yet still be able to tell if the queue is empty or full. This is not a bad trade off to simplify code that oversees the capacity of the queue.

The insert(object) method, accepts an object as a parameter, checks whether the queue is not full, and inserts it. The insert works by adding one to start, and doing a mod with data.Length (the size of the array), the resulting location is set to the incoming object.

The object remove() method doesn't accept any parameters and returns an object. It first checks if the queue is empty, by calling isEmpty(). If it is, the method returns a null, indicating that there's been an error. This is usually a pretty bad bug inside a program, for it to try to remove something from an empty queue, so, you might want to do something more drastic in such a situation (like an exception throw).

The method continues by removing the end object from the queue. The removal is done in the same way insertion was done: by adding one to the end, and mod-ing it with data.Length (array size). The object where end point is returned.

Before remove method returns however, it nulls out the array location where it got the object. This is to erase the reference. Refer to the Array Stack section for a short explanation why this is important in C#.

There are other implementations of the array queue; a little re-arrangement can make several if() statements disappear. The reason it's like this is because it's pretty easy to think of it. Upon insertion, you add one to start and mod, and upon removal, you add one to end and mod... easy? The end always follows the start.

Well, now that we know how it works, let's actually test it! I've modified that pretty cool test driver from the stack example, and got it ready for this queue, so, here it comes:

using System;

/**
 * array queue test class; just runs a few
 * simple iterations on the array queue.
 */
public class pArrayQueueTest {

    /**
     * main method to test the queue
     */
    public static void Main(){

        // create a stack with maximum capacity 10
        pArrayQueue queue = new pArrayQueue(10);

        // insert 10 elements onto the queue
        for(int i=0;i<10;i++){

            // make a string "objN" where N ranges 0 to 9
            string objToQueue = "obj" + i;

            // display what we're doing
            Console.WriteLine("inserting: {0}",objToQueue);

            // insert object onto the queue
            queue.insert(objToQueue);
        }

        // remove all elements from the queue
        while(!queue.isEmpty()){

            // remove object from the queue
            string objFromQueue = (string)queue.remove();

            // display what we're doing
            Console.WriteLine("removed: {0}",objFromQueue);
        }
    }
}

As you can see, it inserts ten objects onto the queue, and later prints them out (exactly like the stack test). The output from the program follows:

inserting: obj0
inserting: obj1
inserting: obj2
inserting: obj3
inserting: obj4
inserting: obj5
inserting: obj6
inserting: obj7
inserting: obj8
inserting: obj9
removed: obj0
removed: obj1
removed: obj2
removed: obj3
removed: obj4
removed: obj5
removed: obj6
removed: obj7
removed: obj8
removed: obj9

I suggest you compare this output to the one from stack. It's almost completely different. In this one, elements are removed in the same order they were inserted. In the stack one, they are removed in the opposite order.

I guess that's it for the array implementation of this FIFO data structure; now, onto something a bit more complex...


Array Lists...

The next step up in complexity is a list. Most people prefer to implement a list as a linked list (and we'll 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, let's not just talk about a list, but write one!

/**
 * Array implementation of List.
 */
public class pArrayList {

    // declare some properties
    protected object[] data;
    protected int start, end, theSize;

    /**
     * construct a new list given the capacity
     */
    public pArrayList(int capacity){

        // allocate memory for list
        data = new object[capacity];

        // start, end and size are 0 (list is empty)
        start = end = theSize = 0;
    }

    /**
     * check whether this list is empty
     */
    public bool isEmpty(){
        return theSize == 0;
    }

    /**
     * check whether this list is full
     */
    public bool isFull(){
        return theSize >= data.Length;
    }

    /**
     * gets the size of this list
     */
    public int size(){
        return theSize;
    }

    /**
     * insert an object at the front of the list
     */
    public void insert(object o){

        // if insert won't overflow list
        if(theSize < data.Length){

            // increment start and set element
            data[start = (start + 1) % data.Length] = o;

            // increment list size (we've added an object)
            theSize++;
        }
    }

    /**
     * insert an object at the end of the list
     */
    public void insertEnd(object o){

        // if insert won't overflow list
        if(theSize < data.Length){

            // set array element with object
            data[end] = o;

            // move end pointer to reflect added object
            end = (end + data.Length - 1) % data.Length;

            // increment list size (we've added an object)
            theSize++;
        }
    }

    /**
     * remove object from front of the list
     */
    public object remove(){

        // check if list is not empty
        if(isEmpty())
            return null;

        // decrement size
        theSize--;

        // get object to be returned
        object o = data[start];

        // null out memory location
        data[start] = null;

        // update start location
        start = (start + data.Length - 1) % data.Length;

        // return object we got
        return o;
    }

    /**
     * remove object from end of the list
     */
    public object removeEnd(){

        // check if list is not empty
        if(isEmpty())
            return null;

        // decrement size
        theSize--;

        // update end location
        end = (end + 1) % data.Length;

        // get object to be returned
        object o = data[end];

        // null out memory location
        data[end] = null;

        // return object we got
        return o;
    }

    /**
     * peek at an element in the list
     */
    public object peek(int offset){

        // is someone trying to peek beyond our size?
        if(offset >= theSize)
            return null;

        // get object we're peeking at (do not remove it)
        return data[(end + offset + 1) % data.Length];
    }
}

The class contains four data elements: data, start, end, and theSize. The theSize 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 data.Length, and do a mod with data.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 theSize. 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 grab the element we want to return, update the start pointer to reflect our removal, and return that element. The start pointer is updated in a similar way to insertEnd(), where we decremented the start and added data.Length and did a mod. As before, this gives the appearance of removing an element from the front of the list (moving the start pointer backwards). We then proceed to return the element we saved earlier.

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 theSize (number of elements) business, and proceeds with updating the end pointer. It first increments the end pointer, and then does a mod with data.Length, and returns the resulting object after null-ing out the array position. Simple?

The next method, object peek(int n), 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 'offset' 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 'offset' (the requesting number) to an incremented end pointer, and do a mod data.Length. This way, it appears as if this function is referencing the array from 0 (while the actual start is the incremented end pointer).

To understand all these array manipulations it helps to draw it out on paper, and to simply count the boxes you need to move, etc., and then compare them to what the code is doing.

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 Queue test driver, and added some features to test out the specifics of a list. Well, here it is:

using System;

/**
 * array list test class; just runs a few
 * simple iterations on the array list.
 */
public class pArrayListTest {

    /**
     * main method to test the lists
     */
    public static void Main(){

        // create a list with maximum capacity 10
        pArrayList list = new pArrayList(10);

        int i;

        // insert 5 elements onto the list (front insert)
        for(i=0;i<5;i++){
            // make a string "objN" where N ranges 0 to 4
            string objToList = "obj" + i;

            // display what we're doing
            Console.WriteLine("insert: {0}",objToList);

            // insert object onto the queue
            list.insert(objToList);
        }

        // fill the list (inserting at end)
        while(!list.isFull()){
            // make a string "objN" where N ranges 4 to 9
            string objToList = "obj" + i++;

            // display what we're doing
            Console.WriteLine("insertEnd: {0}",objToList);

            // insert object onto the queue
            list.insertEnd(objToList);
        }

        // peek through the whole list
        for(i=0;i<list.size();i++)
            Console.WriteLine("peek {0}: {1}",i,list.peek(i));

        // remove five elements from front of list
        for(i=0;i<5;i++)
            Console.WriteLine("remove: {0}",list.remove());

        // clear out the list (from the end)
        while(!list.isEmpty())
            Console.WriteLine("removeEnd: {0}",list.removeEnd());
    }
}

The test driver is nothing special, it inserts (in front) five objects (similar to the ones we did in Stack and Queue), 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 objects, and later removing the rest (also five).

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.

insert: obj0
insert: obj1
insert: obj2
insert: obj3
insert: obj4
insertEnd: obj5
insertEnd: obj6
insertEnd: obj7
insertEnd: obj8
insertEnd: obj9
peek 0: obj9
peek 1: obj8
peek 2: obj7
peek 3: obj6
peek 4: obj5
peek 5: obj0
peek 6: obj1
peek 7: obj2
peek 8: obj3
peek 9: obj4
remove: obj4
remove: obj3
remove: obj2
remove: obj1
remove: obj0
removeEnd: obj9
removeEnd: obj8
removeEnd: obj7
removeEnd: obj6
removeEnd: obj5

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).


Contact Info...

    The only sure way to find me, is to use my e-mail @theparticle.com. Yep, it's my domain which will hopefully stay with me.

    I encourage feedback!

Particle
particle at NO SPAM the particle dot com
http://www.theparticle.com/

Copyright © 2002, Particle

© 1996-2016 by End of the World Production, LLC.