Thread: Singly Linked List - Sort Method

I really hate linkedlists. I've been stairing at this code for 3 days now and I can't seem to create a insertSort method. It has an insertFromBack and insertFromFront.
I'm trying to make a method that sets the current nodes nextNode to the new insertItem node and linking the insertItem node with the current.nextNode as it's nextnode.
What the hell did I just even ask? I really hate linked lists...
Anyways, a more concise question is how to compare the new T object with the current nodes T data variable.

I tried implementing Comparable...

return data.compareTo(node.data);

public class List <T> {
	private ListNode<T> firstNode;
	private ListNode<T> lastNode;
	private String name;
 
	public List(){
		this("list");
	}
 
	public List(String listName){
		name = listName;
		firstNode = lastNode = null;
	}
 
	public void insertAfter(T insertItem) {		
		ListNode<T> current = firstNode;
		if(isEmpty()){
			firstNode = lastNode = new ListNode<T>(insertItem); //firstnode = lastnode because the list is empty.
		}else{
			while(current != null){	
				if(current.getData() <= insertItem){  //my question is how do i compare the data, to the current data I just entered for the T insertItem
					current.nextNode = new ListNode<T>(insertItem, current.nextNode);					
				}
			}
		}
	}
 
	public void insertAtFront(T insertItem){
		if(isEmpty()){
			firstNode = lastNode = new ListNode<T>(insertItem); //firstnode = lastnode because the list is empty.
		}else
			firstNode = new ListNode<T>(insertItem, firstNode);
	}
 
	public void insertAtBack(T insertItem){
		if(isEmpty()){
			firstNode = lastNode = new ListNode<T>(insertItem); //firstnode = lastnode because the list is empty.
		}else
			lastNode = lastNode.nextNode = new ListNode<T>(insertItem);
	}
 
	public T removeFromFront() throws EmptyListException{
		if(isEmpty())
			throw new EmptyListException(name);
 
		T removedItem = firstNode.data;
 
		if(firstNode == lastNode)
			firstNode = lastNode = null;
		else
			firstNode = firstNode.nextNode;
 
		return removedItem;		
	}
 
	public T removeFromBack() throws EmptyListException{
		if(isEmpty())
			throw new EmptyListException(name); 
		//if no exception is thrown
		T removedItem = lastNode.data;
 
		if(firstNode == lastNode)
			firstNode = lastNode = null;
		else{
			ListNode<T> current = firstNode;
 
			while(current.nextNode != lastNode)
				current = current.nextNode;			
			lastNode = current;
			current.nextNode = null;
		}
 
		return removedItem;			
	}
 
	public boolean isEmpty(){
		return firstNode == null;
	}
 
	public void print(){
		if(isEmpty()){
			System.out.printf("Empty %s\n", name);
			return;
		}
 
		System.out.printf("The %s is: ", name);
		ListNode<T> current = firstNode;
 
		while(current!= null){
			System.out.printf("%s ",  current.data);
			current = current.nextNode;
		}
 
		System.out.printf("\n");
	}
 
}
 
public class ListNode< T > {
	T data;
	ListNode< T > nextNode;
 
	ListNode(T object){
		this(object, null);
	}
 
	ListNode(T object, ListNode<T> node){
		data = object;
		nextNode = node;
	}
 
	T getData(){
		return data;
	}
 
	ListNode<T> getNext(){
		return nextNode;
	}
}
 
//custom exception
public class EmptyListException extends RuntimeException {
 
	public EmptyListException(){
		this("list");
	}
 
	public EmptyListException( String name){
		super(name+ " is empty");
	}
}
 
 
public class ListDriver {
	public static void main(String[] args){
		List<Integer> list = new List<Integer>();
 
		list.insertAtFront(-1);
		list.print();
		list.insertAtFront(0);
		list.print();
		list.insertAtBack(1);
		list.print();
		list.insertAtBack(5);
		list.print();
 
		try{
 
			int removedItem = list.removeFromFront();
			System.out.printf("\n%d removed \n", removedItem);
			list.print();
			removedItem = list.removeFromFront();
			System.out.printf("\n%d removed \n", removedItem);
			list.print();
			removedItem = list.removeFromBack();
			System.out.printf("\n%d removed \n", removedItem);
			list.print();
			removedItem = list.removeFromBack();
			System.out.printf("\n%d removed \n", removedItem);
			list.print();
 
		}catch(EmptyListException e){
			e.printStackTrace();
		}
	}
}

--- Update ---

Here is where I try to implement comparable, but it creates many many compiler errors inside of class List....ANY help...greatly appreciated

public class ListNode< T extends Comparable<T>> implements Comparable<ListNode<T>> {
	T data;
	ListNode< T > nextNode;
 
	ListNode(T object){
		this(object, null);
	}
 
	ListNode(T object, ListNode<T> node){
		data = object;
		nextNode = node;
	}
 
	T getData(){
		return data;
	}
 
	ListNode<T> getNext(){
		return nextNode;
	}
 
	public int compareTo(ListNode<T> o) {
		return data.compareTo(o.data);
	}
}

You describe many things you've tried to do, but you're unclear about which of those (all, some, one?) you'd like help with. Please ask specific questions, point to specific areas of code that are giving you trouble, and post the errors you'd like help with.

So where are you now? Post your latest code, preferably commented code that can be corrected (if needed), compiled, and run.

Hey I just saw you replied.
I received no input/help and I gave up.
The original code I started with is posted.
The method inside that code called insertSort() is the method I'm trying to add.
I am so confused as to what you want. I don't even know what I want. It's been a week and I only wanted to spend 20-30 minutes on this.
Look at my classes. Imagne you want to add a way to compare generic objects?
I don't want code from you. I want you to say "use such and such library". Then I can write some code and post it and you can help me further.
I have given myself multiple suggestions and received none from this board. I have searched the forum for similiar linked list structures.
I want to use this current structure because it is professional and what I saw on google wasn't similiar.
Now I realize how to make a linked list by combining the node and list class but this is not what I want.
I want to do it the way I was told to and I'm not looking for shortcuts, just suggestions.
My suggestions were either comparator which is more for tree lists, or the comparable interface provided with generics.
The code I wrote using Comparable has been posted but as I said it creates compiler errors.
I don't understand how a custom list has better processing power than a Collection. Collections are already done for us so why didn't they make it so it had good processing ability? Well, now I'm just whining so please suggest any library and its methods or interface and I will gladly GIvE IT A SHOT and post my findings here.

--- Update ---

What do I need to add to List<T> to stop the compiler errors? I'm sure it has something to do with the class heading but when I include comparable in both classes, the compiler goes bonkers.

--- Update ---

And the first set of code compiles. As long as you don't called the method I was trying to add because it's not complete. I don't think anything has been left out. You have everything I do. I'll give it another shot soon but I'm studying for certifications at the moment. If I wasn't time constrained I would not of asked for help.
I'm 99% positive I have to use T comparible but as you can see if you copy and past my code into any compiler, it creates numerous errors.

--- Update ---

Step one add comparable to the ListNode<t> class

public class ListNode<T> implements Comparable< T > {
	T data;
	ListNode< T > nextNode;
 
	ListNode(T object){
		this(object, null);
	}
 
	ListNode(T object, ListNode<T> node){
		data = object;
		nextNode = node;
	}
 
	T getData(){
		return data;
	}
 
	ListNode<T> getNext(){
		return nextNode;
	}
 
	public int compareTo(T arg0) {
		// TODO Auto-generated method stub
		return 0;
	}	
}

--- Update ---

Step two create the method

public void insertAfter(T insertItem) {		
		ListNode<T> current = firstNode;
		if(isEmpty()){
			firstNode = lastNode = new ListNode<T>(insertItem); //firstnode = lastnode because the list is empty.
		}else{
			while(current != null){	
				if(current.compareTo(insertItem) >= 0){
					current.nextNode = new ListNode<T>(insertItem, current.nextNode);					
				}
			}
		}
	}

--- Update ---

public int compareTo(T a) {
		if(data < a)
		return 0;
	}

Now I'm stuck for the moment.....my thinking...the current node .compareTo is called on it.....it is then compared to the insertedItem.
The method must return 0 or greater so that the if statement true and it inserts the item in the correct node.
Then breaks.
If I wanted to do a reverse order insert. I would have an if statement with if current.compareTo(insertItem) <= 0.
I still have to merge, sort and a few other things with this code.

--- Update ---

	public void insertAfter(T insertItem) {		
		ListNode<T> current = firstNode;
		if(isEmpty()){
			firstNode = lastNode = new ListNode<T>(insertItem); //firstnode = lastnode because the list is empty.
		}else{
			while(current != null){	
				System.out.println("loop through list");
				if(current.compareTo(insertItem) >= 0){
					System.out.println("Compared object was greater and will now insert");
					if(current != firstNode){
						if(current.nextNode != null)
							current.nextNode = new ListNode<T>(insertItem, current.nextNode);
						else 
							current.nextNode = lastNode = new ListNode<T>(insertItem);
					}else
						firstNode = new ListNode<T>(insertItem, firstNode);
					break;
				}
			}
		}
	}

--- Update ---

public int compareTo(T a) {
		return ((Comparable<T>) data).compareTo(a);
	}

--- Update ---

Consider

private class Node<E extends Comparable<E>> implements Comparable<E>

and

private class Node<E extends Comparable<E>> implements Comparable<Node<E>>
...
public int compareTo(Node<E> other)
{
    return data.compareTo(other.data);
}

I wigged and I wagged....here's the finished code, so when someone asks How do I compare a generic node with a generic object you can refer them to this post.

public class ListNode<T> implements Comparable<T> {
	T data;
	ListNode< T > nextNode;
 
	ListNode(T object){
		this(object, null);
	}
 
	ListNode(T object, ListNode<T> node){
		data = object;
		nextNode = node;
	}
 
	T getData(){
		return data;
	}
 
	ListNode<T> getNext(){
		return nextNode;
	}
 
	public int compareTo(T arg0) {
		return ((Comparable<T>) data).compareTo(arg0);
	}
}

 
public static void main(String[] args){
		List<Integer> list = new List<Integer>();
 
		list.insertAtFront(0);
		list.print();
		list.insertAtFront(-1);
		list.print();
		list.insertAtBack(1);
		list.print();
		list.insertAtBack(4);
		list.insertAtBack(5);
		list.print();
		list.insertAfter(3);
		list.print();
 
 
		try{
 
			int removedItem = list.removeFromFront();
			System.out.printf("\n%d removed \n", removedItem);
			list.print();
			removedItem = list.removeFromFront();
			System.out.printf("\n%d removed \n", removedItem);
			list.print();
			removedItem = list.removeFromBack();
			System.out.printf("\n%d removed \n", removedItem);
			list.print();
			removedItem = list.removeFromBack();
			System.out.printf("\n%d removed \n", removedItem);
			list.print();
 
		}catch(EmptyListException e){
			e.printStackTrace();
		}
	}
}

@SuppressWarnings("serial")
public class EmptyListException extends RuntimeException {
 
	public EmptyListException(){
		this("list");
	}
 
	public EmptyListException( String name){
		super(name+ " is empty");
	}
}

public class List<T>  {
	private ListNode<T> firstNode;
	private ListNode<T> lastNode;
	private String name;
 
	public List(){
		this("list");
	}
 
	public List(String listName){
		name = listName;
		firstNode = lastNode = null;
	}
 
	public void insertAfter(T insertItem) {		
		ListNode<T> lastTemp = firstNode;
		ListNode<T> current = firstNode;
		if(isEmpty()){
			firstNode = lastNode = new ListNode<T>(insertItem); //firstnode = lastnode because the list is empty.
		}else{
			while(current != null){	
				System.out.println("loop through list, comparison int return = : " + current.compareTo(insertItem) + " current item: " + current.data + " item to insert: " + insertItem);
				if(current.compareTo(insertItem) > 0){					
					System.out.println("Compared object was greater and will now insert");
					if(current != firstNode){
						if(current.nextNode != null)
							lastTemp.nextNode = new ListNode<T>(insertItem, current);
						else 
							current.nextNode = lastNode = new ListNode<T>(insertItem);
					}else
						firstNode = new ListNode<T>(insertItem, firstNode);
					break;
				}
				lastTemp = current;
				current = current.nextNode;
			}
		}
	}
 
	public void insertAtFront(T insertItem){
		if(isEmpty()){
			firstNode = lastNode = new ListNode<T>(insertItem); //firstnode = lastnode because the list is empty.
		}else
			firstNode = new ListNode<T>(insertItem, firstNode);
	}
 
	public void insertAtBack(T insertItem){
		if(isEmpty()){
			firstNode = lastNode = new ListNode<T>(insertItem); //firstnode = lastnode because the list is empty.
		}else
			lastNode = lastNode.nextNode = new ListNode<T>(insertItem);
	}
 
	public T removeFromFront() throws EmptyListException{
		if(isEmpty())
			throw new EmptyListException(name);
 
		T removedItem = firstNode.data;
 
		if(firstNode == lastNode)
			firstNode = lastNode = null;
		else
			firstNode = firstNode.nextNode;
 
		return removedItem;		
	}
 
	public T removeFromBack() throws EmptyListException{
		if(isEmpty())
			throw new EmptyListException(name); 
		//if no exception is thrown
		T removedItem = lastNode.data;
 
		if(firstNode == lastNode)
			firstNode = lastNode = null;
		else{
			ListNode<T> current = firstNode;
 
			while(current.nextNode != lastNode)
				current = current.nextNode;			
			lastNode = current;
			current.nextNode = null;
		}
 
		return removedItem;			
	}
 
	public boolean isEmpty(){
		return firstNode == null;
	}
 
	public void print(){
		if(isEmpty()){
			System.out.printf("Empty %s\n", name);
			return;
		}
 
		System.out.printf("The %s is: ", name);
		ListNode<T> current = firstNode;
 
		while(current!= null){
			System.out.printf("%s ",  current.data);
			current = current.nextNode;
		}
 
		System.out.printf("\n");
	}	
 
}