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
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 ListDataNow 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 AListNow 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 mainAnd 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 -1This code is also available under the examples section here.
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 ListDataEach 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 llistHere 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 mainThis code is also available under the examples section here.