Solved

Need help with some code

Posted on 2011-03-23
27
416 Views
Last Modified: 2012-06-21
I am learning Java linked list to be precise. I have been working on it for about a week now but I have hit a brick wall. I need add and add method that adds strings according to the specifications of the constructor. I also need to add a getNext  method and getPrevious method according to the instructions. I have posted the code below. Any help would be appreciated

/*//Constructors

 LinkedList constructor
 *
 * The boolean parameter permitsDuplicates determines whether the list allows duplicate entries.
 *
 * The int parameter sortOrder determines whether and how the list should be sorted.
 * If sortOrder is zero, the list should not be sorted.
 * If sortOrder is a positive int, the list should be sorted in increasing order.
 * If sortOrder is a negative int, the list should be sorted in decreasing order.
 
//public LinkedList(boolean permitsDuplicates, int sortOrder)

//Your implementation of LinkedList needs to ensure that all of the following linked list varieties can be created using the above constructor:
Duplicates

    * lists that permit duplicates
    * lists that do not permit duplicates

Sorting

    * lists that maintain data in increasing sorted order
    * lists that maintain data in decreasing sorted order
    * lists that maintain data in non-sorted order

So, your List must handle all six possible combinations of the above characteristics. Careful design will help eliminate some redundant coding.

When sorting contents of the LinkedList, use alphabetic sorting based on the toString representation of the objects being sorted.

All List instances are initially empty.*/

public class LinkedList {
            
         private double size;
         private Node head;
         private Node present;
         private boolean permitsDuplicates;
         private int sortOrder;
        

          public LinkedList () {
              size = 0;
              head = null;
          }
          
          public LinkedList(Node t){
                
                head = t;
                reset();
                
          }
          
          public LinkedList(boolean permitsDuplicates, int sortOrder){
                
                this.permitsDuplicates = permitsDuplicates;
                this.sortOrder = sortOrder;
                
          }

          
        

          /* Insert a new node containing Object obj into the list according to the
           * sorting and duplication parameters specified at list construction.
           */

          public void add(Object obj){
                
          }
          
          /* Using an internally maintained pointer,
           *   return the contents stored at the node in the next position in the list.
           *
           *   E.g., the first time getNext() is called,
           *   it returns the contents of the first node in the list,
           *   the second time it's called, it returns the second item in the list, etc.
           *
           * If the list is empty, return null.
           * If the most recent call to getNext returned the last item in the list,
           *   and getPrevious has not been called since then,
           *   and no new items have been added to the end of the list, return null.
           *
           * When adding new items, the internal pointer should still point to the
           *   same item, even if doing so might cause its index position to change.
           *   If the current item is removed by a delete() call, simply reset the
           *   internal pointer to the beginning.
           */

          
          public Object getNext(){
                
                Node present = head;
                if(present == null || present.getNext() == null){
                      return null;
                } else
                  
              present = present.getNext();
              return present;
       
          }
          
          /* Using the SAME internally maintained pointer as getNext(),
           * return the contents of the node in the list immediately preceding the item last returned
           * by either getNext() or getPrevious().
           *
           * If the list is empty, return null.
           * If neither getNext nor getPrevious has been called on this object, return null.
           * If the most recent call to getNext() or getPrevious()
           *   returned the first item in the list, return null.
           * If the most recent call to getPrevious returned null,
           *   and getNext has not been called since then, return null.
           *
           * If the list is not empty, and the most recent call to getNext returned null
           *   (meaning the pointer is at the end of the list),
           *   and getPrevious has not been called since then, return the last item in the list.
           *
           * The behavior of the internal pointer when new items are added should
           *   be same with getNext().
           *
           * Note that you MUST NOT implement LinkedList using a doubly-linked list.
           */

          
          public Object getPrevious(){
                
          }
          
          public void reset(){
                present = head;
          }
          
          
      
       public static void main(String[] args){
             
             
       }

}
0
Comment
Question by:excalibuxo
  • 15
  • 11
27 Comments
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
You should add the java zone to get a larger response
0
 
LVL 26

Expert Comment

by:dpearson
Comment Utility
You should probably post the Node class too - it's not clear what's capable.

If Node contains a getPrevious() link then the getPrevious method is something like this:
 
public Object getPrevious(){                
                if(present == null){
                      return null;
                }
                  
                this.present = present.getPrevious();
                return this.present;
          }

Open in new window


If Node does not contain a getPrevious() method then you'd instead have to search:
 
public Object getPrevious(){
      Node p = head ;

      // Find p such that p.getNext() == present
      while (p != null && p.getNext() != present) {
         p = p.getNext() ;
      }       

      // Move present back to p
      present = p ;

      return present ;
 }

Open in new window


If the list is sorted, then the add method will require a similar loop to the one I included in getPrevious(), where you search for the correct place to insert the object into the sorted list.  The key here is to recognize that the list you're inserting into is already sorted, so all you need to do is scan down it in the correct sequence until you find the place to add the new object.

If the list isn't sorted, then you should just add the object (unless the list is "no duplicates" in which case you'd need to scan the list looking to see if the same value is there).

I don't want to write all of this for you since it's clearly a learning exercise.

But I hope this helps move you in the right direction,

Doug
0
 

Author Comment

by:excalibuxo
Comment Utility
I guess my next question is how do I sort the list. Do I use a the toString method in the objects class or the compareto method and could you please include a code example that I can follow and try to understand this is the code for my node class.

public class Node {
      
      public Node(){
            
            data = null;
            next = null;
      }
      
      public Node(Object initData, Node initLink) {
        data = initData;
        next = initLink;
    }

    // selectors and modifiers

    public void setData(Object newData) {
        data = newData;
    }

    public void setNext(Node newLink) {
        next = newLink;
    }
   
    public Object getData() {
        return data;
    }

    public Node getNext() {
        return next;
    }

    // methods
   
    public boolean equals(Object o) {

        if (data != null && o != null) {
            return data.equals(((Node) o).data);
        } else {
            return (data == null && o == null);
        }
    }



    public void display() {
        System.out.println(data.toString());
    }

 

    // instance data

    private Object data;
    private Node next;


       
0
 

Author Comment

by:excalibuxo
Comment Utility
How is the second getPrevious method working specifically what is p.getNext() != present and p = p.getNext(). Thank you for the help.
0
 
LVL 26

Expert Comment

by:dpearson
Comment Utility
The problem statement says:
"When sorting contents of the LinkedList, use alphabetic sorting based on the toString representation of the objects being sorted."

so yes you should use the toString() method and compare those values.

The basic method is:

public void add(Object obj) {
     Node p = head ;
     if (p == null) {
         // Empty list
         head = new Node(obj, null) ;
         return ;
     }

     String insert = obj.toString() ;
     // Scan the list to find where to insert
     // Testing == -1 here depends on the sort order.  You will want to test == 1 to sort
     // in the other direction and == 0 to check for duplicates.
     while (p.getNext() != null && p.getData().toString().compareTo(insert) == -1 ) {
          p = p.getNext() ;
     }

     // Add the new object into the list
     Object pNext = p.getNext() ;
     p.setNext(new Node(obj, pNext)) ;
}

 I've not thought this through very carefully - this may be inserting one ahead of where you want or one behind - depends on exactly when to stop the loop, but it gives you the pattern.

Hope this helps,

Doug
0
 
LVL 26

Expert Comment

by:dpearson
Comment Utility
You asked how this is working:

      // Find p such that p.getNext() == present
      while (p != null && p.getNext() != present) {
         p = p.getNext() ;
      }  

This is walking down the list (moving the "p" pointer down the list) until it reaches the place where it's next point (p.getNext()) matches the current "present" marker.

When p.getNext() equals the present marker, then p is the value before present in the list.  So p is now the previous value before present - which is what we're looking for.

Make sense?

Doug
0
 

Author Comment

by:excalibuxo
Comment Utility
Makes lots of sense let me look at all we've discussed and then I will get back with more questions . I have have to say thank you again for all the help.
0
 

Author Comment

by:excalibuxo
Comment Utility
Question in the add method I am supposed to add code for sorting which way?  I mean which way did you sort it so that I can do it the other way. For == 0 part the instructions say that that should be for a loop that is not being sorted so can I still use it for duplicates and if not how do I go ahead and differentiate lists that should allow duplicates and ones that shouldn't.
0
 
LVL 26

Expert Comment

by:dpearson
Comment Utility
The way to figure out details like which way to sort is to build this and run it with some test data and see which way it sorts.  You will probably want to consider some code like this:

p.getData().toString().compareTo(insert) == this.sortOrder && this.sortOrder != 0

The duplicates will want something like:

public void add(Object obj) {  
   .. Check for empty head of list (see earlier code) ...

  if (!permitsDuplicates) {
     // Do a loop similar to the one I wrote but now checking for compareTo(insert)==0
     // If you find an exact match, return without adding the item.
  }

  // If we get here we're going to be adding the item.  All we have to do is
  // put it in the right place.
  if (sortOrder == 0) {
      // this list isn't sorted ,so just add it to the front
      p = head ;
   } else {
      // Now do the loop I wrote earlier to find where to insert, considering the two possible sortOrder values.
   }

     // Add the new object into the list
     Object pNext = p.getNext() ;
     p.setNext(new Node(obj, pNext)) ;
}

I hope you don't find this too frustrating.  I'm trying to help you along in writing the code rather than just writing it all for you, so you can learn how this all really works.  In the long term it should be the greater help.

Doug
0
 

Author Comment

by:excalibuxo
Comment Utility
Thanks a lot for the help it's frustrating and challenging but I guess that the best way to learn something. I feel like am really getting somewhere with this though thanks for the help.
0
 

Author Comment

by:excalibuxo
Comment Utility
Ok I got my code working but am having problems figuring out the sortOrder. When I use test data  a b c d with
                        String insert = obj.toString() ;
                      while (p.getNext() != null && p.getData().toString().compareTo(insert) == -1 ) {
                           p = p.getNext() ;
                      }
                       // Add the new object into the list
                       Node pNext = p.getNext() ;
                       p.setNext(new Node(obj, pNext)) ;
                       size++;
                       }
i get a d c b which doesn't make sense in decreasing order it should be a b c d. When I try to code so as to sort in increasing order I get stuck because I don't have a getPrevious method in Node class or maybe am just looking at it wrong.
0
 

Author Comment

by:excalibuxo
Comment Utility
My code is very long and am not posting all of it here. I also have another section of it that am not very sure. Please refer to the Node class above. I have to create a lookup method according to this specifications

/* Search the List for an Object equal to obj and
 *   return true if found, false otherwise.
 *
 * In this context equal means that
 *   true is returned from the call to the equals method;
 *   it does not mean pointer equality.
 */
public boolean lookup(Object obj);

How do I go about coding this method an example would really be helpful.


            
0
 
LVL 26

Expert Comment

by:dpearson
Comment Utility
Sorry excalibuxo - turns out I mislead you by misreading the docs for compareTo.  It can return values greater than -1 or +1.

So this code would be closer to what you need for both sorting directions:
 
String insert = obj.toString() ;
		     Node p = head ;
		     if (p == null || p.getData().toString().compareTo(insert) * sortOrder > 0) {
		         // Empty list
		         head = new Node(obj, head) ;
		         return ;
		     }
	
		     // Scan the list to find where to insert
		     // Testing == -1 here depends on the sort order.  You will want to test == 1 to sort
		     // in the other direction and == 0 to check for duplicates.
		     while (p.getNext() != null && p.getNext().getData().toString().compareTo(insert) * sortOrder < 0 ) {
		          p = p.getNext() ;
		     }
	
		     // Add the new object into the list
		     Node pNext = p.getNext() ;
		     p.setNext(new Node(obj, pNext)) ;

Open in new window


I hope you can work to add some code for the unsorted case.

The lookup method should be pretty simple:

             public boolean lookup(Object obj) {
                   for (Node p = head ; p != null ; p = p.getNext()) {
                         if (p.getData().equals(obj))
                             return true ;
                   }
                  return false ;
             }

Once you have the lookup method, making sure you don't add an element when it's already in the list and the list is set to "not permitsDuplicates" should become one line of code calling this method.

Doug
0
Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

 

Author Comment

by:excalibuxo
Comment Utility
Awesome got that working. I am now trying to test all my methods but my getNext and getPrevious methods are acting up and I can't get them to print any thing therefore can't test em.

My methods are
public Object getNext(){
                
                Node present = head;
                if(present == null || present.getNext() == null){
                      return null;
                } else
                  
              present = present.getNext();
                //System.out.println(present);
              return present;
       
          }
          
          public Object getPrevious(){
                
                 Node p = head ;

               // Find p such that p.getNext() == present
               while (p != null && p.getNext() != present) {
                  p = p.getNext() ;
               }      

               // Move present back to p
               present = p ;
               //System.out.println(present);
               return present ;

                
          }

My test data is

LinkedList sl = new LinkedList(false, 1);

             String s1 = "jack";
             sl.add(s1);

             String s2 = "hello world";
             sl.add(s2);

             String s3 = "tomato";
             sl.add(s3);
             
             Object o;
             Object a;
         
             o = sl.getNext();           // Value of o is "hello world"
             System.out.println(o);
             a = sl.getPrevious(); // Value of o is "jack"
             System.out.println(a);
            
and the printout is

csci1902.lab3.Node@addbf1
csci1902.lab3.Node@42e816

Do you have any idea why this may not be working please refer to an earlier posting for the instructions. Thanks a lot for your help this is a really great forum.
0
 
LVL 26

Expert Comment

by:dpearson
Comment Utility
Step 1 to figuring this out is to fix the printouts.  If you call "println" on an object in Java, it calls it's toString() method.  Since Node hasn't got one it's printing out the default - which is the address of the object.

Try adding:
    public String toString() {
        return data == null ? "null" : data.toString() ;
    }

to the Node class.  This should make your print statements return something intelligible and hopefully let you figure out how things are working.

Doug
0
 

Author Comment

by:excalibuxo
Comment Utility
Awesome it worked, I was able to test my getNext and getPrevious methods of which I realized that my getNext method doesn't work even after afew hours of trying to tweak the code the best way I could do it. The instructions for the method were

/* Using an internally maintained pointer,
 *   return the contents stored at the node in the next position in the list.
 *
 *   E.g., the first time getNext() is called,
 *   it returns the contents of the first node in the list,
 *   the second time it's called, it returns the second item in the list, etc.
 *
 * If the list is empty, return null.
 * If the most recent call to getNext returned the last item in the list,
 *   and getPrevious has not been called since then,
 *   and no new items have been added to the end of the list, return null.
 *
 * When adding new items, the internal pointer should still point to the
 *   same item, even if doing so might cause its index position to change.
 *   If the current item is removed by a delete() call, simply reset the
 *   internal pointer to the beginning.
 */
public Object getNext();

my code is

public Object getNext(){
                
                Node p = head;
                if(present == null){
                return null;
          }
                while (p != null && p.getNext() != present) {
                  p = p.getNext() ;
               }      

           
          this.present = present.getNext();
          return this.present;
       
          }

where am I going wrong.
0
 
LVL 26

Expert Comment

by:dpearson
Comment Utility
Since the list itself has pointers to the next items (going forward down the list) there's no need to scan the list in the way you have to scan the list for getPrevious().

Also I noticed that the spec for the method asks it to return the data - not the Node.  Small point but important.  Anyway try these two.
 
public Object getNext(){
	        // If not initialized, start with head
		if (present == null)
			present = head ;
			
            if(present == null || present.getNext() == null){
                  return null;
            }
            
            present = present.getNext();
            return present.getData();
      }
      
      public Object getPrevious(){
             Node p = head ;

           // Find p such that p.getNext() == present
           while (p != null && p.getNext() != present) {
              p = p.getNext() ;
           }      

           // Move present back to p
           present = p ;
           return present != null ? present.getData() : null ;
      }

Open in new window


Hope that helps,

Doug
0
 

Author Comment

by:excalibuxo
Comment Utility
Wow that helps but when I tested the getNext method it seems to be jumping the very first data item on the list. I figured it is initially skipping the data item from what I need it to return. I tried fixing that by just returning present but when I do that then it doesn't move down the list. I tried to insert instruction for pointing to the head initially but it does the same thing. I guess I am wondering what I can do so that it stops skipping the very first data item on the List. Thanks alot dpearson.
0
 
LVL 26

Expert Comment

by:dpearson
Comment Utility
This will handle the initial case better:

              // If not initialized, start with head
            if (present == null) {
                  present = head ;
                        return present == null ? null : present.getData() ;
                }

replacing the first test in the current code.
0
 

Author Comment

by:excalibuxo
Comment Utility
It works perfectly so I am very curious as to the code you just added. What does it actually do. I think am almost getting done with this exercise I am on my last method which is really just a simple reset.

/* Reset the internal pointer used by the two above methods
 *   so that the next call to getNext()  
 *   returns the contents of the first Node in the list.
 */
public void reset();

this is my code which when I run it and call getNext it prints out the second element on the list which means it resets it to the second element  and not the first. Can you please tell me what I am doing wrong.

public void reset(){
                          present = head;
          }
0
 
LVL 26

Expert Comment

by:dpearson
Comment Utility
For this it's function is petty simple:

            if (present == null) {
                  present = head ;
                        return present == null ? null : present.getData() ;
                }

If the "present" pointer is not initialized, set it to the head (first element) in the list.
Then return (x)?a:b means the same as
    if (x) return a ;
    else return b;
so in this case
    if (present == null)
        return null ;
    else
        return present.getData();

Does that make more sense?

For the reset method, try "present = null".

Doug
0
 

Author Comment

by:excalibuxo
Comment Utility
Yap it makes sense I guess what really confused me was the (null ? null : present.getData();). So I have been testing my code now for quite some time but then I realized that all the code is getting sorted except the very first element on the list. I figured that I could maybe solve this by adding a dummy head so that everything after that dummy head would be sorted. I attempted to do this but I kept getting errors. I was wondering what would be the best way to take care of this problem.

0
 
LVL 26

Expert Comment

by:dpearson
Comment Utility
I seem to recall you were having that problem before.  Are you using this at the top of your add method:
                 Node p = head ;
                 if (p == null || p.getData().toString().compareTo(insert) * sortOrder > 0) {
                     // Empty list
                     head = new Node(obj, head) ;
                     return ;
                 }

It should handle inserts that need to go in front of the head element (which I think is what you're saying is failing).

Doug
0
 

Author Comment

by:excalibuxo
Comment Utility
Oh yeah but it has only the p == null part I don't how I missed that part I will update it and see how it runs.
0
 

Author Comment

by:excalibuxo
Comment Utility
Hurray it worked!!
Ok I think I am almost done but there is one little glitch Have been testing my getNext and getPrevious methods and i think the getPrevious is acting up a little bit Here is my printout stating the methods I called what the they should produce and separated by a space is what was produced.

Here is the string list:
hello world jack tomato

This is the printout

getNext called should produce hello world   hello world
getPrevious called should produce null   null
getNext called should hello world   hello world
getNext called should jack   jack
getPrevious called should produce hello world   hello world
getPrevious called should produce null   null
getPrevious called should produce null   tomato
getNext called should produce hello world   null
getNext called should produce jack   null
getNext called should produce tomato   null
getNext called should produce null   null
getPrevious called should produce tomato   jack
getPrevious called should produce jack   hello world
getPrevious called should produce hello world   null
getPrevious called should produce null   tomato

Any ideas?
0
 
LVL 26

Accepted Solution

by:
dpearson earned 500 total points
Comment Utility
It sounds like there's some specific end conditions that you need to handle.  This hinges on exactly what should happen when you call getPrevious() when the present point is null.  It sounds like you may need an extra condition:

if (present == null)
   return null ;

But for this level of detail you really need to just look at the state of the individual variables in each call and figure out what it's returning and why.  You're no longer working on the algorithms - it's just a matter of paying close attention to the end conditions (what happens when present=null or present.getNext() = null etc.)

Doug
0
 

Author Comment

by:excalibuxo
Comment Utility
Ok I will work on it am sure I will get it thank you very much.
0

Featured Post

IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

One of Google's most recent algorithm changes affecting local searches is entitled "The Pigeon Update." This update has dramatically enhanced search inquires for the keyword "Yelp." Google searches with the word "Yelp" included will now yield Yelp a…
Article by: Nadia
Linear search (searching each index in an array one by one) works almost everywhere but it is not optimal in many cases. Let's assume, we have a book which has 42949672960 pages. We also have a table of contents. Now we want to read the content on p…
Get a first impression of how PRTG looks and learn how it works.   This video is a short introduction to PRTG, as an initial overview or as a quick start for new PRTG users.
This demo shows you how to set up the containerized NetScaler CPX with NetScaler Management and Analytics System in a non-routable Mesos/Marathon environment for use with Micro-Services applications.

772 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!

Get 1:1 Help Now