Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 7 of 7

Thread: Singly Linked List - Sort Method

  1. #1
    Junior Member
    Join Date
    May 2014
    Posts
    23
    My Mood
    Tired
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default 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);
    	}
    }


  2. #2
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    6,090
    My Mood
    Mellow
    Thanks
    244
    Thanked 752 Times in 738 Posts

    Default Re: Singly Linked List - Sort Method

    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.

  3. #3
    Junior Member
    Join Date
    May 2014
    Posts
    23
    My Mood
    Tired
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Re: Singly Linked List - Sort Method

    I think I was pretty precise.
    Quote Originally Posted by Sfrius View Post
    Anyways, a more concise question is how to compare the new T object with the current nodes T data variable.
    And I pretty much said all this the first time but heres another go at it.

    In the second example I even showed you how I tried to implement a comparable interface for T in my ListNode<T> class

    Except it creates compiler errors in my list<T> class.

    This isn't for school or anything. This is just for personal learning. I've already graduated but I still don't understand a lot about generics and creating "custom" lists.

    So if you look down to the if statement which i commented. I'm trying to compare the T data object in the ListNode<T> class with an integer I'm passing through to be added to the list.
    This is passed in as a T object. Not a ListNode<T>. So I have a listnode object and a T object and I can't compare them.
    Now as you see front and back are done for you, that was the easy part.
    Now I'm trying to run a while loop through the list. When the data entered(in this case an integer) it will compare itself to each node until it is EQual or GREATER than the current nodes T data object.

    Now the only thing I know to do to compare two T objects is to use the compareTo method with interface comparable.

    You can swap out the listnode<T> class with the one with comparable to see what compiler errors I'm getting.

    Other than that the first set of classes is what I'm using now. If I could figure out how or "if i can" use the comparable interface, I might try to use that again.

    So basically I'm looking for suggestions on how to compare the new object I'm entering with the T object thats already in the node.

    --- Update ---

    In addition when I want to display the objects in the singly linked list, current.data is a string object....and that makes this all the more confusing for me. I tried casting and toString, and String comparison but I don't think that's what I want.
    Last edited by Sfrius; July 24th, 2014 at 06:02 PM.

  4. #4
    Junior Member
    Join Date
    May 2014
    Posts
    23
    My Mood
    Tired
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Re: Singly Linked List - Sort Method

    Managed to find this post from 18 months ago. Sort and Merge Two Linked List
    I'm not really sure this person had their questions answered, it left me even more confused.
    Merging the nodes is the easy part....how do i compare T objects in this format? I think this is what this guy was trying to ask, he didn't realize he needed to use something like the Comparable interface.
    I also tried including comparable to both classes, weird things happened. Compiler had lots of useless ideas. Still sifting through old posts.

    Pulled out the problem so you could visualize it better. I'm probably almost there... just need an extra push!
    public boolean isGreater(ListNode<T> node, T a){
    		boolean result = false;
    		if(node.data > a){
    			result = true;
    		}
    		return result;
    	}


    --- Update ---

    Got a node and a custom object, not sure how to compare them. Why are linkedlists better than simple collections? collections already have the methods and functionality I need...and I could customize my own methods for collections as well....

    and I think I've been going about this all wrong, I'm currently working on a static compareTo method that uses comparable t.

    .......

    public  <T extends Comparable<T> > boolean isGreater(ListNode<T> node, T a){
    		boolean result = false;
    		if(node.data.compareTo(a) > 0){
    			result = true;
    		}
    		return result;
    	}
    brain is in overdrive, help please[COLOR="Silver"]

    Error I'm currently getting...
    Bound mismatch: The generic method isGreater(T, T) of type List<T> is not applicable for the arguments (T, T). The inferred type T is not a valid substitute for the bounded parameter <T extends Comparable<T>>

    currently reading: http://stackoverflow.com/questions/1...e-generic-type

    found the answer to this problem but still don't understand - http://stackoverflow.com/questions/1...rable-elements

    --- Update ---

    Me:I'm trying to figure out how to use a comparator with custom objects
    Random:I know all about that
    Me:Well I'm building a custom list and can't compare anything lol
    Random:I'd say overall
    Random:You need to wig instead of wag
    Me: lol?
    Random:On multiple levels

    Werd
    Last edited by Sfrius; July 24th, 2014 at 08:49 PM.

  5. #5
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    6,090
    My Mood
    Mellow
    Thanks
    244
    Thanked 752 Times in 738 Posts

    Default Re: Singly Linked List - Sort Method

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

  6. #6
    Junior Member
    Join Date
    May 2014
    Posts
    23
    My Mood
    Tired
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Re: Singly Linked List - Sort Method

    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);
    }

  7. #7
    Junior Member
    Join Date
    May 2014
    Posts
    23
    My Mood
    Tired
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Re: Singly Linked List - Sort Method

    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");
    	}	
     
    }

Similar Threads

  1. Remove at index in singly linked list?
    By EDale in forum What's Wrong With My Code?
    Replies: 7
    Last Post: October 3rd, 2013, 10:47 PM
  2. Creating methods in a singly linked list?
    By EDale in forum Collections and Generics
    Replies: 13
    Last Post: September 29th, 2013, 07:13 PM
  3. Remove at index method for singly linked list... what's wrong?
    By EDale in forum What's Wrong With My Code?
    Replies: 1
    Last Post: September 27th, 2013, 10:12 PM
  4. Singly Linked List
    By koala711 in forum What's Wrong With My Code?
    Replies: 1
    Last Post: September 27th, 2012, 03:15 PM
  5. Singly-Linked list structure
    By blaster in forum Algorithms & Recursion
    Replies: 24
    Last Post: March 11th, 2012, 04:42 PM