Welcome to Dream.In.Code
Getting Java Help is Easy!

Join 132,145 Java Programmers for FREE! Get instant access to thousands of Java experts, tutorials, code snippets, and more! There are 2,015 people online right now. Registration is fast and FREE... Join Now!




This is the method I need help with: Cleaned up

2 Pages V  1 2 >  
Closed TopicStart new topic

This is the method I need help with: Cleaned up, Problem with assigning to new list.

absynthe
post 10 Oct, 2008 - 11:54 AM
Post #1


D.I.C Addict

****
Joined: 20 Sep, 2008
Posts: 801



Thanked 5 times
My Contributions


wub.gif My code just will not work!! Any help would be appreciated! My problem is in the last method SplitAt. These are the conditions set and my code:

Splitting a Linked List at a Given Node, into Two Sublists
a. Add the following as an abstract method to the class
LinkedListClass:

public void splitAt (LinkedListClass<T> secondList, T item);
//This method splits the list at the node with the info item into two sublists.
//Precondition: The list must exist.
//Postcondition: first and last point to the first and last nodes of the first sublist,
// respectively. secondList.first and secondList.last point to the first
// and last nodes of the second sublist.

Consider the following statements:

UnorderedLinkedList<Integer> myList;
UnorderedLinkedList<Integer> otherList;

Suppose myList points to the list with the elements 34, 65, 18, 39, 27, 89, and 12 (in this order). The statement

myList.splitAt(otherList, 18);
splits myList into two sublists: myList points to the list with elements 34 and 65, and otherList points to the sublist with elements 18, 39, 27, 89, and 12.

b. Provide the definition of the method splitAt in the class UnorderedLinkedList. Also write a program to test your method.






CODE




public void splitAt(LinkedListClass<T> secondList, T item)
    {
    LinkedListNode<T> current;        //variables to traverse the list
    LinkedListNode<T> trailCurrent = null;
    
    
    int i;
    boolean found;            //variables
    
    
    if (first==null)//List Empty
  
    {        
   System.err.println("The List is Empty.");
       first = null;            //if the list is empty
       last = null;
       count=0;
                                               }
              else
    {
        current = first;
        found=false;
        i=1;
       
               while(current !=null &&!found)

       if(current.info.equals(item))
       found= true;
               
       else
   {
       trailCurrent = first;
       current = current.link;            //loop
       i++;
                   
               }
       
        if(found)
    {
        if(first==current)
    {
        trailCurrent=first;
       trailCurrent=last;                              
       trailCurrent.link=last.link;        //set current
        count++;
                 
       return;
                       }
           
       else
   {
       current=first;
       trailCurrent.link = last.link; //set trailCurrent to
                current = first.link;
            last.link=null;
       count = count - i+1;
       count = i-1;
       count++;
        i++;
        return;
            }
                                  }
else  
    {
       System.out.println("Item to be split at is "
           + "not in the list.");
        first=null;
        last=null;
        count = 0;
        count++;
         return;
       }
      }
    }
       
  }
    


This post has been edited by absynthe: 11 Oct, 2008 - 11:19 AM
User is online!Profile CardPM

Go to the top of the page

absynthe
post 10 Oct, 2008 - 03:27 PM
Post #2


D.I.C Addict

****
Joined: 20 Sep, 2008
Posts: 801



Thanked 5 times
My Contributions


I dont have a test program at all. The program is supposed to prompt for user input of numbers. (it does) Take the input and end at input of -999 (it does). Then it asks user where it wants to split list (it does). When I enter a number it does nothing after that. I am going to post updated code and see if that helps along with all the classes. Thanks!


This is the class to prompt:

CODE

import java.util.*;

public class Ch16_ProgEx6
{
    static Scanner console = new Scanner(System.in);

    public static void main(String[] args)
    {
        UnorderedLinkedList<Integer> list
                          = new UnorderedLinkedList<Integer>();
        UnorderedLinkedList<Integer> subList =
                          new UnorderedLinkedList<Integer>();

        Integer num;

        System.out.println("Enter integers ending with -999.");

        num = console.nextInt();

        while (num != -999)
        {
            list.insertLast(num);
            num = console.nextInt();
        }

        System.out.println();

        System.out.println("list: ");
        list.print();
        System.out.println();
        System.out.println("Length of list: " + list.length());


        System.out.print("Enter the number at which to split list: ");

        num = console.nextInt();

        list.splitAt(subList, num);

        System.out.println("Lists after splitting list");

        System.out.print("list: ");
        list.print();
        System.out.println();
        System.out.println("Length of list: " + list.length());

        System.out.print("sublist: ");
        subList.print();
        System.out.println();
        System.out.println("Length of sublist: " + subList.length());
    }
}


This is the ADT:

CODE
public interface LinkedListADT<T> extends Cloneable
{
    public Object clone();
       //Returns a copy of objects data in store.
       //This method clones only the references stored in
       //each node of the list. The objects that the
       //list nodes point to are not cloned.

    public boolean isEmptyList();
       //Method to determine whether the list is empty.
       //Postcondition: Returns true if the list is empty;
       //               false otherwise.

    public void initializeList();
       //Method to initialize the list to an empty state.
       //Postcondition: The list is initialized to an empty
       //               state.

    public void print();
       //Method to output the data contained in each node.

    public int length();
       //Method to return the number of nodes in the list.
       //Postcondition: The number of nodes in the list is
       //               returned.

    public T front();
       //Method to return a reference of the object containing
       //the data of the first node of the list.
       //Precondition: The list must exist and must not be empty.
       //Postcondition: The reference of the object that
       //               contains the info of the first node
       //               is returned.

    public T back();
       //Method to return a reference of object containing
       //the data of the last node of the list.
       //Precondition: The list must exist and must not be empty.
       //Postcondition: The reference of the object that
       //               contains the info of the last node
       //               is returned.

    public boolean search(T searchItem);
       //Method to determine whether searchItem is in the list.
       //Postcondition: Returns true if searchItem is found
       //               in the list; false otherwise.

    public void insertFirst(T newItem);
       //Method to insert newItem in the list.
       //Postcondition: newItem is inserted at the
       //               beginning of the list.

    public void insertLast(T newItem);
       //Method to insert newItem at the end of the list.
       //Postcondition: newItem is inserted at the end
       //               of the list.

    public void deleteNode(T deleteItem);
       //Method to delete deleteItem from the list.
       //Postcondition: If found, the node containing
       //               deleteItem is deleted from the
       //               list.

    public void splitAt(LinkedListClass<T> secondList, T item);
}




This is the linked list class:




CODE
import java.util.NoSuchElementException;

public abstract class LinkedListClass<T> implements LinkedListADT<T>
{
    protected class LinkedListNode<T> implements Cloneable
    {
        public T info;
        public LinkedListNode<T> link;

           //Default constructor
           //Postcondition: info = null; link = null;
        public LinkedListNode()
        {
            info = null;
            link = null;
        }

           //Constructor with parameters
           //This method sets info pointing to the object to
           //which elem points to and link is set to point to
           //the object to which ptr points to.
           //Postcondition:  info = elem; link = ptr;
        public LinkedListNode(T elem, LinkedListNode<T> ptr)
        {
            info = elem;
            link = ptr;
        }

           //Returns a copy of objects data in store.
           //This method clones only the references stored in
           //the node. The objects that the nodes point to
           //are not cloned.
        public Object clone()
        {
            LinkedListNode<T> copy = null;

            try
            {
                copy = (LinkedListNode<T>) super.clone();

            }
            catch (CloneNotSupportedException e)
            {
                return null;
            }

            return copy;
        }

           //Method to return the info as a string.
           //Postcondition: info as a String object is
           //               returned.
        public String toString()
        {
            return info.toString();
        }
    } //end class LinkedListNode


    public class LinkedListIterator<T>
    {
        protected LinkedListNode<T> current;  //variable to
                                              //point to the
                                              //current node in
                                              //list
        protected LinkedListNode<T> previous; //variable to
                                              //point to the
                                              //node before the
                                              //current node

           //Default constructor
           //Sets current to point to the first node in the
           //list and sets previous to null.
           //Postcondition: current = first; previous = null;
        public LinkedListIterator()
        {
            current = (LinkedListNode<T>) first;
            previous = null;
        }

           //Method to reset the iterator to the first node
           //in the list.
           //Postcondition: current = first; previous = null;
        public void reset()
        {
            current = (LinkedListNode<T>) first;
            previous = null;
        }

           //Method to return a reference of the info of the
           //current node in the list and to advance iterator
           //to the next node.
           //Postcondition: previous = current;
           //               current = current.link;
           //               A refrence of the current node
           //               is returned.
        public T next()
        {
            if (!hasNext())
                throw new NoSuchElementException();

            LinkedListNode<T> temp = current;

            previous = current;
            current = current.link;

            return temp.info;
        }

            //Method to determine whether there is a next
            //element in the list.
            //Postcondition: Returns true if there is a next
            //               node in the list; otherwise
            //               returns false.
        public boolean hasNext()
        {
            return (current != null);
        }

           //Method to remove the node currently pointed to
           //by the iterator.
           //Postcondition: If iterator is not null, then the
           //               node that the iterator points to
           //               is removed. Otherwise the method
           //               throws NoSuchElementException.
        public void remove()
        {
            if (current == null)
                throw new NoSuchElementException();

            if (current == first)
            {
                first = first.link;
                current = (LinkedListNode<T>) first;
                previous = null;

                if (first == null)
                    last = null;
            }
            else
            {
                previous.link = current.link;

                if (current == last)
                {
                    last = first;
                    while (last.link != null)
                        last = last.link;
                }

                current = current.link;
            }

            count--;
        }

           //Method to return the info as a string.
           //Postcondition: info as a String object is returned.
        public String toString()
        {
            return current.info.toString();
        }

    } //end class LinkedListIterator


       //Instance variables of the class LinkedListClass
    protected LinkedListNode<T> first; //variable to store the
                                       //address of the first
                                       //node of the list
    protected LinkedListNode<T> last;  //variable to store the
                                       //address of the last
                                       //node of the list
    protected int count;  //variable to store the number of
                          //nodes in the list

       //Default constructor
       //Initializes the list to an empty state.
       //Postcondition: first = null, last = null,
       //               count = 0
    public LinkedListClass()
    {
        first = null;
        last = null;
        count = 0;
    }

       //Method to determine whether the list is empty.
       //Postcondition: Returns true if the list is empty;
       //               false otherwise.
    public boolean isEmptyList()
    {
        return (first == null);
    }

       //Method to initialize the list to an empty state.
       //Postcondition: first = null, last = null,
       //               count = 0
    public void initializeList()
    {
        first = null;
        last = null;
        count = 0;
    }

       //Method to output the data contained in each node.
    public void print()
    {
        LinkedListNode<T> current; //variable to traverse
                                   //the list

        current = first;    //set current so that it points to
                            //the first node
        while (current != null) //while more data to print
        {
            System.out.print(current.info + " ");
            current = current.link;
        }
    }//end print

       //Method to return the number of nodes in the list.
       //Postcondition: The value of count is returned.
    public int length()
    {
        return count;
    }

       //Method to return a reference of the object containing
       //the data of the first node of the list.
       //Precondition: The list must exist and must not be empty.
       //Postcondition: The reference of the object that
       //               contains the info of the first node
       //               is returned.
    public T front()
    {
        return first.info;
    }

        //Method to return a reference of object containing
        //the data of the last node of the list.
        //Precondition: The list must exist and must not be empty.
        //Postcondition: The reference of the object that
        //               contains the info of the last node
        //               is returned.
    public T back()
    {
        return last.info;
    }

       //Returns a copy of objects data in store.
       //This method clones only the references stored in
       //each node of the list. The objects that the
       //list nodes point to are not cloned.
    public Object clone()
    {
        LinkedListClass<T> copy = null;

        try
        {
            copy = (LinkedListClass<T>) super.clone();

        }
        catch (CloneNotSupportedException e)
        {
            return null;
        }

            //If the list is not empty clone each node of
            //the list.
        if (first != null)
        {
               //Clone the first node
            copy.first = (LinkedListNode<T>) first.clone();
            copy.last = copy.first;

            LinkedListNode<T> current;

            if (first != null)
                current = first.link;
            else
                current = null;

               //Clone the remaining nodes of the list
            while (current != null)
            {
                copy.last.link =
                        (LinkedListNode<T>) current.clone();
                copy.last = copy.last.link;
                current = current.link;
            }
        }

        return copy;
    }

       //Method to return an iterator of the list.
       //Postcondition: An iterator is instantiated and
       //               returned.
    public LinkedListIterator<T> iterator()
    {
        return new LinkedListIterator<T>();
    }

       //Method to determine whether searchItem is in
       //the list.
       //Postcondition: Returns true if searchItem is found
       //               in the list; false otherwise.
    public abstract boolean search(T searchItem);

       //Method to insert newItem in the list.
       //Postcondition: first points to the new list
       //               and newItem is inserted at the
       //               beginning of the list. Also,
       //               last points to the last node and
       //               count is incremented by 1.
    public abstract void insertFirst(T newItem);

       //Method to insert newItem at the end of the list.
       //Postcondition: first points to the new list and
       //               newItem is inserted at the end
       //               of the list. Also, last points to
       //               the last node and
       //               count is incremented by 1.
    public abstract void insertLast(T newItem);

       //Method to delete deleteItem from the list.
       //Postcondition: If found, the node containing
       //               deleteItem is deleted from the
       //               list. Also, first points to the first
       //               node, last points to the last
       //               node of the updated list, and count
       //               is decremented by 1.
    public abstract void deleteNode(T deleteItem);

    public abstract void splitAt(LinkedListClass<T> secondList, T item);
}



And this is the UnorderedLinked Class with the very last method the one being Im stuck on. The SplitAt Method.

CODE
public class UnorderedLinkedList<T> extends LinkedListClass<T>
{
       //Default constructor
    public UnorderedLinkedList()
    {
        super();
    }

        //Method to determine whether searchItem is in
        //the list.
        //Postcondition: Returns true if searchItem is found
        //               in the list; false otherwise.
    public boolean search(T searchItem)
    {
        LinkedListNode<T> current; //variable to traverse
                                   //the list
        boolean found;

        current = first;  //set current to point to the first
                          //node in the list

        found = false;    //set found to false

        while (current != null && !found) //search the list
            if (current.info.equals(searchItem)) //item is found
                found = true;
            else
               current = current.link; //make current point to
                                       //the next node
        return found;
    }

        //Method to insert newItem in the list.
        //Postcondition: first points to the new list
        //               and newItem is inserted at the
        //               beginning of the list. Also,
        //               last points to the last node and
        //               count is incremented by 1.
    public void insertFirst(T newItem)
    {
        LinkedListNode<T> newNode;     //variable to create the
                                    //new node

        newNode =
           new LinkedListNode<T>(newItem, first); //create and
                                       //insert newNode before
                                       //first

        first = newNode;   //make first point to the
                           //actual first node

        if (last == null)   //if the list was empty, newNode is
                            //also the last node in the list
            last = newNode;

        count++;     //increment count
    }

        //Method to insert newItem at the end of the list.
        //Postcondition: first points to the new list and
        //               newItem is inserted at the end
        //               of the list. Also, last points to
        //               the last node and
        //               count is incremented by 1.
    public void insertLast(T newItem)
    {
        LinkedListNode newNode; //variable to create the
                                //new node

        newNode =
           new LinkedListNode(newItem, null);  //create newNode

        if (first == null)  //if the list is empty, newNode is
                            //both the first and last node
        {
            first = newNode;
            last = newNode;
        }
        else     //if the list is not empty, insert
                 //newNode after last
        {
            last.link = newNode; //insert newNode after last
            last = newNode;      //set last to point to the
                                 //actual last node
        }

        count++;
    }//end insertLast

        //Method to delete deleteItem from the list.
        //Postcondition: If found, the node containing
        //               deleteItem is deleted from the
        //               list. Also, first points to the first
        //               node, last points to the last
        //               node of the updated list, and count
        //               is decremented by 1.
    public void deleteNode(T deleteItem)
    {
        LinkedListNode<T> current; //variable to traverse
                                   //the list
        LinkedListNode<T> trailCurrent; //variable just
                                        //before current
        boolean found;

        if ( first == null)    //Case 1; the list is empty
            System.err.println("Cannot delete from an empty "
                             + "list.");
        else
        {
            if (first.info.equals(deleteItem)) //Case 2
            {
                first = first.link;

                  if (first == null)  //the list had only one node
                     last = null;
                  count--;
               }
            else  //search the list for the given info
            {
                found = false;
                trailCurrent = first; //set trailCurrent to
                                      //point to the first node
                current = first.link; //set current to point to
                                      //the second node

                while (current != null && !found)
                {
                    if (current.info.equals(deleteItem))
                        found = true;
                    else
                    {
                        trailCurrent = current;
                        current = current.link;
                    }
                }//end while

                if (found) //Case 3; if found, delete the node
                {
                    count--;
                    trailCurrent.link = current.link;

                    if (last == current)  //node to be deleted
                                          //was the last node
                       last = trailCurrent;  //update the value
                                             //of last
                }
                else
                   System.out.println("Item to be deleted is "
                                    + "not in the list.");
            }//end else
        }//end else
    }//end deleteNode


    public void splitAt(LinkedListClass<T> secondList, T item)
    {
     LinkedListNode<T> current;
     LinkedListNode<T> trailCurrent;
    
     int i;
     boolean found;
    
     if (first==null)
     {
    System.out.println("Empty.");
    first=null;
    last=null;
    count--;
    count=0;
     }
     else
     {
         current=first;
         found=false;
         i=1;
        
         while(current !=null &&!found)
             if(current.info.equals(item))
            
                found= true;
                
                else
                {
                    trailCurrent=first;
                    current=first;
                    i++;
                }
         if(found)
         {
             if(first==current)
             {
                 first.link=first;
                 last.link=last;
                    count--;
                 count=0;
                
             }
            
             else
             {
                 first.link=current;
                 last.link=last;
                
                 last=null;
                 count = count- i+1;
                 count = i-1;
             }
         } else  {
            System.out.println("Item to be split at is "
                + "not in the list.");
             first=null;
             last=null;
             count=0;
            
        }

                
                    
         }
             }
        
     }
        
    



Any help or just advice would be fine. Im not the best at Java, better at VB. Am completely stumped! Thanks so much!

Mod edit - Fixed code tags.
User is online!Profile CardPM

Go to the top of the page

absynthe
post 10 Oct, 2008 - 06:49 PM
Post #3


D.I.C Addict

****
Joined: 20 Sep, 2008
Posts: 801



Thanked 5 times
My Contributions


When I run the program its supposed to get the user input to form the list (series of numbers). Then Split the list at given node defined by another user prompt. When I run it the program prompts and the input is good. When it gives me the sublist back and its size its wrong. This is the response:

Lists after splitting list
list: 1 2 3 4
Length of list: 1
sublist:
Length of sublist: 0


This is the SplitAt Method:

CODE
public void splitAt(LinkedListClass<T> secondList, T item)
    {
     LinkedListNode<T> current;            //variables to traverse the list
     LinkedListNode<T> trailCurrent = null;
    
                 int i;
                 boolean found;                //variables
                int number;
                 if (first==null)
     {                 first=null;                            
    System.err.println("Empty.");
                 first=null
                 last=null;
                 count=0;
                                    }
     else
     {
         current=first;
         found=false;
         i=1;
    while(current !=null &&!found)
     if(current.info.equals(item))
               found= true;
                
    else
    {
        trailCurrent = current;
        current = first.link;
        i++;
                }
     if(found)
         {
        if(first==current)
    {
        first.link=first;
        last.link=last;                              
    trailCurrent=last.link;        //set current
    current=current.link;
           count--;
        count=0;
        return;
             }
            
    else
   {
     current=first.link;
     trailCurrent = last.link; //set trailCurrent to
      current = current.link;
     last.link=null;
    count = count- i+1;
     count = i-1;
     }
         }
else
{
  System.out.println("Item to be split at is "
  + "not in the list.");
    first=null;
    last=null;
    count=0;
    count--;
        }
     }
    }
   }



Any suggestions?
User is online!Profile CardPM

Go to the top of the page

absynthe
post 11 Oct, 2008 - 05:42 AM
Post #4


D.I.C Addict

****
Joined: 20 Sep, 2008
Posts: 801



Thanked 5 times
My Contributions


The trouble with the code is in the very LAST METHOD. Not anywhere else. The rest of the code is fine. At the SplitAT method. Not a single response. bummer...
User is online!Profile CardPM

Go to the top of the page

JeroenFM
post 11 Oct, 2008 - 06:12 AM
Post #5


D.I.C Head

Group Icon
Joined: 30 Jun, 2008
Posts: 182



Thanked 9 times

Dream Kudos: 100
My Contributions


You have a logic error in the loop in your splitAt method:

java

while(current !=null &&!found)
if(current.info.equals(item))
found= true;
else {
trailCurrent=first;
current=first;
i++;
}


What this does is keep setting current to the first element in your list, thereby causing an infinite loop unless the very first element matches.

Try current=current.link instead, it should give you some progress.

And please, use the Edit button next time.
User is offlineProfile CardPM

Go to the top of the page

>>codingGeek<<
post 11 Oct, 2008 - 06:18 AM
Post #6


New D.I.C Head

*
Joined: 12 Jun, 2008
Posts: 28



Thanked 1 times
My Contributions


In order to split the list, you have to have to two lists. Did I miss it in your code where you create the new list.

In your current list, iterate to the node of interest, assign your new list to point to this node. Then reassign the pointers on the node of interest to point to your new list's starting node, or null. Finally, reassign the pointers on your current list, which previously pointed to the node to point to an ending node or null.

User is offlineProfile CardPM

Go to the top of the page