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