9 Replies - 6107 Views - Last Post: 08 February 2011 - 08:11 AM Rate Topic: -----

#1 mistamutt  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 07-February 11

Writing a toString method for my LinkedList class

Posted 07 February 2011 - 08:53 PM

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


Is This A Good Question/Topic? 0
  • +

Replies To: Writing a toString method for my LinkedList class

#2 moobler  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 143
  • View blog
  • Posts: 224
  • Joined: 21-January 11

Re: Writing a toString method for my LinkedList class

Posted 07 February 2011 - 08:58 PM

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.
Was This Post Helpful? 0
  • +
  • -

#3 Guest_mistamutt*


Reputation:

Re: Writing a toString method for my LinkedList class

Posted 07 February 2011 - 09:46 PM

Alright, I thought the description would be enough but here it is:

public class LinkedList<E> {
	
	private static class LinkedNode<E>{
		private E item;
		private String key;
		private LinkedNode<E> next;
		
		private LinkedNode(E value, String a){
		item = value;
		key = a;
		next = null;
		}
		
		private LinkedNode(E value, String a, LinkedNode<E> reference){
		item = value;
		key = a;
		next = reference;
		}
		
		
		
	} // end of LinkedNode
	
	protected LinkedNode<E> head;
	protected LinkedNode<E> tail;
	protected int size;
	
	public LinkedList() { //constructor for an empty list
		head = null;
		tail = null;
		size = 0;
	}
	
	public void addFront(E value, String a){
		head = new LinkedNode<E>(value, a, head);
		if (tail == null) {
			tail = head;
		}	
	}
		
	public void addEnd(E value, String a){
		LinkedNode<E> newNode = new LinkedNode<E>(value, a, tail);
		tail.next = newNode;
		tail = newNode;
	}
	
	public boolean add(E value, String a){
		if (head != null){
			addEnd(value,a);
		} else {
			addFront(value,a);
		}
		size++;
		return true;
	}
	
	public int size(){
		return size;
	}
	
	public LinkedNode<E> get(int nodePosition){
		if (nodePosition >= 0){
			LinkedNode<E> result = head;
			while (nodePosition > 0){
				result = result.next;
				nodePosition--;
			}
			if (result == null) {
				System.out.println("Node does not exist");
				return null;
			} else {
				return result;
			}
		} else {
			System.out.println("You must enter a position greater to, or equal to 0.");
			return null;
		}
	}

	public LinkedNode<E> find(String findKey){
		LinkedNode<E> result = head;
		int position = 0;
		
		try {
			while (!result.key.equalsIgnoreCase(findKey)){
				result = result.next;
				position++;
			}
				if (result.key.equalsIgnoreCase(findKey)){
					System.out.println("'" + result.key +"' was found, with number " + result.item);
					return result;
				} else {
					return null;
				}
		} catch (NullPointerException fail) {
			System.out.println("Key was not found, node does not exist");
			return null;
		}
	}
	
	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();
	}
		
	
	
}


Was This Post Helpful? 0

#4 moobler  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 143
  • View blog
  • Posts: 224
  • Joined: 21-January 11

Re: Writing a toString method for my LinkedList class

Posted 07 February 2011 - 10:07 PM

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.
Was This Post Helpful? 1
  • +
  • -

#5 mistamutt  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 07-February 11

Re: Writing a toString method for my LinkedList class

Posted 07 February 2011 - 10:32 PM

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.
Was This Post Helpful? 0
  • +
  • -

#6 moobler  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 143
  • View blog
  • Posts: 224
  • Joined: 21-January 11

Re: Writing a toString method for my LinkedList class

Posted 07 February 2011 - 10:48 PM

View Postmistamutt, 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.
Was This Post Helpful? 0
  • +
  • -

#7 mistamutt  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 07-February 11

Re: Writing a toString method for my LinkedList class

Posted 07 February 2011 - 11:25 PM


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.
Was This Post Helpful? 0
  • +
  • -

#8 moobler  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 143
  • View blog
  • Posts: 224
  • Joined: 21-January 11

Re: Writing a toString method for my LinkedList class

Posted 07 February 2011 - 11:31 PM

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.
Was This Post Helpful? 0
  • +
  • -

#9 mistamutt  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 07-February 11

Re: Writing a toString method for my LinkedList class

Posted 08 February 2011 - 12:09 AM

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

Was This Post Helpful? 0
  • +
  • -

#10 moobler  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 143
  • View blog
  • Posts: 224
  • Joined: 21-January 11

Re: Writing a toString method for my LinkedList class

Posted 08 February 2011 - 08:11 AM

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).
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1