双链表实现不起作用

Question

我有一个双向链表实现如下：

public class DoublyLinkedList<T> {
    DoublyLinkedListNode<T> head;

    public DoublyLinkedListNode<T> getHead() {
        return head;
    }

    public void setHead(DoublyLinkedListNode<T> head) {
        this.head = head;
    }

    public void addNode(DoublyLinkedListNode<T> node) {
        if(null == head) {
            head = new DoublyLinkedListNode<>(node.getData());
        }else{
            traverseAndAdd(node);
        }
    }

    private boolean traverseAndAdd(DoublyLinkedListNode<T> node) {
         boolean isAdded = false;
    DoublyLinkedListNode<T> tempHead = head;
  do{
        if(tempHead.getNext() == null) {
            head.setNext(node);
            node.setPrev(head);
            isAdded = true;
            break;
        }

         tempHead = tempHead.getNext();
    }while(null != tempHead);

    return isAdded;
    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        while(null != head) {
            sb.append(head.getData());
            head = head.getNext();
        }

        return sb.toString();
    }

}

下面是我的DoublyLinkedListNode类：

public class DoublyLinkedListNode<T> {

    T data;
    DoublyLinkedListNode<T> prev;
    DoublyLinkedListNode<T> next;

    public DoublyLinkedListNode(T data) {
        this.data = data;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public DoublyLinkedListNode<T> getPrev() {
        return prev;
    }

    public void setPrev(DoublyLinkedListNode<T> prev) {
        this.prev = prev;
    }

    public DoublyLinkedListNode<T> getNext() {
        return next;
    }

    public void setNext(DoublyLinkedListNode<T> next) {
        this.next = next;
    }
}

现在，当我创建DoublyLinkedList的实例并尝试向其添加节点时，我的头部实例变量始终为null。

即使我在addNode方法中初始化它，当我尝试添加下一个节点时，它总是为null。

有人可以告诉我这个实现是否有任何问题。

下面是我如何添加节点到我的列表：

DoublyLinkedList<Integer> mylist = new DoublyLinkedList<>();
DoublyLinkedListNode<Integer> node1 = new DoublyLinkedListNode<>(10);
DoublyLinkedListNode<Integer> node2= new DoublyLinkedListNode<>(20);
DoublyLinkedListNode<Integer> node3 = new DoublyLinkedListNode<>(30);
DoublyLinkedListNode<Integer> node4 = new DoublyLinkedListNode<>(40);
DoublyLinkedListNode<Integer> node5 = new DoublyLinkedListNode<>(50);
DoublyLinkedListNode<Integer> node6 = new DoublyLinkedListNode<>(60);
mylist.addNode(node1);
mylist.addNode(node2);
mylist.addNode(node3);
mylist.addNode(node4);
mylist.addNode(node5);
mylist.addNode(node6);
System.out.println(mylist.toString());

Answer 1

这有效

class DoublyLinkedList <T> {

    DoublyLinkedListNode<T> head;

    public DoublyLinkedListNode<T> getHead() {
        return head;
    }

    public void setHead(DoublyLinkedListNode<T> head) {
        this.head = head;
    }

    public void addNode(DoublyLinkedListNode<T> node) {
        if (null == head) {
            head = new DoublyLinkedListNode<>(node.getData());
        } else {
            traverseAndAdd(node);
        }
    }

    private boolean traverseAndAdd(DoublyLinkedListNode<T> node) {

        boolean isAdded = false;

        for (DoublyLinkedListNode<T> it = head; it != null; it = it.getNext()) {
            if(null == it.getNext()) {
                it.setNext(node);
                node.setPrev(it);
                isAdded = true;
                break;
            }
        }

        return isAdded;
    }

    @Override
    public String toString() {

        StringBuffer sb = new StringBuffer();

        for (DoublyLinkedListNode<T> it = head; it != null; it = it.getNext()) {
            sb.append(it.getData() + "\n");
        }

        return sb.toString();

    }
}

class DoublyLinkedListNode <T> {

    T data;
    DoublyLinkedListNode<T> prev;
    DoublyLinkedListNode<T> next;

    public DoublyLinkedListNode(T data) {
        this.data = data;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public DoublyLinkedListNode<T> getPrev() {
        return prev;
    }

    public void setPrev(DoublyLinkedListNode<T> prev) {
        this.prev = prev;
    }

    public DoublyLinkedListNode<T> getNext() {
        return next;
    }

    public void setNext(DoublyLinkedListNode<T> next) {
        this.next = next;
    }
}

public class Main {

    public static void main(String []args) {
        DoublyLinkedList<Integer> mylist = new DoublyLinkedList<>();

        DoublyLinkedListNode<Integer> node1 = new DoublyLinkedListNode<>(10);
        DoublyLinkedListNode<Integer> node2 = new DoublyLinkedListNode<>(20);
        DoublyLinkedListNode<Integer> node3 = new DoublyLinkedListNode<>(30);
        DoublyLinkedListNode<Integer> node4 = new DoublyLinkedListNode<>(40);
        DoublyLinkedListNode<Integer> node5 = new DoublyLinkedListNode<>(50);
        DoublyLinkedListNode<Integer> node6 = new DoublyLinkedListNode<>(60);
        mylist.addNode(node1);
        mylist.addNode(node2);
        mylist.addNode(node3);
        mylist.addNode(node4);
        mylist.addNode(node5);
        mylist.addNode(node6);

        System.out.println(mylist.toString());
        System.out.println(mylist.toString());
    }
}

Answer 2

您的头引用并不总是为null，它会在初始化时添加第一个节点，代码中的问题在traverseAndAdd（）方法中。

private boolean traverseAndAdd(DoublyLinkedListNode<T> node) {
    boolean isAdded = false;
    while(null != head.getNext()) {
        if(head.getNext() == null) {
            //this code is unreachable
        }
        //why are u changing the head value
        head = head.getNext();
    }
    return isAdded;
}

所以用。替换功能

private void traverseAndAdd(DoublyLinkedListNode<T> node) {
    DoublyLinkedListNode<T>temp=head;
    while(null != temp.getNext()) {
        temp=temp.getNext();
    }
    temp.setNext(node);
    node.setPrev(temp);
}

另一个错误，在toString（）方法中，您将空值赋给head。 head值首先被初始化，但每次调用toString（）时都变为null。用方法替换方法

public String toString() {
    StringBuffer sb = new StringBuffer();
    DoublyLinkedListNode<T>temp=head;
    while(null != temp) {
        sb.append(temp.getData());
        temp = temp.getNext();
    }
    return sb.toString();
}