Linked Lists

Create a linked list record class (LinkedList.java) which contains one string data field (name) and one pointer (LinkedList) . It should contain an empty constructor as well as the two get and two put methods for the data.

// The "LinkListRecord" class.
public class LinkListRecord
{
    private String name;
    private LinkListRecord next;

    // initializes list with data
    public LinkListRecord ()
    {
     this.name = "";
     next = null;
    } // end constructor

    public String getData ()
    {
     return name;
    }

    public LinkListRecord getNext ()
    {
     return next;
    }

    public void setName (String name)
    {
     this.name = name;
    }

    public void setNext (LinkListRecord next)
    {
     this.next = next;
    }
} // LinkListRecord class

... Then create a test program that lets you enter several names and print them out from first to last.

// The "Ass2s4p1" class.
import java.awt.*;
import hsa.Console;

public class Ass2s4p1
{
    static Console c = new Console ();

    public static void main (String [] args)
    {
     String name;
     LinkListRecord first, last;
     c.println ("Enter a name: ");
     String newName = c.readLine ();
     first = new LinkListRecord ();
     first.setName (newName);
     last = first;
     c.println ("Enter a new name, end with q");
     newName = c.readLine ();
     while (!newName.equals ("q"))
     {
         LinkListRecord p = new LinkListRecord ();
         last.setNext (p);
         p.setName (newName);
         last = p;
         c.println ("Enter a new name, end with q");
         newName = c.readLine ();
     }
     c.println ("here is the reverse order list: ");
     LinkListRecord p = first;
     while (p != null)
     {
         c.println (p.getData ());
         p = p.getNext ();
     }

    } // main method
} // Ass2s4p1 class

Prepare a new binary file from the metro population file of problem 2.2.6, that contains only the city's name and the current (2002) population. Save the data in alphabetic order.

Calgary (AB)                  993.2     
Chicoutimi-JonquiËre (QC)     156.9     
Edmonton (AB)                 967.2     
Halifax (NS)                  363.2     
Hamilton (ON)                 686.9     
Kitchener (ON)                438       
London (ON)                   427.3     
MontrÈal (QC)                 3548.8    
Oshawa (ON)                   310       
Ottawa-Hull (ON-QC)           1128.9    
QuÈbec (QC)                   697.8     
Regina (SK)                   197       
Saint John (NB)               127  
Saskatoon (SK)                231.8     
Sherbrooke (QC)               156.5     
St. Catharines-Niagara (ON)   392.3     
St. John's (NF)               177.2     
Sudbury (ON)                  155.9     
Thunder Bay (ON)              125.1     
Toronto (ON)                  5029.9    
Trois-RiviËres (QC)           141.4     
Vancouver (BC)                2136.2    
Victoria (BC)                 322.1     
Windsor (ON)                  319.9     
Winnipeg (MB)                 685.5     

// The "Ass2s4p2" class.
import java.awt.*;
import java.io.*;
import hsa.Console;

public class Ass2s4p2
{
    static Console cs = new Console ();
    static String name [] = new String [25];
    static double pop [] = new double [25];

    public static void main (String [] args) throws IOException
    {
     readText ("cities.txt");
     saveBin ("cities.dat");
     cs.println ("done");
    } // end main method


    public static void readText (String fileName) throws IOException
    {
     String line;
     FileReader f = new FileReader (fileName);
     BufferedReader input = new BufferedReader (f);
     for (int i = 0 ; i < 25 ; i++)
     {
         line = input.readLine ();
         name [i] = line.substring (0, 30);
         pop [i] = Double.valueOf (line.substring (30)).doubleValue ();
     } // end i-loop
     input.close ();
    } // end readText


    public static void saveBin (String fileName) throws IOException
    {
     RandomAccessFile f = new RandomAccessFile ("cities.dat", "rw");
     for (int i = 0 ; i <  25 ; i++)
     {
         byte nameBytes [] = new byte [30];
         // add an extra 30 spaces to assure that there are at least 30
         name [i] += "                         ";
         name [i].getBytes (0, 30, nameBytes, 0);
         f.write (nameBytes);
         f.writeDouble (pop [i]);
     } //end for each record
     f.close ();
    }
} // Ass2s4p2 class

Create a linked list record class called PopMetro.java which contains one name and one real number. Then write a program that uses it to load a linked list from the binary file of 2.4.2 and that prints the linked list on screen.

// The "PopMetro" class.
public class PopMetro
{
    private String name;
    private double pop;
    private PopMetro next;

    // initializes list with data
    public PopMetro ()
    {
     name = "";
     pop = 0;
     next = null;
    } // end constructor

    public String getName ()
    {
     return name;
    }

    public double getPopulation ()
    {
     return pop;
    }

    public PopMetro getNext ()
    {
     return next;
    }

    public void setName (String name)
    {
     this.name = name;
    }

    public void setPopulation (double pop)
    {
     this.pop = pop;
    }

    public void setNext (PopMetro next)
    {
     this.next = next;
    }
} // PopMetro class

Create a class ListMetroPop that uses the routines you have developed in the previous few programs, to manage the binary file. It should contain a constructor, ListMetroPop(String binFile) that loads the binary file into a linked list and that contains the following methods:

     PopMetro find(String name) // null, if not found
     void add(String name, double pop)  // in alphabetic order
     void delete (String name) // does nothing if not found
     void print (Console c) // print the entire list on the given console
     void save(String binFile) // saves the data to the said file

// The "ListMetroPop" class.
import java.io.*;
import hsa.TextConsole;

public class ListMetroPop
{
    private PopMetro first = null, p = null;
    private long len = 0;

    // this constructor loads the file into a linked list
    // the number of records is "len"
    // the first record can be found at "first"
    public ListMetroPop (String datFile)
    {
     String nameTemp;
     double popTemp;
     try
     {
         RandomAccessFile f = new RandomAccessFile (datFile, "r");
         len = f.length () / 38;
         if (len > 0)
         {
            first = new PopMetro ();
            byte nameBytes [] = new byte [30];
            f.readFully (nameBytes);
            nameTemp = new String (nameBytes, 0).trim ();
            popTemp = f.readDouble ();
            first.setName (nameTemp);
            first.setPopulation (popTemp);
            p = first;
            for (int i = 1 ; i < len ; i++)
            {
               f.readFully (nameBytes);
               nameTemp = new String (nameBytes, 0).trim ();
               popTemp = f.readDouble ();
               p.setNext (new PopMetro ());
               p = p.getNext ();
               p.setName (nameTemp);
               p.setPopulation (popTemp);
            }
            p.setNext (null);
         }
         f.close ();
     }
     catch (IOException e)
     {
     }
    } // end constructor


    // the following routine will only compare the characters of "city"
    public PopMetro find (String city)
    {
      p = first;
      PopMetro found = null;
      while (p != null)
      {
         int charnum = city.length ();
         if (p.getName ().substring (0, charnum).equalsIgnoreCase (city))
             found = p;
         p = p.getNext ();
      }
      return found;
    } // end find


    //
    public void add (String name, double pop)
    {
       PopMetro temp = null;
       String upName = name.toUpperCase ();
       PopMetro current = new PopMetro ();
       current.setName (name);
       current.setPopulation (pop);
       // case: the list is empty or the name comes before first
       if (first == null || first.getName ().toUpperCase ().compareTo (upName) > 0)
        {
           current.setNext (first);
           first = current;
        }
       // case: the name comes after first
       else
        {
           p = first;
           while (p != null && p.getName ().compareTo (name) < 0)
           {
             temp = p;
             p = p.getNext ();
           }
           temp.setNext (current);
           current.setNext (p);
        }
    } // end add


    public void delete (String name)
    {
     PopMetro temp = null;
     String upName = name.toUpperCase ();
     if (first != null)
     {
         if (first.getName ().equalsIgnoreCase (name))
              first = first.getNext ();
         else
         {
            p = first;
            while (p != null && p.getName ().toUpperCase ().compareTo (upName) < 0)
            {
               temp = p;
               p = p.getNext ();
            }
            if (p != null && p.getName ().equalsIgnoreCase (name))
                 temp.setNext (p.getNext ());
         }
     }
    } // end delete


    public void print (TextConsole c)
    {
     c.println ("city                       population");
     c.println ("-------------------------------------");
     p = first;
     while (p != null)
     {
         c.print (p.getName (), 30);
         c.println (p.getPopulation (), 5, 1);
         p = p.getNext ();
     }
    } // end print


    public void save (String datFile)
    {
     String nameTemp;
     double popTemp;
     try
     {
         RandomAccessFile f = new RandomAccessFile (datFile, "rw");
         p = first;
         while (p != null)
         {
            nameTemp = p.getName () + "                              ";
            f.writeBytes (nameTemp.substring (0, 30));
            f.writeDouble (p.getPopulation ());
            p=p.getNext();
         }
         f.close ();
     }
     catch (IOException e)
     {
     }
   } // end save
} // end "ListMetroPop" Class

...Write a program to test the class.

// The "Ass2s4p7" class.
import java.awt.*;
import hsa.TextConsole;

public class Ass2s4p7
{
    static TextConsole cs = new TextConsole ();
    static ListMetroPop canCities;
    static PopMetro rec;

    public static void main (String [] args)
    {
     rec = new PopMetro ();
     canCities = new ListMetroPop ("town.dat");
     String tempName = "";
     double tempPop = 0;
     char c = menu ();
     while (c != 'Q')
     {
         switch (c)
         {
          case 'L':
              canCities.print (cs);
              break;
          case 'A':
              cs.print ("Enter a city name you wish to ADD: ");
              tempName = cs.readLine ();
              cs.print ("Enter the population for " + tempName + ": ");
              tempPop = cs.readDouble ();
              canCities.add (tempName, tempPop);
              break;
          case 'D':
              cs.print ("Enter the city name you wish to DELETE: ");
              tempName = cs.readLine ();
              canCities.delete (tempName);
              break;
          case 'F':
              cs.print ("Enter (part of) the city name you wish to FIND: ");
              tempName = cs.readLine ();
              rec = canCities.find (tempName);
              if (rec == null)
                 cs.println (tempName + " is not on file");
              else
                 cs.println ("city: " + rec.getName () + " population: " 
                         + rec.getPopulation ());
              break;
          case 'S':
              cs.print ("Enter the name of the file to save: ");
              tempName = cs.readLine ();
              canCities.save (tempName);
              break;
         }
         c = menu ();
     }
     cs.println ("\nBye");
    } // main method


    public static char menu ()
    {
      PopMetro p = new PopMetro ();
      cs.println ("Canadian Cities Menu");
      cs.println ("L List the entire file");
      cs.println ("A Add a record");
      cs.println ("D Delete a record");
      cs.println ("F Find a record");
      cs.println ("S Save the list to disk");
      cs.println ("Q Quit");
      cs.print ("\nWhat do you wish to do? ");
      String choice = cs.readString ().toUpperCase ();
      return choice.charAt (0);
    }
} // Ass2s4p7 class