Results 1 to 6 of 6
  1. #1
    tigertomas is offline Member
    Join Date
    Jan 2009
    Posts
    26
    Rep Power
    0

    Default Need help using linked list

    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> {

    Java Code:
        /**
         * <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:




    Java Code:
     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);
        }
    Last edited by Fubarable; 02-12-2011 at 03:48 PM. Reason: Moderator Edit: Code tags added

  2. #2
    tigertomas is offline Member
    Join Date
    Jan 2009
    Posts
    26
    Rep Power
    0

    Default

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

  3. #3
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,315
    Blog Entries
    1
    Rep Power
    26

    Default

    Quote Originally Posted by tigertomas View Post
    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:

    Java Code:
    [cod&#101;]
      // your code goes here
      // notice how the top and bottom tags are different
    [/cod&#101;]

  4. #4
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,315
    Blog Entries
    1
    Rep Power
    26

    Default

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

  5. #5
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,315
    Blog Entries
    1
    Rep Power
    26

    Default

    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?

  6. #6
    tigertomas is offline Member
    Join Date
    Jan 2009
    Posts
    26
    Rep Power
    0

    Default

    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.

Similar Threads

  1. help with linked list
    By Yakg in forum New To Java
    Replies: 7
    Last Post: 01-24-2011, 07:40 PM
  2. Linked list inside a linked list
    By viperlasson in forum New To Java
    Replies: 5
    Last Post: 07-27-2010, 12:15 AM
  3. Linked list
    By rosh72851 in forum New To Java
    Replies: 1
    Last Post: 02-05-2009, 08:21 AM
  4. Linked List integer list
    By igniteflow in forum Advanced Java
    Replies: 1
    Last Post: 12-10-2008, 09:53 PM
  5. Help with linked list
    By trill in forum New To Java
    Replies: 1
    Last Post: 08-07-2007, 08:29 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •