I am having a few problems with a sorted linked list I have written
It all compiles fine but when I run it, i come into problems
The first noticeable problem is that it is not getting sorted. When I print the first element, it prints the first element added (which is 6 not 1), not the beginning of the set and it'e the same for the last (which is 1 not 6).
Also how do i get it to throw duplicate entries? In my example I have added 1 twice and I only want it to add it once.
Another problem is when i try and use the iterator, it throws null pointer exceptions.
The last problem is when i try and print the subSet, tailSet and headSet. I get a stack overflow error.
Any ideas how i can get this working?
import java.util.*;
public class OrderedLinkedList<E> extends AbstractSet<E> implements SortedSet<E> {
private Node<E> head;
private Node<E> current;
private int numberContents;
public OrderedLinkedList() {
head = new Node<E>(null);
numberContents = 0;
}
public boolean add(E cargo){
Node<E> nextNode = new Node<E>(cargo);
if(numberContents == 0){
head = nextNode;
}
else{
Node<E> current = head;
for(int i=1; i< numberContents; i++){
current=current.getNext();
}
current.setNext(nextNode);
}
numberContents++;
return true;
}
public int size() {
return numberContents;
}
public boolean isEmpty() {
return head == null;
}
public E first() {
if (isEmpty()) {
throw new NoSuchElementException();
}
current = head;
return head.getContents();
}
public E last() {
if(isEmpty()){
throw new NoSuchElementException();
}
for(int i=1; i < numberContents; i++){
current = current.getNext();
}
return current.getContents();
}
public SortedSet<E> tailSet(E fromElement) {
if (isEmpty()) {
throw new NullPointerException();
}
OrderedLinkedList oll = new OrderedLinkedList();
SortedSet<E> tail = oll.tailSet(fromElement+"\0");
return tail;
}
public SortedSet<E> headSet(E toElement) {
if (isEmpty()) {
throw new NullPointerException();
}
OrderedLinkedList oll = new OrderedLinkedList();
SortedSet<E> head = oll.headSet(toElement+"\0");
return head;
}
public SortedSet<E> subSet(E fromElement, E toElement) {
//if (isEmpty()) {
// throw new NullPointerException();
//}
OrderedLinkedList oll = new OrderedLinkedList();
SortedSet<E> sub = oll.subSet(fromElement, toElement+"\0");
return sub;
}
public Iterator<E> iterator() {
return new Iterator<E>() {
E valueReturned;
private int counter = 0;
public boolean hasNext() {
if (counter >= numberContents){
return false;
}
else {
counter++;
return true;
}
}
public E next() {
valueReturned = current.getContents();
current = current.getNext();
return valueReturned;
}
public void remove() {
throw new UnsupportedOperationException();
}
};
}
public Comparator<E> comparator(){
return new Comparator<E>() {
public int compare(E obj1, E obj2) {
Node<E> node1 = (Node) obj1;
Node<E> node2 = (Node) obj2;
return node1.compareTo(node2.getContents());
}
public boolean equals(Object obj) {
if (!(obj instanceof OrderedLinkedList)) {
return false;
}
Node<E> newNode = (Node) obj;
return current.getContents().equals(newNode.getContents());
}
};
}
public static void main(String Args[]){
OrderedLinkedList linkedList = new OrderedLinkedList();
linkedList.add(new Node("6"));
linkedList.add(new Node("2"));
linkedList.add(new Node("4"));
linkedList.add(new Node("3"));
linkedList.add(new Node("1"));
linkedList.add(new Node("1"));
int size = linkedList.size();
System.out.println("Number of elements in list " + size);
System.out.println("The first element is " + linkedList.first());
System.out.println("The last element is " + linkedList.last());
System.out.println("The tailSet is " + linkedList.tailSet("4"));
System.out.println("The headSet is " + linkedList.headSet("4"));
System.out.println("The subSet is " + linkedList.subSet("4", "1"));
Iterator itr = linkedList.iterator();
while(itr.hasNext()){
Object element = itr.next();
System.out.println(element + "\n");
}
}
}
and this is my Node class
import java.util.*;
public class Node<E> implements Comparable<E>{
Node<E> next; // Refers to next item in the list.
Node<E> previous; // Refers to the previous item. ***
E cargo; // The item for this Node.
// Constructor:
public Node(E cargo) {
this.cargo = cargo; // Store the item.
next = null; // Set next and previous to null. ***
previous = null;
}
// Set the pointer to the next Node:
public void setNext(Node<E> next) {
this.next = next; // Store reference to the next item.
}
// Additional method to set the pointer to the previous Node: ***
public void setPrevious(Node<E> previous) {
this.previous = previous; // Store reference to the previous item.
}
// Get the next item in the list:
public Node<E> getNext() {
return next;
}
// Additional method to get the previous item in the list: ***
public Node<E> getPrevious() {
return previous;
}
// Get the object for this item:
public E getContents() {
return cargo;
}
// Return class name & object:
public String toString() {
return ""+ cargo;
}
public int compareTo(E obj) {
Node<E> newNode = (Node<E>) obj;
int nodeComp = ((Comparable<E>)cargo).compareTo(newNode.getContents());
return nodeComp;
}
}
Email this Topic
Edit this Topic
