Reputation: 446
Im trying to make a linked list implementation of a queue in java we are working from a basic IQueue interface then we have a list element class which defines the elements in the list/queue then we also have a MyQueue class which the bulk of the information is stored in. I will provide all of the code below. I have also written a test.java main class to run it all and see if it is working then when I compiled it and ran it I got some errors which will also be shown.
Interface:
/**
* An interface for a generic queue
*/
public interface IQueue<E> {
// Add an element to the (end of) queue.
public void enqueue(E element);
// Remove and return element from the (start of) queue.
public E dequeue();
// Returns true when the queue has no elements, false otherwise.
public boolean isEmpty();
}
List element:
public class ListElement<E> {
private final E value;
private ListElement<E> next;
private ListElement<E> prev;
public ListElement(E value) {
this.value = value;
}
public E getValue() {
return this.value;
}
public ListElement<E> getNext() {
return this.next;
}
public ListElement<E> getPrev() {
return this.prev;
}
public void setNext(ListElement<E> e) {
this.next = e;
}
public void setPrev(ListElement<E> e) {
this.prev = e;
}
}
MyQueue.java:
import java.util.ArrayList;
public class MyQueue<E> implements IQueue<E> {
private ListElement<E> head;
private ListElement<E> tail;
public MyQueue() {
head = null;
tail = null;
}
// INCOMPLETE.
public E modifyHead(E newhead) {
ListElement<E> update_head = new ListElement(newhead);
ListElement<E> oldhead = new ListElement(head);
head = update_head;
// Modifies the head of the queue to contain newhead.
// Returns the old value in the head.
return oldhead.getValue();
}
public boolean isEmpty() {
return (head == null);
}
public E dequeue() {
if (isEmpty()) {
return null;
}
ListElement<E> tmp = head;
head = tmp.getNext();
if (head == null) {
tail = null;
}
return tmp.getValue();
}
public void enqueue(E value) {
ListElement<E> tmp = new ListElement(value);
if (isEmpty()) {
tail = head = tmp;
} else {
tail.setNext(tmp);
tail = tmp;
}
}
public String toString() {
ArrayList a = new ArrayList();
while (head.getNext() != null){
a.add(head.getNext());
}
return a.toString();
}
}
Test.java:
public class test{
public static void main(String args[]){
MyQueue test = new MyQueue();
test.MyQueue();
test.enqueue("Kieran");
test.enqueue("Lavelle");
test.toString();
test.modifyHead("Replacement Head");
test.toString();
}
}
Sorry for that big bulk of code but I feel it is all needed to help the issue be worked out. Thanks in advance and here is the error:
Exception in thread "main" java.lang.NoClassDefFoundError: test/java
Caused by: java.lang.ClassNotFoundException: test.java
at java.net.URLClassLoader$1.run(URLClassLoader.java:202)
at java.security.AccessController.doPrivileged(Native Method)
at java.net.URLClassLoader.findClass(URLClassLoader.java:190)
at java.lang.ClassLoader.loadClass(ClassLoader.java:306)
at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:301)
at java.lang.ClassLoader.loadClass(ClassLoader.java:247)
Bit of an accident I ran it wrong. New error:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at java.util.Arrays.copyOf(Arrays.java:2760)
at java.util.Arrays.copyOf(Arrays.java:2734)
at java.util.ArrayList.ensureCapacity(ArrayList.java:167)
at java.util.ArrayList.add(ArrayList.java:351)
at MyQueue.toString(MyQueue.java:55)
at test.main(test.java:6)
Upvotes: 1
Views: 292
Reputation: 41
In toString method, you don't move from head, and without that head will always have next element
while (head.getNext() != null){
a.add(head.getNext());
}
So you have inifinite loop.
Also, when adding new element, not only must current tail reference new element with 'next', new element must reference tail with 'prev'.
In toString you should something like this
ListElement<E> item = head;
a.add(item);
while (item.getNext() != null){
a.add(item.getNext());
item = item.getNext();
}
And when adding element something like this
tail.setNext(tmp);
tmp.setPrev(tail);
tail = tmp;
Upvotes: 1