Join 300,470 Java Programmers for FREE! Get instant access to thousands of Java experts, tutorials, code snippets, and more! There are 1,739 people online right now. Registration is fast and FREE... Join Now!
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.
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
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());
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;
//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;
//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;
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!
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;
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...
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.
I rechecked your code. I saw the new linked list (secondList) as a parameter in the call to the method. However, you didn't ever assign anything to the new list. This may be your problem. On top of your infinite loop problem.
I rechecked your code. I saw the new linked list (secondList) as a parameter in the call to the method. However, you didn't ever assign anything to the new list. This may be your problem. On top of your infinite loop problem.
Thank you so much for your help! You really dont know how much it means. I fixed the infinite loop and am trying to figure out how exactly to assign the new list. Each time I try my complier throws an error (Eclipse-Ganymeade)
I rechecked your code. I saw the new linked list (secondList) as a parameter in the call to the method. However, you didn't ever assign anything to the new list. This may be your problem. On top of your infinite loop problem.
Thank you so much for your help! You really dont know how much it means. I fixed the infinite loop and am trying to figure out how exactly to assign the new list. Each time I try my complier throws an error (Eclipse-Ganymeade)
If its not alot of trouble is there anyway you could comment my code where my trouble is and any suggestions to fix it. I am SO LOST with these Linked List problems. Recursion was pie to me! I wished I could just use a recursive call! ha! My instructor wouldn't allow it though! I am in an accelerated program that covers SO MUCH information one night a week and its limited on instructor guidance. I really appreciate you guys helping. Add me on your myspace if you want!
Linked lists are an issue in Java because they are faked, without pointers I don't understand the point of implementing them, but I've had Java linked list assignments in Univ classes.
Linked lists are an issue in Java because they are faked, without pointers I don't understand the point of implementing them, but I've had Java linked list assignments in Univ classes.
QUOTE
No edit button! Cant re name post! UGH!
rename it to what?
I was going to beg!! haha! Or put "Will show boobs for code" haha! Kidding Willy! I dont know, something with all my probably wrong updates. Ive changed everything back and forth and back again twice! haha!
while(current !=null &&!found) {// this was missing if(current.info.equals(item)) found= true;
else { trailCurrent = current; current = current.link; // instead of first.link which is an endless loop i++; } }// this is ending while if(found)
the {} around the while were a little offset, the lists are not displaying properly, but i think it's a start, i'll take a look at the rest and see if there's anything that stands out
Well I took out some of your code, rewrote some of it and put it into a format that you can work with. I put in some comments to show you what I had done.
The idea here is that you loop through the list until you find your node, from that point on you have to write the node value to the second list and then remove from the current list. The result is your two lists split.
java
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--; // <-- Not sure why you decrement if you are just setting to zero count = 0; } else { current = first; found = false; i = 1;
// Loop until you find the current node while(current != null &&!found) if(current.info.equals(item)) { found = true; } else { trailCurrent = first; current = current.link; i++; }
// Once found, go into a loop from that node forward, recording each to the second list // and deleting from the original list if (found) { while (current != null) { // Insert into the second list secondList.insertLast(current.info); // Get a reference to the next node before deleting this one LinkedListNode<T> current2 = current.link;
// Delete this one and then reset the current node to the next one in the chain deleteNode(current.info); current = current2; } } else { System.out.println("Item to be split at is not in the list."); first=null; last=null; count=0; } } }
You will notice that I get a bit tricky there in that second while loop where I first have to record the next node FIRST then delete the current node, but then set the current node to the next node. I have to make sure I get a reference to that next node first because if I delete the current node, then I have nothing to get reference to the next one in the list.
Hope this helps you out and is what you wanted.
Oh and if it is what you wanted, I am sure jacob could use a good old flash of nudity because he is soooooo soooo lonely.
"At DIC we be node splitting code ninjas.... we also split our cash winnings at the DIC casino! Jackpots are now up to 250,000 doughnuts! Play now!"
This post has been edited by Martyr2: 11 Oct, 2008 - 04:34 PM
You are a code writing GOD! Wow! I would have never got that second Loop!! EVER!! haha! Im all batty eyed at you now! Hope you know that! Impressive! Thank you so much for taking your time to help me and comment it out so I can figure out what I was doing wrong!
The issue that I saw was when it finds the matching item in the list. You never build the secondList from that point forward. So with the addition of a loop once the item has been found this will add the remaining items to the second list.
Hope that helps. If not I'm sure one of the three answers you have been given will get you going.
java
public void splitAt(LinkedListClass<T> secondList, T item) { LinkedListNode<T> current; LinkedListNode<T> trailCurrent;
else { //need to iterate through the current list and add them items into //the second list while(current != null) { //Check if there is anything in the list if (secondList.length() == 0) secondList.insertFirst(current.info); else secondList.insertLast(current.info);
current = current.link; }
} } else { System.out.println("Item to be split at is " + "not in the list."); first=null; last=null; count=0;
The issue that I saw was when it finds the matching item in the list. You never build the secondList from that point forward. So with the addition of a loop once the item has been found this will add the remaining items to the second list.
Hope that helps. If not I'm sure one of the three answers you have been given will get you going.
java
public void splitAt(LinkedListClass<T> secondList, T item) { LinkedListNode<T> current; LinkedListNode<T> trailCurrent;
else { //need to iterate through the current list and add them items into //the second list while(current != null) { //Check if there is anything in the list if (secondList.length() == 0) secondList.insertFirst(current.info); else secondList.insertLast(current.info);
current = current.link; }
} } else { System.out.println("Item to be split at is " + "not in the list."); first=null; last=null; count=0;
}
} }
Wow! Thank you so much!! I m looking over yours, Martyrs and mine and trying to figure out all my mistakes!! It helps SO MUCH WHERE YOU GUYS COMMENTED! Thank you!! MY HEROES!!!
Linked lists are an issue in Java because they are faked, without pointers I don't understand the point of implementing them, but I've had Java linked list assignments in Univ classes.
Java is only pointers but hidden fro the user...
C++ has real object creation
CODE
int main() { Rectangle x; // this creates a new Rectangle called x }
and the object x will be destroy when the method will exit
in Java
CODE
int main() { Rectangle x; }
does not create a new Rectangle... the C++ equivalent is
CODE
int main() { Rectangle *x; }
So just an uninitialzed pointer to a Rectangle object
So, despiste all your claims... Java is only and only pointers... hidden from the user but this is what they are
Forum Index:
Programming Help |
C and C++ |
VB6 |
Java |
VB.NET |
C# |
ASP.NET |
PHP |
ColdFusion |
Perl and Python |
Ruby |
Databases |
Other Languages |
Game Programming |
Mobile Development |
Software Development |
Computer Science |
Industry News |
Programming Tutorials |
C++ Tutorials |
Visual Basic Tutorials |
Java Tutorials |
VB.NET Tutorials |
C# Tutorials |
Linux Tutorials |
PHP Tutorials |
ColdFusion Tutorials |
Windows Tutorials |
HTML/JavaScript Tutorials |
CSS Tutorials |
Flash Tutorials |
Web Promotion Tutorials |
Graphic Design & Photoshop Tutorials |
Software Development Tutorials |
Database Tutorials |
Other Language Tutorials |
ASP.NET Tutorials |
Game Programming Tutorials |
WPF & Silverlight Tutorials |
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:
| 
