Notes 5

Abstract Data Types

We have seen several examples of data types. Each class we have made is a new data type. Arrays and Vectors are data types. Data types, like classes, have a set of properties that define them. An array is a specific data type because it has a single concrete implementation. Abstract data types (ADT) have a definition which is separate from the implementation. We will see this in the definitions of some container classes. A container is a class that holds a collection of objects. All containers have some common properties. Elements can be added and deleted, you can ask how many elements are in the container. Examples include arrays, vectors, lists, stacks and others.

Linked Lists ADT

Lists are a container class. Each element in the container includes the location of the next. Elements can be added at either end or anywhere in between. Lists can be empty and have no length limit. You cannot directly access any element as you can in an array. To get to the third element, you have to go through the first two. Access is slower than arrays. Insertions and deletions are easier. Elements can either be single or double linked to each other. A thing is a list if each part or node is connected to the next. Each node can be connected to only one other. You can add nodes to either end of the list or in between any two nodes. A list can be empty.

This is the description or definition of a list. There are many ways to implement a list as long as they obey the rules for listhood. We will look at two implementations. one using arrays and another using references. For all these examples we will need a data class.


public class Data
{
    private int x,y;

    public Data() { x = 0; y=0; }
    public Data(int a, int b) { x = a; y=b; }
    public int getX() { return x;}
    public int getY() { return y;}
    public void setX(int a) { x=a;}
    public void setY(int a) { y=a;}
    public String toString() { return "x= " + x + " y= " + y;}
    public boolean equals(Data other)
    {
        if( (x == other.getX()) && (y == other.getY()) )
            return true;
        return false;
    } // equals
} // Data class

Array implementation

Since an array requires that all the elements be of the same type, I can't create an array that will hold both the data items and the pointer items at the same time. To do this, I need a simple container that holds both items. The pointers in an array implementation are just array indices. So here is an intermediate class to do this.

import Data;

public class ListData
{
    private Data d;   // the data element in this node
    private int next;   // the pointer to the next one

    /** Constructor for objects of class ListData */
    public ListData() { d=null; }

    public int getNext() { return next; }
    public void setNext(int v) { next = v;}
    
    public Data getData() { return d;}
    public void setData(Data x) { d=x;}
} // class ListData

Now we need a class that holds the list. I decided to make a class that held a single list of data objects. It would be possible to construct an array that would hold several lists in it. This class has methods to implement the list operations like addToFront(), addToEnd(), etc.

import Data;
import ListData;

public class AList
{
    private ListData[] List = null;
    private static final int FREE=-2;  // marks unused slot
    public static final int NIL = -1;  // end of list pointer
    private static final int DEFSIZE=10; // default size of the List array
    private int Pos=0;  // last slot used
    private int Head=NIL;  // first entry in this list

    /** Constructor for objects of class AList */
    public AList()
    {
        List = new ListData[DEFSIZE];  // array of references
        for(int i = 0; i < List.length; i++) // fill in slots
		  List[i] = new ListData();
        clearArray();  // mark all free
    }
    public AList(int size)
    {
        List = new ListData[size];  // array of references
        for(int i = 0; i < List.length; i++)  // fill in slots
		  List[i] = new ListData();
        clearArray();  // mark all free
    }
    
    // mark each array entry as being free
    private void clearArray()
    {
       	for(int i = 0; i < List.length; i++)
		  List[i].setNext(FREE);
    } // clearArray
    
    /*
    When we want to add an element to the list, we  look through the 
    array for an element that has a next value of -1.
    To make the search a little faster, we can keep a counter to tell us where
    we stopped last.
    */
    private int findEmpty()
    {
        int start = Pos; // start where we left off
        while(List[start].getNext() != FREE) {
            start  += (++start % List.length);  // wrap around the array
            if(start == Pos) return NIL;  // we wrapped around
	   } // while
	   // the only way out of the loop this way is if we found one
	   Pos = (start+1) % List.length; // start again after the one we found
	   return start;
    } // findEmpty
    
    /* We find an elmpty slot first. If there aren't any, return false.
       Adding to the front is easy since we just set the head pointer
       to the new element and set the new elements next field to point
       to whatever the list head pointed to.
       If the head is NIL, it still works the way we want.
    */
    public boolean addToFront(Data d)
    {
        int my_l=findEmpty();
        if( my_l == NIL) return false;  // no slots
        List[my_l].setData(d);
        List[my_l].setNext(Head);
        Head = my_l;
        return true;
    } // addToFront
    
    /*  Like addToFront(), we first find an empty slot and if
        there is one, store the data value  in it.
        Then we have to find the lest element of the list.
        We do this in a loop where we check if the pointer is NIL
        and if it isn't, check if it's next is NIL.
        We want to stop when the pointer is referring to the last element.
        If the pointer is NIL when we leave the loop, then the list was
        empty and we just point the Head pointer at it.
        Otherwise, we change the next pointer of the last one to point
        to the one we just added.
    */
    public boolean addToEnd(Data d)
    {
        int my_l,lptr = Head;
        if( (my_l = findEmpty()) == NIL) return false;  // no memory
        List[my_l].setData(d);
        List[my_l].setNext(NIL);
        // find the end of the list
        while( (lptr != NIL) && (List[lptr].getNext() != NIL)) {
            lptr = List[lptr].getNext();
        } // while
        if(lptr == NIL) 
            Head = my_l; // first entry
        else
            List[lptr].setNext(my_l);
        return true;	
    }  // addToEnd
    
    // loop over the list bumping a counter. Note we stop
    // when we have gone past the last element on the list.
    public int length()
    {
        int lptr = Head, count=0;
        while(lptr != NIL) {
            count++;
            lptr = List[lptr].getNext();
        } // while
        return count;
    } // length

    /*  We start at the front of the list and look at each element
        checking if the data item stored there is the same as
        one we passed in.
    */
    public int find(Data target)
    {
        int lptr = Head;
    	while(lptr != NIL) {
            if(List[lptr].getData().equals(target))
                return lptr;
			lptr = List[lptr].getNext();
		} // while
        return NIL; // is we get here, we didn't find it
    } // find
    
    // walk the list and print each data item
    public void printList()
    {
		int lptr = Head;
		if(lptr == NIL) return;
		while(lptr != NIL) {
            System.out.println(List[lptr].getData());
			lptr = List[lptr].getNext();
		} // while
    } // printList

} // class AList
Now all we need is a small driver to test the implementation.

import AList;

public class Main
{
    public static void main(String[] args)
    {
        AList joe = new AList(6);
        joe.addToFront(new Data(1,42));
        joe.addToFront(new Data(2,43));
        joe.addToEnd(new Data(3,44));
        joe.printList();
        System.out.println("There are " + joe.length() + " items in the list");
        int results = joe.find(new Data(1,42));
        System.out.println("Item(1,42) found at location " + results);
        results = joe.find(new Data(2,43));
        System.out.println("Item(2,43) found at location " + results);
        results = joe.find(new Data(2,454));
        System.out.println("Item(2,454) found at location " + results);
    } // main

}  // class main
And here is what happens when it runs.

x= 2 y= 43
x= 1 y= 42
x= 3 y= 44
There are 3 items in the list
Item(1,42) found at location 0
Item(2,43) found at location 1
Item(2,454) found at location -1
This code is also available under the examples section here.

Linked implementation

Normally, lists are built using more dynamic linked structures. The array implementation has a strict size limit in that the array can't get bigger. And regardless of how long or short the list is, the array takes up the same amount of room. Here we will see an implementation that is similar to the array one, but uses references to link the nodes together rather than array indices. It uses the same Data class as above. First up is the listdata class. Note that the changes are to the type of the next field.

import data;

public class listdata
{
    private data d;   // the data element in this node
    private listdata next;   // the pointer to the next one

    /** Constructor for objects of class ListData */
    public listdata() { d=null; next=null; }
    public listdata(data other) { d=other; next=null; }

    public listdata getNext() { return next; }
    public void setNext(listdata v) { next = v;}
    
    public data getData() { return d;}
    public void setData(data x) { d=x;}
} // class ListData
Each listdata instance contains a reference to the next one.

The main list code is similar but a number of routines are removed.


import data;
import listdata;

public class llist
{
    private listdata Head;  // first entry in this list

    /** Constructor for objects of class llist */
    public llist()
    {
        Head=null;
    }
     
     /* We make a listdata node first. If there is no memory, we return false.
        Later this will be changed to use exceptions.
        Adding to the front is easy since we just set the head pointer
        to the new element and set the new elements next field to point
        to whatever the list head pointed to.
        If the head is null, it still works the way we want.
    */
    public boolean addToFront(data d)
    {
        listdata my_l=new listdata(d);
        if( my_l == null) return false;  // no memory
        my_l.setNext(Head);
        Head = my_l;
        return true;
    } // addToFront
    
    /*  Like addToFront(), we first create a listdata node and
        add the data to it.
        Then we have to find the last element of the list.
        We do this in a loop where we check if the pointer is null
        and if it isn't, check if its next is null.
        We want to stop when the pointer is referring to the last element.
        If the pointer is null when we leave the loop, then the list was
        empty and we just point the Head pointer at it.
        Otherwise, we change the next pointer of the last one to point
        to the one we just added.
    */
    public boolean addToEnd(data d)
    {
        listdata my_l,lptr = Head;
        if( (my_l = new listdata(d)) == null) return false;  // no memory
        // find the end of the list
        while( (lptr != null) && (lptr.getNext() != null)) {
            lptr = lptr.getNext();
        } // while
        if(lptr == null) 
            Head = my_l; // first entry
        else
            lptr.setNext(my_l);
        return true;    
    }  // addToEnd
    
    // loop over the list bumping a counter. Note we stop
    // when we have gone past the last element on the list.
    public int length()
    {
        int count=0;
        for(listdata lptr = Head; lptr != null; lptr = lptr.getNext())  {
            count++;
        } // for
        return count;
    } // length

    /*  We start at the front of the list and look at each element
        checking if the data item stored there is the same as
        one we passed in.
    */
    public listdata find(data target)
    {
        listdata lptr = Head;
        while(lptr != null) {
            if(lptr.getData().equals(target))
                return lptr;
            lptr = lptr.getNext();
        } // while
        return null; // is we get here, we didn't find it
    } // find
    
    // walk the list and print each data item
    public void printList()
    {
        listdata lptr = Head;
        while(lptr != null) {
            System.out.println(lptr.getData());
            lptr = lptr.getNext();
        } // while
    } // printList
} // class llist
Here is the somewhat changed driver code.

import llist;

public class main
{
    public static void main(String[] args)
    {
        llist joe = new llist();
        joe.addToFront(new data(1,42));
        joe.addToFront(new data(2,43));
        joe.addToEnd(new data(3,44));
        joe.printList();
        System.out.println("There are " + joe.length() + " items in the list");
        look(joe,1,42);
        look(joe,2,43);
        look(joe,2,454);
    } // main

    // look for the item indicated in the list passed. print results
    private static void look(llist l, int a, int b)
    {
        listdata results = l.find(new data(a,b));
        if(results != null)
            System.out.println("Item(" + a + "," + b  + ") found");
        else
            System.out.println("Item(" + a + "," + b  + ") not found");
    } // look
}  // class main
This code is also available under the examples section here.