I am trying to reverse a doubly-linked list and print it by overriding the toString method. I used a template for the implementation of a doubly-linked list in java, and only added one method: reverse().
I've spent quite some time debugging, and was able to print out the entire reversed list properly. However, when the testReverse() function runs and calls the overridden toString() method on the new reversed list, I get a java.lang.outofmemoryerror java heap space error thrown at me. I've included the entire implementation of the doubly-linked list I used below, but I'm almost certain the issue concerns my algorithm.
Any and all insight or advice would be greatly appreciated. Thank you!
public class LinkedList<T> implements Iterable<T> {
private int size;
private Node<T> beginMarker;
private Node<T> endMarker;
private class Node<NodeT> {
public Node(NodeT d, Node<NodeT> p, Node<NodeT> n) {
data = d;
prev = p;
next = n;
}
public NodeT data;
public Node<NodeT> prev;
public Node<NodeT> next;
}
public LinkedList() {
doClear();
}
public void doClear() {
beginMarker = new Node<>(null, null, null);
endMarker = new Node<>(null, beginMarker, null);
beginMarker.next = endMarker;
size = 0;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size() == 0;
}
private Node<T> getNode(int idx, int lower, int upper) {
Node<T> p;
if (idx < lower || idx > upper)
throw new IndexOutOfBoundsException("getNode index: " idx "; size: " size());
if (idx < size() / 2) { // Search through list from the beginning
p = beginMarker.next;
for (int i = 0; i < idx; i )
p = p.next;
} else { // serch through the list from the end
p = endMarker;
for (int i = size(); i > idx; i--)
p = p.prev;
}
return p;
}
private Node<T> getNode(int idx) {
return getNode(idx, 0, size() - 1);
}
public T get(int idx) {
return getNode(idx).data;
}
public T set(int idx, T newVal) {
Node<T> p = getNode(idx);
T oldVal = p.data;
p.data = newVal;
return oldVal;
}
private void addBefore(Node<T> p, T x) {
Node<T> newNode = new Node<>(x, p.prev, p);
newNode.prev.next = newNode;
p.prev = newNode;
size ;
}
public void add(int idx, T x) {
addBefore(getNode(idx, 0, size()), x);
}
public void add(T x) {
add(size(), x);
}
private T remove(Node<T> p) {
p.next.prev = p.prev;
p.prev.next = p.next;
size--;
return p.data;
}
public T remove(int idx) {
return remove(getNode(idx));
}
public void reverse() {
Node current = beginMarker.next;
Node temp = null;
while (current != endMarker) {
temp = current.next; // store reference to next node
current.next = current.prev; // next points to previous node
current.prev = temp; // prev points to next node
current = temp; // current references temp (next node).
}
// changing references of beginning and end nodes
temp = beginMarker.next;
beginMarker.next = endMarker.prev;
endMarker.prev = temp;
/* TESTING THE PROGRAM, THIS PRINTS THE REVERSED LIST 'PROPERLY' BUT THE TESTER METHOD DOESN'T WORK */
current = beginMarker;
for (int i = 0; i <= size() 1; i ) {
System.out.println(current.data);
current = current.next;
/* END TEST */
}
}
public String toString() {
StringBuilder sb = new StringBuilder("[ ");
for (T x : this) {
sb.append(x " ");
}
sb.append("]");
return new String(sb);
}
public java.util.Iterator<T> iterator() {
return new LinkedListIterator();
}
private class LinkedListIterator implements java.util.Iterator<T> {
private Node<T> current = beginMarker.next;
private boolean okToRemove = false;
public boolean hasNext() {
return current != endMarker;
}
public T next() {
if (!hasNext())
throw new java.util.NoSuchElementException();
T nextItem = current.data;
current = current.next;
okToRemove = true;
return nextItem;
}
public void remove() {
if (!okToRemove)
throw new IllegalStateException();
LinkedList.this.remove(current.prev);
okToRemove = false;
}
}
public static void testReverse(){
LinkedList<Integer> lst = new LinkedList<>();
for (int i = 0; i < 10; i )
lst.add(i);
for (int i = 20; i < 30; i )
lst.add(0, i);
System.out.println("Testing reverse:");
System.out.println("Original list:");
// Should print [ 29 28 27 26 25 24 23 22 21 20 0 1 2 3 4 5 6 7 8 9 ]
System.out.println(lst);
lst.reverse();
System.out.println("After reversal:");
// Should print [ 9 8 7 6 5 4 3 2 1 0 20 21 22 23 24 25 26 27 28 29 ]
System.out.println(lst);
}
public static void main(String[] args) {
testReverse();
}
}
CodePudding user response：
public void reverse() {
Node current = beginMarker.next;
Node temp = null;
while (current != endMarker) {
temp = current.next; // store reference to next node
if (current == beginMarker.next) {
current.next = endMarker;
} else {
current.next = current.prev; // next points to previous node
}
current.prev = temp; // prev points to next node
current = temp; // current references temp (next node).
}
// changing references of beginning and end nodes
temp = beginMarker.next;
beginMarker.next = endMarker.prev;
endMarker.prev = temp;
/* TESTING THE PROGRAM, THIS PRINTS THE REVERSED LIST 'PROPERLY' BUT THE TESTER METHOD DOESN'T WORK */
current = beginMarker;
for (int i = 0; i <= size() 1; i ) {
System.out.println(current.data);
current = current.next;
/* END TEST */
}
}