I have this class I am able to use to test my code: import java.util.Iterator; /
ID: 3771479 • Letter: I
Question
I have this class I am able to use to test my code:
import java.util.Iterator;
// This Class can be used to test the OrderedLinkedList class
public class LinkedListTest {
private class Courses implements Comparable<Courses>{
String rubric;
int number;
public Courses(String rub, int num) {
rubric = rub;
number = num;
}
public int compareTo(Courses other) {
if (rubric.compareTo(other.rubric) < 0)
return -1;
else if (rubric.compareTo(other.rubric) > 0)
return 1;
else
return number - other.number;
}
public String toString() {
return rubric + " " + number;
}
}
public static void main(String[] args) {
LinkedListTest ll = new LinkedListTest();
Courses listOfCourses[] = { ll.new Courses("COSC", 2436),
ll.new Courses("ITSE", 2409),
ll.new Courses("COSC", 1436),
ll.new Courses("ITSY", 1300),
ll.new Courses("ITSY", 1300),
ll.new Courses("COSC", 2436),
ll.new Courses("ITSE", 2417) };
OrderedLinkedList<Courses> orderedList = new OrderedLinkedList<Courses>();
for (int i = 0; i < listOfCourses.length; i++)
orderedList.findOrAdd(listOfCourses[i]);
Iterator<Courses> classIter = orderedList.iterator();
while(classIter.hasNext()) {
System.out.println(classIter.next());
} // There should be 5 courses listed in order
}
}
Here are the requirements: Implement a generic ordered linked list abstract data type. A unique feature of this generic linked list data structure is the findOrAdd method. This method searches the list for a previously added object with the same name, if one is found, the previous object is returned, if not the new object is added, in alphabetical order, to the list. Using ADTs from standard Java classes is not permitted. This is the code I have so far for the OrderedLinkedList:
import java.util.Iterator;
public class OrderedLinkedList< E extends Comparable< E>> implements Iterable <E>
{
private E first;
private E next;
private E last;
private E current;
private E temp;
private int size;
public OrderedLinkedList()
{
this.first = null;
this.next = null;
this.last = null;
this.current = null;
this.temp = null;
this.size = 0;
}
public E findOrAdd (E element)
{
E value = null;
Iterator <E> iter = this.iterator ();
if (this.first == null)
{
this.first = element;
this.current = element;
this.size++;
}
else
for (int i = 0; i < this.size; i++)
{
if (current.compareTo(element) > 0 && iter.hasNext() == false)
{
temp = this.first;
this.current = element;
this.next = temp;
this.size++;
}
else if (current.compareTo(element) < 0 && iter.hasNext() == true)
continue;
else if (current.compareTo(element) == 0)
value = element;
else if (current.compareTo(element) > 0)
{
temp = this.next;
this.current = element;
}
}
return value;
}
public Iterator <E> iterator ()
{
return new OrdListIterator <E> ();
}
private class OrdListIterator <E> implements Iterator <E>
{
private E nextNode;
public OrdListIterator ()
{
}
public boolean hasNext ()
{
return (next != null);
}
public E next ()
{
return (E) next;
}
public void remove ()
{
}
}
}
At this point, I am at a complete loss. It just keeps printing COSC 2436 infinitely.
Explanation / Answer
Answer:
Program code to copy:
import java.util.Iterator;
public class OrderedLinkedList<E extends Comparable<E>> implements Iterable<E>
{
private class OrderedLinkedListNode<E>
{
E data;
OrderedLinkedListNode<E> next = null;
}
OrderedLinkedListNode<E> first;
OrderedLinkedListNode<E> last;
private int size;
public OrderedLinkedList()
{
this.first = null;
this.last = null;
this.size = 0;
}
public void addFirst(E dataItem)
{
OrderedLinkedListNode<E> newNode = new OrderedLinkedListNode<E>();
newNode.data = dataItem;
newNode.next = first;
first = newNode;
if (last == null) // adding to empty list
last = newNode;
}
public void addLast(E dataItem)
{
if (last == null)
{ // treat case of empty linked list
last = new OrderedLinkedListNode<E>();
first = last;
}
else
{ // case of non-empty linked list
last.next = new OrderedLinkedListNode<E>();
last = last.next;
}
last.data = dataItem;
last.next = null;
}
/**
* @param element
*/
public E findOrAdd(E element)
{
E value = null;
if (this.first == null)
{
addFirst(element);
}
else if (element.compareTo(first.data) == -1)
{
addFirst(element);
}
else if (element.compareTo(last.data) == 1)
{
addLast(element);
}
else
{
OrderedLinkedListNode<E> current = first;
while (element.compareTo(current.data) < 0)
{
if (element.compareTo(current.data) == 0)
return element;
current = current.next;
}
OrderedLinkedListNode<E> oldIter = first;
OrderedLinkedListNode<E> iter = first.next;
while (iter.data.compareTo(element) == -1)
{
oldIter = iter;
iter = iter.next;
}
OrderedLinkedListNode<E> newNode = new OrderedLinkedListNode<E>();
newNode.data = element;
newNode.next = iter;
oldIter.next = newNode;
}
return value;
}
public Iterator<E> iterator()
{
return new OrdListIterator();
}
private class OrdListIterator implements Iterator<E>
{
OrderedLinkedListNode<E> next;
private OrderedLinkedListNode<E> current;
private OrderedLinkedListNode<E> lastVisited;
public OrdListIterator()
{
current = first;
lastVisited = null;
}
public boolean hasNext()
{
return (current != last);
}
public E next()
{
if (hasNext())
{
E nextItem = current.data;
lastVisited = current;
current = current.next;
return nextItem;
}
return null;
}
public void remove()
{
}
}
}
//LinkedListTest.java
import java.util.Iterator;
// This Class can be used to test the OrderedLinkedList class
public class LinkedListTest
{
private class Courses implements Comparable<Courses>
{
String rubric;
int number;
public Courses(String rub, int num)
{
rubric = rub;
number = num;
}
public int compareTo(Courses other)
{
if (this.rubric.compareTo(other.rubric) < 0)
return -1;
else if (this.rubric.compareTo(other.rubric) > 0)
return 1;
else
{
int value = 0;
if (this.number < other.number)
value = -1;
else if (this.number > other.number)
value = 1;
else
value = 0;
return value;
}
}
public String toString()
{
return rubric + " " + number;
}
}
public static void main(String[] args)
{
LinkedListTest ll = new LinkedListTest();
Courses listOfCourses[] =
{ ll.new Courses("COSC", 2436), ll.new Courses("ITSE", 2409),
ll.new Courses("COSC", 1436), ll.new Courses("ITSY", 1300),
ll.new Courses("ITSY", 1300), ll.new Courses("COSC", 2436),
ll.new Courses("ITSE", 2417) };
OrderedLinkedList<Courses> orderedList = new OrderedLinkedList<Courses>();
for (int i = 0; i < listOfCourses.length; i++)
orderedList.findOrAdd(listOfCourses[i]);
Iterator<Courses> classIter = orderedList.iterator();
while (classIter.hasNext())
{
System.out.println(classIter.next().toString());
} // There should be 5 courses listed in order
}
}