creating my own linked list class - very new to this


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 5 of 5

Thread: creating my own linked list class - very new to this

Hybrid View

  1. #1
    Join Date
    Dec 2004
    Posts
    4

    creating my own linked list class - very new to this

    I have tried searching the forum (and google) and can't seem to come with anything that solves my problem. either that or i just really dont get it. My professor was to supply a class that creates an object of a class that I will create called PriorityQueue.

    PriorityQueue to my understanding is to take the place of the LinkedList class as i was strictly instructed not to use the LinkedList class. What i am wondering is this, with an array i could use index's within my PriorityQueue class and wouldn't have to worry. but not without being able to use indexes, how am i supposed to keep track of all the names that can be entered by the user? After i enter more than 2 names, how is the program to keep track of any new names entered?

    The first object should hold the first node for as long as the program runs. But after i take in a few more names from the user, how am i supposed to know what was ever in the second node? Since tempNode gets new data everytime a user enters a name, and we keep moving position up the list as we get names, but its really not even a list. im just changing the values of .data. Can anyone understand what I'm saying? Would an iterator be of use here or since i'm not using java's linked list class it wouldn't work?

    I'm so confused right now. Most of the examples i see online are for classes that use either the java supplied linkedlist or create their own and do everything within that class.

    My professor has supplied this amount of code to me already.

    Code:
    
    /**
    StaffList.java
    Provided by instructor for use in Project 6 - Priority Queue
    */
    
    import java.io.*;
    /**
    Demonstrates use of PriorityQueue class in compiling an ordered list of staff.
    */
    
    public class StaffList
    {  
       public static void main(String[] args) throws IOException
       {
          PriorityQueue staff = new PriorityQueue();
                
          BufferedReader in =
             new BufferedReader (new InputStreamReader (System.in));
    
          System.out.print("Enter a name to add to the staff, . to quit: ");
          String name = in.readLine();
    
          while (!name.equals("."))
          {
             staff.insert(name); 
             System.out.println("The updated staff list:");
             System.out.println(staff);
             System.out.print("Enter a name to add to the staff, . to quit: ");
             name = in.readLine();
          }  
       }
    }
    
    I have coded this much, but its hardly anything at all.

    Code:
    
    import java.util.*;
    
    public class PriorityQueue
    {
    	private class Node
    	{
    	     public Object data;
    	     public Node next;
    	}
    
    	public PriorityQueue()
    	{
    	     first = null;
    	}
    
    	public boolean empty()
    	{
    	     return (newNode == null);
    	}
    
    	public void insert(Comparable obj)
    	{
    	   Node tempNode = new Node();
    	   tempNode.next = newNode;
    	   tempNode.data = obj;
    	  //need to test if empty first
    	   if (empty())
    	   {
    	       first = tempNode;
    	   }
    		
    	   newNode = tempNode;
    
    	}
    
    	public String toString()
    	{
                       //figure out the list before moving down it and printing
    	   String returnStr = (String)newNode.data;
    	   return (String)returnStr;
    	}
    	private Node newNode;
    	private Node first;
    	private Node position;
    }
    

  2. #2
    Join Date
    Dec 2004
    Posts
    4
    is the object staff supposed to represent the linked list itself? in order for the linked list to work, there must be multiple objects stored in some location. each object has a reference to the object after it. (im working a singly linked list). but they have to be stored somewhere in my program. does staff represent that "location" where my nodes are stored?

  3. #3
    Join Date
    Nov 2004
    Location
    Minnesota
    Posts
    99
    Yes, the object, staff, is the location where all of your data gets put.

    //this inserts a name on the priority queue
    staff.insert(name);

    Currently, your code only puts it at the front of the list (first node). However, I'm assuming you will change the insert method after you understand what is going on...

    I would look at your textbook or lecture notes on what he actually wants your priority queue to do (what is the priority, is it just making the list sorted? Or is there some other way of determining that Bill comes before Susan?) Oh, wait. I see that insert takes a Comparable, which means all objects inserted must implement compare()...seems like that should be the method to use to determine where in the list a new name should be inserted! If so, then data should also be of type Comparable, not Object.

    Hope this helps.

  4. #4
    Join Date
    Dec 2004
    Posts
    4
    i got it

    thankyou. yea that did help. i just couldn't figure out why or how or where the nodes were getting stored. its a little complicated at first but its ok now. thanks again.

    now i have just one other problem. in a second class that the teacher has given me, i can't seem to compile. I get an error that an object of type Job (class i created) can't be passed into insert method of my PriorityQueue class that is accepting Comparable objects. However, the insert method is required to accept this kind of object. What do you guys think?

    Code:
    Job Class
    /**
     Job.java
     Project 3
    */
    
    public class Job
    {
    	/**
    	 Constructor for the Job class
    	 */
    	public Job(int priority, String description)
    	{
    		cPriority = priority;
    		cDescription = description;
    	}
    
    	public int compareTo(Object other)
    	{
    		if (((Job)other).cPriority > this.cPriority) return LOWER_PRIORITY;
    		else if (((Job)other).cPriority > this.cPriority) return HIGHER_PRIORITY;
    		else return EQUAL_PRIORITY;
    	}
    
    	public String toString()
    	{
    		return cDescription;
    	}
    
    	private String cDescription;
    	private int cPriority;
    	private final int LOWER_PRIORITY = -1;
    	private final int HIGHER_PRIORITY = 1;
      	private final int EQUAL_PRIORITY = 0;
    }
    Code:
    ToDoList.java \\ given by instructor and not to be changed
    /**
    ToDoList.java
    Provided by instructor for use in Project 6 - Priority Queue
    */
    import java.io.*;
    
    /**
    Demonstrates use of PriorityQueue class in maintaining a to-do list.
    */
    public class ToDoList
    {  
       public static void main(String[] args) throws IOException
       {
          PriorityQueue toDoList = new PriorityQueue();
                
          BufferedReader in =
             new BufferedReader (new InputStreamReader (System.in));
    
          String choice;
          
          do
          {
             printMenu();
       
             choice = in.readLine();
             if (choice.equals("a"))
             {
                System.out.print ("Enter job priority: ");
                boolean gotPriority = false;
                int priority = 0;
                while (!gotPriority)
                {
                   try
                   {
                      priority = Integer.parseInt(in.readLine());
                      gotPriority = true;
                   }
                   catch (NumberFormatException exception)
                   {
                      System.out.print ("Priority must be an integer.  "+
                         "Please try again: ");
                   }
                }
                System.out.print ("Enter job description: ");
                String description = in.readLine();
                Job job = new Job(priority, description);
                toDoList.insert(job);//error here
             }
             else if (choice.equals("g"))
             {
                if (toDoList.empty())
                   System.out.println ("There are no jobs in your to-do list!");
                else
                   System.out.println ("Your next job: " + toDoList.removeFirst());
             }
             else if (choice.equals("p"))
             {
                System.out.println ();
                System.out.println ("TO-DO LIST:");
                System.out.print(toDoList);
             }
             else if (!choice.equals("q"))
             {
                System.out.println ("Sorry, unrecognized command -- please try again");
             }
          }
          while (!choice.equals("q"));
       }
    
       /**
       Prints menu, preceded by a blank line.
       */
       private static void printMenu()
       {
          System.out.println();
          System.out.println("Menu:");
          System.out.print("   a: add a job to the to-do list");
          System.out.println("     g: get the next job to do");
          System.out.print("   p: print entire to-do list");
          System.out.println("         q: quit");
          System.out.print("Enter your choice: ");
       }
    }
    Code:
    updated insert method in PriorityQueue
    public void insert(Comparable obj) // doesn't like passing Job into Comparable here 
    	{
    		Node tempNode = new Node();
    		tempNode.data = obj;
    
    		//need to test if list is empty first
    		if (empty())
    		{
    			first.next = tempNode;
    		}
    
    		//list is not empty
    		else
    		{
    			boolean done = false;
    			position = first.next;
    			previous = null;
    
    			while(!done)
    			{
    				//higher priority, regardless of list size
    				if (position.data.compareTo(obj) > 0 && previous == null)
    				{
    					tempNode.next = position;
    					first.next = tempNode;
    					previous = tempNode;
    					done = true;
    				}
    
    				//higher priority, more than one item in list
    				else if (position.data.compareTo(obj) > 0 /* && position.next != null */ )
    				{
    					tempNode.next = position;
    					position = previous;
    					position.next = tempNode;
    					done = true;
    				}
    
    				//lower or equal priority and not at the end of list
    				else if (position.data.compareTo(obj) == 0 && position.next != null)
    				{
    					Node temp2 = new Node();
    					temp2 = position.next;
    					position.next = tempNode;
    					previous = position;
    					position = tempNode;
    					position.next = temp2;
    					done = true;
    				}
    
    				//lower or equal priority and at the end of the list
    				else if (position.data.compareTo(obj) <= 0 && position.next == null)
    				{
    					position.next = tempNode;
    					done = true;
    				}
    
    				//lower priority and not at the end of the list
    				else if (position.data.compareTo(obj) < 0 && position.next != null)
    				{
    					previous = position;
    					position = position.next;
    				}
    			}
    		}
    	}

  5. #5
    Join Date
    Dec 2004
    Posts
    4
    nevermind, i went to all the trouble posting and all it was, was that I didnt put "implements Comparable" in my Job class.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center