Sorted Linked List help

[Tussles]

As part of an assignment I have been asked to create a SortedLinkedList class. We have been told that we must use the java.util.LinkedList<E> in order to dervie this class.

I understand that I must in some way overwrite the .add(Object) method.

I realise that I must in some way make a call to super.add(Object), however, this gives me nothing to carry out Collections.sort() method on.

My code at present is as follows:

import java.util.*;
/**
 * Creates a Sorted Linked List in Ascending Order
 * 
 * @author Tussles
 * @version 14/10/09
 */
public class SortedLinkedList<E> extends LinkedList<E>
{

    /**
     * Constructor for objects of class SortedLinkedList
     */
    public SortedLinkedList()
    {
    }

      //**Overwriting the add method here**//
     public boolean add(E c)
     {  
         super.add(c);
         return true;
     }

}

EDIT: Including the main code I am running to test this Class. User is the object I am attempting to store within a Sorted Linked List.

public static void main(String[] args)
{
    User user1 = new User("Tuss","Les",0);
    User user2 = new User("Zed","Zeberdee",0);
    User user3 = new User("Macy","Middle",0);
    
    SortedLinkedList LibraryUser = new SortedLinkedList();
    
    LibraryUser.add(user2);
    LibraryUser.add(user1);
    LibraryUser.add(user3);
    
    for (int i = 0; i<LibraryUser.size();i++)
    {
        System.out.println(LibraryUser.get(i));
        
    }
    
   
}

This is the output results at present (I am adding, but not sorting the list)

First Name: Zed Second Name: Zeberdee
First Name: Tuss Second Name: Les
First Name: Macy Second Name: Middle

How would I go about altering this so that I am able to sort the List every time I add a new Object to it?

If more information is needed I can provide it.

Thanks

[JamesCherrill]

Since your class extends (is-a-kind-of) LinkedList, you can just use the sort in Collections directly on your object:
Collections.sort(this);

(Although I suspect your prof may expect you to insert each object into the list in the right place, thus keeping it sorted all the time - loop thru the list until you find the first object that sorts after the new one, and insert it there)

[Tussles]

Whilst that is the easy option, I have been told that I am not allowed to do this. The sorting has to take place every time we add the data.

In reality I would much rather use the method you suggest, but the assignment clearly states differently.

Thank you for your help :(

[ejosiah]

when you override the add method you have to compare the objects you are adding in to make sure that the largest object is alwasys at the end of the list. Make your User class extend Comparable and implement the compareTo method. you get the picture

[ejosiah]

override the method this way after implementing Comparable in your user class

//**Overwriting the add method here**//
public boolean add(E e){
int size = size();
for(int i = 0; i < size; i++){
    if(e.compareTo(get(i) < 0){
         // e is less than object at this position
         insert(i-1,e); // insert e before position i
    }else{
       // e is => object at position i
       insert(i+1,e); // insert e after positoin i
   }
return true;
}

[JamesCherrill]

ejosiah: You obviously didn't try this. You may want to test that code and fix it before re-posting :-)

[ejosiah]

@ jamesCherrill I just can't give him everything he kinda has to figure the rest out for himself. I knew there was something when I posted it but I figured he would have know. if you got a problem with that then be my get and fix it

[JamesCherrill]

I agree that we shouldn't just give people the answer - but giving a newbie code that doesn't work is likely to make their problem harder, not easier. We both know that the corect solution doesn't look much like the thing you posted. ANyway, enough said. Let's get back to the OP's needs.

[Tussles]

//**Overwriting the add method here**//
public boolean add(E e){
int size = size();
for(int i = 0; i < size; i++){
    if(e.compareTo(get(i)) < 0)
    {
         // e is less than object at this position
        add(i-1,e); // insert e before position i
         return true;
    }
}
return true;
}

Im not the best at coding, however. I think that fixes the issue of adding the object more than once. However, when compiling I recieve the error "cannot find symbol - method compareTo(E)", before I read ejosiahs reply I created my own, clumsier version, however I still had the same issue

as follows is my clumsy version:

//**Overwriting the add method here**//
     public boolean add(E c)
     {  
             E d = null;
             int count = 0;
             
             if (count == 0)
             {
                         super.add(c);
                         count++;
                         return true;
              }else
              {
                   for (int i=0; i<super.size()-1;i++)
                    {
                            d=super.get(i);
                            if ((c.compareTo(d)<0))
                            {
                                super.add(i-1,c);
                                return true;
                            }
                     }
                     return false;
                }
      }

are my references to super pointless?

How do I go about correcting the issue of "cannot find symbol - method compareTo(E)"

[ejosiah]

Ok ok this time no code. Tossles this is want you need to do. to create a sorted list from a linked list. override the add method and perform an insertion sort to find the correct position to insert your data. when u find it call the insert method from your super class and insert the data in that position.

[ejosiah]

dude I guess I kinda made your life hell by giving you this code. so I might as well give you something that works. I'm bout to leave work so just check back in a couple of hours

[Tussles]

dude I guess I kinda made your life hell by giving you this code. so I might as well give you something that works. I'm bout to leave work so just check back in a couple of hours

Will do :) You helped me go from No clue to know what I need to do, just cant fathom how to do the thing I need.

[JamesCherrill]

If you like I'll fill in a bit while ejosiah's away.
Your "clumsy" code is very nearly right - stick with it.
Your int count looks like its supposed to be the size of the list - so just use size() instead. You can say super.size() if you like, but since you don't override size(), the super is not needed.
However, you do need the super.add because you have overriden add.
Your other problem is the compareTo method.
To sort the elements you need to know what order they should come in, and that's defined by the compareTo method. But that depends on what kind of objects they are - for Strings, or Integers, it's pretty obvious, and Java gives you the right method. But suppose the objects are Colors, or JButtons - what's the order then? I don't know what your requirements have to say about this, but IMHO you can only make a sorted list work if the elements are Comparable (ie there is a compareTo method for them). I would personally restrict my class to make sure this is true, by specifyking that the type E must be Comparable, something like:

class SortedLinkedList<E extends Comparable<E>>  extends LinkedList<E>

ps: You also need to cover the case where the new element should go on the end of the list (sorts after all the existing elements) - it's where you currently return false;

[Tussles]

It appears that I have fully working code :)

It sorts all my names out in Alphabetical order, Therefore, I believe you both deserve my thanks. I would have struggled for weeks on that part of the code.

class SortedLinkedList<E extends Comparable<E>>  extends LinkedList<E>

Turns out to be the ultimate problem solver for me.

I owe you both huge thanks :) Its off to impliment the rest of this mammoth assignment for me. Just rest assured, you guys have helped loads.

If anyone else is struggling with something like this, reading this thread will definatley help.

[JamesCherrill]

:-)

[Tussles]

I spoke to soon. I realised, If I tried to add an item on which would come at the back of the ordered Linked List, it wasnt being added.

I corrected my code to tag an else statement on the end

if (size() == 0)
             {
                         super.add(c);
                         return true;
              }else
              {
                   for (int i=0; i<size();i++)
                    {
                            d=get(i);
                            if ((c.compareTo(d)<0))
                            {
                                super.add(i,c);
                                return true;
                            }else
                            {
                                super.add(c);   
                            }
                     }
                     return false;

Im now getting an error saying that "java.lang.OutOfMemoryError: Java heap space". It seemed like a simple addition to the program, any idea as to why this is showing.

EDIT: putting in a return true; fixed it. I apologise for my tired tired coding.

[ejosiah]

don't ask any question and just use this

public boolean add(E e) {
		int position = size();

		for (int i = size() - 1; i >= 0; --i) {
			if (e.compareTo(get(i)) > 0) {
				break;
			}
			--position;
		}
		add(position, e);

		return position == size();

	}

[ejosiah]

Let me explain the code to you. when you call add it uses the insertion sort algorithm to find the insertion point for you item when this position is found it adds its to the list using LinkedList's add(index, object) method. you also need to always return true as this is the Contract requirement of the Collection.add method. so replace return position == size() with return true.

you don't need to call super.add() as you are overriding the original implementation and creating a new one.