在 java 中反转短双向链表时遇到内存不足错误

Question

我正在尝试反转双向链表并通过覆盖 toString 方法打印它。我在java中使用了一个实现双向链表的模板，只添加了一个方法：reverse().

我花了很多时间调试，并且能够正确打印出整个反转列表。但是，当 testReverse() 函数运行并在新的反向列表上调用覆盖的 toString() 方法时，我收到 java.lang.outofmemoryerror java heap space 错误。我已经包括了我在下面使用的双向链表的整个实现，但我几乎可以肯定这个问题与我的算法有关。

任何和所有见解或建议将不胜感激。谢谢！

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();
    }
}

Answer 1

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 */
        }
    }