Need help using linked list

[tigertomas]

Hi. I've been having trouble the last couple of days with this assignment, and I'm running out of time. I'm supposed to change a method called "add" in the file below so that it not only adds an element to the list, but also sorts it, the element with least value first, most value last. If you want to see where I need help search for: [!"#] . I've also made a test file but I don't think you need that. If you could help me out, I would be incredibly greatful. Here's the code:

public class LinkedCollection<E>
extends AbstractCollection<E> {

    /**
     * <tt> head </tt> is a referens to the first
     * element in the list.
     * <tt> head </tt> is <tt> null </tt> in the
     *  empty collection.
     */
    protected Entry head;

    /**
     * The class of objects used as nodes of the
     *  singly linked list
     */
    protected class Entry { 

        public E      element;
        public Entry  next;

        public Entry( E element, Entry next ) {
            this.element = element;
            this.next = next;
        }

    } // Entry

    /** 
     * The constructor of the collection.
     * The collection is initialized to be empty.
     */
    public LinkedCollection() {
        head = null;
    }  // constructor LinkedCollection

    /**
     * Compute the number of elements in the container.
     * @return The number of elements in the container.
     */
    public int size() {
	int count = 0;
        for ( Entry p = head; p != null; p = p.next )
            count++;
        return count;
    } // size

    /**
     * Create an iterator over the elements contained
     * in the collection.
     * @return the created iterator.
     */
    public Iterator<E> iterator() {
	return new LinkedCollectionIterator();
    }  // iterator 
    
    /**
     * Adds an element to the collection.
     * The element added last will be the first element 
     * given by the iterator and the first element 
     * added will be the last given by the iterator.
     * 
     * @param element the object to add into the list
     * @return true if the object has been added to the list.
     * @throws NullPointerException if parameter <tt>element<tt> is null. 
     */
    public boolean add( E element ) {
        if ( element == null )
	    throw new NullPointerException();
	else {
	    head = new Entry( element, head );
	    return true;
	}
    } // add

    /**
     * Decides if there are any elements in the collection.
     *
     * @return true if there are no elements in the collection, 
     *         otherwise false.
     * 
     */
    public boolean isEmpty() {  
        // not necessary, but more efficient
	return head == null;
    } // isEmpty

    /**
     * Remove all of the elements from this collection.
     */
    public void clear() {  
        // not necessary, but much more efficient
        // than to remove the elements one by one
    	head = null;
    } // isEmpty

    private class LinkedCollectionIterator
	implements Iterator<E>         {

        Entry   next, previous;
        boolean removeAllowed;

	LinkedCollectionIterator() {
	    next          = head;
	    previous      = null;
	    removeAllowed = false;
	} //  constructor LinkedCollectionIterator

	public boolean hasNext() {
	    return next != null;
	}  //  hasNext

	public E next() {
	    try {
		previous      = next;
		next          = next.next;
		removeAllowed = true;
		return previous.element;
	    }
	    catch(NullPointerException npe) {
		throw new NoSuchElementException();
	    } //  next

	} // next 

	public void remove() {
	    if ( removeAllowed ) {
		if ( previous == head )
		    head = head.next;
		else {
		    Entry p = head;
		    while ( p.next != previous )
			p = p.next;
		    p.next = p.next.next;
		}
		removeAllowed = false;
	    }
	    else
		throw new IllegalStateException();
	}  //  remove 

    }  // class LinkedCollectionIterator

} // LinkedCollection

So it's quite a simple assignment, but I just can't get it to work. Here's how I've tried to solve it:

 public class SortedLinkedCollection<E extends Comparable<E>> extends LinkedCollection<E> {

	
	/**Adds an element and sorts it in sort
	 */
    public boolean add( E element ) {
        if ( element == null )
        	throw new NullPointerException();
        else {
        	head = new Entry( element, head );
        	sort(head);
        	return true;
        }
    } // add

    /** Returns the element at the place index
     */
    
    public E get(int index){
        //System.out.println(size());
    	if (index < 0 || index >= size()) {
    		throw new IndexOutOfBoundsException(Integer.toString(index));
    	}
    	Entry elem = head;
    	//for ( Entry i = head; i != null; i = i.next){
    	for ( int i = 0; i < index && elem != null; i++){
    		elem = elem.next;
    	}
    	return elem.element;
            
    } // get
    
    private void sort(Entry head) {
    	Entry elem = head.next;
    	Entry elemNext = null;
    	Entry elemTmp = null;
    	int pass = 1;
    	boolean exchanges = false;
    	do {
    		exchanges = false;
    		for (int i = 0; i < size() - pass; i++) {
    			elemNext = elem.next;    			
    			if (elem.element.compareTo(elemNext.element) > 0) {
    				elemTmp = elem;
    				elem = elemNext;
    				elemNext = elemTmp;
    				exchanges = true;
    			}
    			else {
    				exchanges = false;
    				elem = new Entry(elemNext, elem.element) // THIS IS WHERE I NEED HELP, HOW DO I ADD THE ELEMENT?[!"#]
    			}
    			
    		}
    	} while (exchanges);
    }

[tigertomas]

I'm sorry I don't understand what you're trying to tell me.

[Fubarable]

I'm sorry I don't understand what you're trying to tell me.

I think that you were reading a spam post that I have removed. Sorry for any inconvenience.


Also, when posting code here, please use code tags so that your code will retain its formatting and thus will be readable -- after all, your goal is to get as many people to read your post and understand your code as possible, right?

To do this, highlight your pasted code (please be sure that it is already formatted when you paste it into the forum; the code tags don't magically format unformatted code) and then press the code button, and your code will have tags.

Another way to do this is to manually place the tags into your code by placing the tag [cod&#101;] above your pasted code and the tag [/cod&#101;] below your pasted code like so:

[code]
  // your code goes here
  // notice how the top and bottom tags are different
[/code]

[Fubarable]

Edit: I have added the code tags to your original post

[Fubarable]

Question, if the new add always adds an element in sorted order, then there's no need to sort the list with each add, correct? All you have to make sure is that you add it at the right location and the list will stay sorted. If that's the case, couldn't you simply iterate through the list using compareTo until you either reach the end or reach a spot where the added element belongs and then add it?

[tigertomas]

Thanks a lot for the help. Yeah that is exactly what I was thinking, but I couldn't get it to work. I'm in 3rd year in Chalmers, and I haven't had any programming courses since 1st year, and I don't remember much at all. What I'm trying to understand is what variables I'm going to put into the "New Entry(x, y). I appreciate your help. What I have in that last New Entry(...) atm is not correct, the code doesn't work.