从单链表扩展创建双链表-获取空指针

Question

我一直试图利用我以前的单链表来创建双向链表。因此，在Node类中，我添加了以前的节点引用，并更新了List类中的add和插入方法，以适应在DoublyLinked列表类中的来回。add将新节点放在当前节点之后，并将新节点放在列表类中当前节点之前；这是因为我想在DoublyLinked中以升序添加和插入我的值列表类。[这可能听起来很混乱，但我会在下面发布代码]当我测试我的add方法[在DoublyLinked类]我得到一个空指针异常。

正如我所说，我已经为此工作了几天，所以在这段时间里，我考虑了前面的这些问题：

1. 如何将单链接列表更改为双链接列表

列表JAVA

public class List<T> implements ListInterface<T> {
        protected class Node {
        private T value = null;
        private Node prev = null;
        private Node next = null;

        public T getValue( ) {
            return value;
        }

        public Node getPrev( ) {
            return prev;
        }

        public Node getNext( ) {
            return next;
        }

        public void setValue( T newValue ) {
            value = newValue;
        }

        public void setPrev( Node prevNode ) {
            prev = prevNode;
        }

        public void setNext( Node nextNode ) {
            next = nextNode;
        }
    }

    protected Node head = null;
    protected Node cur  = null;
    protected int      size = 0;

    // add after cur
    @Override
    public void add( T value ) {
        Node temp = new Node( );
        temp.setValue( value );
        size++ ;
        if (isEmpty( )) {
            head = temp;
            cur = temp;
        } else {
            temp.setNext(cur.getNext());
            temp.setPrev(cur);
            cur.setNext(temp);
            cur = temp;
        }
    }

    // insert before cur
    @Override
    public void insert( T value ) {
        Node temp = new Node( );
        temp.setValue( value );
        size++ ;
        if (isEmpty( )) {
            head = temp;
            cur = temp;
        } else if (head == cur) {
            head = temp;
            head.setNext( cur );
            cur.setPrev(head);
            cur = head;
        } else {
            Node prev = head;
            while( prev.getNext( ) != cur ) {
                prev = prev.getNext( );
            }
            temp.setNext( prev.getNext( ) );
            temp.setPrev(prev);
            prev.setNext( temp );
            cur = temp;
        }
    }
}

双倍inked.java

public class DoublyLinked<T extends Comparable<T>> 
extends List<T> implements ListInterface<T> {

    private int size;
    private Node tail;

    DoublyLinked() {
        this.size = 0;
        this.tail = null;
    }

    @Override
    public void add(T value) {
        size++;

        reset();
        // getting Null pointer on add when doublinked list is empty
        if(isEmpty()) {
            super.add(value);
            head = cur;
            tail = head;
            cur = head;
        }
        else {
            try {
                while(value.compareTo(get()) > 0 && hasNext()) { // error here
                    next();
                    if(value.compareTo(get()) <= 0) {
                        super.add(value);
                        // how to set cur to this new node?
                    }
                }
            } catch (EmptyListException | EndOfListException e) {}  
            super.add(value); // add at end of list
            tail = cur;
            cur = tail;
        }
    }

    @Override
    public T get() throws EmptyListException {
        return cur.getValue();
    }

    @Override
    public T next() throws EmptyListException, EndOfListException {
        if (!hasNext( )) {
            throw new EndOfListException( );
        }
        cur = cur.getNext( );
        return cur.getValue( );
    }

    @Override
    public boolean hasNext() {
        return((!isEmpty()) && (cur.getNext() != null));
    }

    @Override
    public void reset() {
        cur = head;
    }

    @Override
    public boolean isEmpty() {
        return size ==  0;
    }
}

然后我有一个基本的JUnit测试来测试代码：

import static org.junit.Assert.*;

import org.junit.Test;


public class DoublyLinkedTest {

    @Test
    public void testAdd() {
        DoublyLinked<Integer> list = new  DoublyLinked<Integer>();
        list.add(1);
    }
}

Answer 1

您递增size，然后调用isAir ty（）（检查size是否为零）来决定如何添加该项：

    size++ ;
    if (isEmpty( )) {