Вдвойне LL вставка в конце застрял на петле

Question

Не могу понять, почему вставка узла в конце двусвязного списка застревает в цикле. Либо он застрял в цикле, либо нулевой указатель. Также я хотел бы знать, является ли публичный Node лучше или публичным недействительным при работе со связанными списками или какими-либо структурами данных.

public Node insertEnd(int data) {
    Node newNode = new Node(data);
    newNode.next = null;
    if (head == null) {
        head = newNode;
        return newNode;
    }

    Node last = head;
    while(last!=null) {
        last = last.next;
        last.next = newNode;
    }
    newNode.previous = last;
    return newNode;
}

Answer 1

Чтобы ответить на 1 часть, вам необходимо внести следующие изменения в свой код -

 Node last = head;
    while(last.next!=null) { // be careful- it should be last.next!=null instead of last!=null , as it will give null pointer exception.
        last = last.next;    
    }
    last.next = newNode;
    newNode.previous = last;
    return newNode;

как оператор "last.next = newNode;" в то время как цикл устанавливал последнюю в newNode в самой первой итерации.

для 2-й части вашего вопроса, это зависит от требования вызова функции.

Answer 2

Ну, это из-за этой части логики

    Node last = head;
    while(last!=null) {
        last = last.next;
        last.next = newNode; //// This shouldn't happen.
    }

Как только связанный список уже создан, вы пытаетесь перейти к последнему элементу. Однако во время этого обхода вы также изменили следующий указатель, на который указывал узел.

Попробуйте изменить свою логику на:

public Node insertEnd(int data) {
    Node newNode = new Node(data);
    newNode.next = null;
    if (head == null) {
        head = newNode;
        return newNode;
    }

    Node last = head;
    while(last.next != null) {
        last = last.next;
    }
    last.next = newNode;
    newNode.previous = last;
    return newNode;
}

Answer 3

Что касается второй части вопроса, это зависит от того, каким образом клиент / вызывающая сторона этого API будет ожидать вывода.

Вы пишете этот API для использования в другой программе, которую пишете? В этом случае подумайте, будет ли вам полезно получить вновь созданный узел в качестве возвращаемого значения этого API или допустимо оставить его недействительным.

Для справки, Java-реализация API имеет void в качестве возвращаемого типа. (https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html#addLast(E))

Answer 4

В вашем while цикле:

while(last!=null) {
    last = last.next;
    last.next = newNode;
}

Вторая строка устанавливает last.next на newNode, поэтому на следующей итерации last будет установлено на newNode, поле next которого равно нулю. Вы хотите установить last.next на newNode только один раз last.next == null (Когда вы достигнете конца списка):

while(last.next != null) {
   last = last.next;
}
last.next = newNode;