[mistamutt]

I'm trying to write a toString() method for a LinkedList class, written by me, that hold LinkedNodes that store Keys and Values. It works when there is only a single node in the list, but when there are more than one I get the following exception:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at java.util.Arrays.copyOf(Unknown Source)
	at java.lang.AbstractStringBuilder.expandCapacity(Unknown Source)
	at java.lang.AbstractStringBuilder.append(Unknown Source)
	at java.lang.StringBuffer.append(Unknown Source)
	at LinkedList.toString(class and line) // see below
	at AddressBook.main(class and line) //I took this out for reasons I don't want to discuss but it shouldn't matter

public String toString() {
		LinkedNode<E> node = head;
		StringBuffer str = new StringBuffer();
		
		while (node != null){
		str.append(node.key.toString() + " ");
		str.append(node.item.toString());
		node = node.next;
		}
		
		return str.toString();
	}

Is there a memory leak or something? Most of the code in this program I referenced from my instructor, and the example he gave us is really similar to our assignment, just that our nodes have to store a "key" string in addition to an "item" string. I've googled my fingers to the bone trying to search for more examples of overridden toString methods and couldn't find anything. Hopefully someone can point me in the right direction. Thanks in advance.

This post has been edited by mistamutt: 07 February 2011 - 08:53 PM

[moobler]

It's really hard to tell with just the code you posted. If we had the entire LinkedList class, we may be able to spot a problem.

[moobler]

Thanks for the rest of the code.

Your problem happens where you use the second constructor for LinkedNode. In addFront and addEnd you create a new node in which the next node is set to itself.

With that in mind, take a look at the toString method, where your end condition is to check for a null node. If your tail node always has itself as the next node, you will never leave that loop. Unless you're making a circular linked list of some sort, always make sure to set tail.next to null.

[mistamutt]

Hooray, it works now. Thanks for the help!

Any tips on writing a method that sorts the nodes by key? The only reference I could find on the internet was a sorting algorithm that sorted integers, and I need to sort alphabetically so that the name Bob would be printed before the name Jill, even if Jill was entered in first.

[moobler]

mistamutt, on 08 February 2011 - 12:32 AM, said:

Hooray, it works now. Thanks for the help!

Any tips on writing a method that sorts the nodes by key? The only reference I could find on the internet was a sorting algorithm that sorted integers, and I need to sort alphabetically so that the name Bob would be printed before the name Jill, even if Jill was entered in first.

Good news for you: your keys are String objects, and the String class implements the Comparable interface.

In short, this means that you can use the built in compareTo method like this:

String s1 = "Bob";
String s2 = "Jill";

int result = s1.compareTo(s2);

You can use result to determine the alphabetical ordering. If result is negative, then s1 is "less than" s2. If result is positive, then s1 is "greater than" s2. If result is zero, then s1.equals(s2).

Use the sorting algorithm you found, but replace any numerical comparisons with a call to compareTo.

[mistamutt]

public int sortList() {

int result;
LinkedNode<E> node = head;

String s1 = node.key;
String s2 = node.next.key;

result = s1.compareToIgnoreCase(s2);

return result;

}

When I print that out, it gives me 8? I thought it was supposed to be -1, 0, or 1?

I made it return an int because I wasn't getting results I expected after writing an algorithm to sort, so I wanted to see what compareToIgnoreCase was, and I found that it was 8? I read your compareTo API link, but I need it to ignore the case of the string because the users enter the data and might capitalize the first letter of the key, or might not and vice versa.

[moobler]

Both compareTo and compareToIgnoreCase use the same format:

Quote

If result is negative, then s1 is "less than" s2. If result is positive, then s1 is "greater than" s2. If result is zero, then s1.equals(s2).

The actual value doesn't matter, only its relation to 0. If it returned 8, then it means s1 was greater than s2.

[mistamutt]

Hmm, I can't seem to implement this correctly.

public void sortList(){
		int result;		
		LinkedNode<E> temp;		
		
		for (LinkedNode<E> node = head; node.next != null; node = node.next) {
			String s1 = node.key;
			String s2 = node.next.key;
						
			result = s1.compareToIgnoreCase(s2);

		if (result > 0) { // node is bigger than node.next, and the nodes are supposed to be sorted from lesser to greater
			temp = node; // store first node in temp variable
			node = node.next; //move node.next to node, essentially moving it 'backwards' in the lest or towards the left
			node.next = temp; //now that node is what was previously node.next, set node.next to what used to be node
                }
                }
}

edit: sorry for the indentations being all out of whack hope you can read it okay
Is this resulting in an infinite loop? My program seems to just do nothing after I call the method and print in my other class. Trying to get this down before moving on to the other cases.

This post has been edited by mistamutt: 08 February 2011 - 12:10 AM

[moobler]

Your node swapping part is a bit off - after the first swap, there will be a loop created between node and node.next that will never exit.

Swapping nodes is a bit different than swapping values. Here's a simple example:

List = node1 -> node2 -> node3 -> node4 -> null

Now let's say we want to swap nodes 2 and 3. Here's some pseudocode:

node1.next = node3
node3.next = node2
node2.next = node4

Which gives us List = node1 -> node3 -> node2 -> node4 -> null

Notice how we never directly change any of the nodes, we only change which nodes they point to. That is the major difference between this sort of thing and swapping int variables.

It's important to keep track of the previous node, as well as the current one when working with a linked list. You'll also need at least one special case (to handle swapping the first two nodes, where there is no previous one).