Как разместить узел в стеке, не получив NPE

Question

Это метод pop для реализации стека в связанном списке.

Этот метод генерирует NPE, когда "количество всплывающих окон" равно "размеру связанного списка".

Пример:

LinkedList list = new LinkedList();
        list.push("A");
        list.push("B");
        list.push("C");

        System.out.println(list.pop().getElement());
        System.out.println(list.pop().getElement());
        // the below code list.pop will have a null value.
        System.out.println(list.pop().getElement());
        System.out.println(list.pop().getElement());

public boolean isEmpty()
{
        return head == null;
}

public Node pop()
{

                if( !isEmpty())
                {
                    head = head.getNext();
                    size--;
                }
                else if(isEmpty())
                {
                    System.out.println("empty stack");

                }

                 return  head;

}

Мое решение состояло в том, чтобы переписать как это, но теперь есть дублированный код для возврата, который я понятия не имею, чтобы исправить. Любое руководство по этому вопросу поможет.

 public Node pop()
 {

                if(head != null)
                {
                    return head;
                }
                if( !isEmpty())
                {
                    head = head.getNext();
                    size--;
                }
                else if(isEmpty())
                {
                    System.out.println("empty stack");

                }

                 return  head;

 }

Другой вопрос: не уверен, должен ли я называть переменную head(концепция связанного списка) или top(концепция стека)? Пожалуйста, ответьте и на этот вопрос.

Мой аргумент для тех, кому может быть интересно, почему я возвращаю объект узла, который будет удален позже: в моем учебнике написано, что pop означает, что мне нужно вернуть извлеченный узел, а также удалить его из связанного списка, а не просто удалить его.

Answer 1

В вашей первой реализации:

public Node pop()
{
    if( !isEmpty())
    {
        head = head.getNext();
        size--;
    }
    else if(isEmpty())
    {
        System.out.println("empty stack");

    }

     return  head;

}

Представьте, что ваш список 5->6->7->null,

Голова указывает на 5, Этот список не пуст. Итак, вы делаете head = head.getNext()Теперь голова указывает на 6. А потом вы возвращаетесь head, который 6,

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

---

В вашей второй реализации:

public Node pop()
 {
    if(head != null)
    {
        return head;
    }
    if( !isEmpty())
    {
        head = head.getNext();
        size--;
    }
    else if(isEmpty())
    {
        System.out.println("empty stack");

    }

     return  head;

 }

Если голова не нулевая, вы просто возвращаетесь, не продвигаясь вперед. Как только вы используете returnбольше ничего не будет сделано в методе.

---

Примечание. Было бы лучше вместо возврата узла возвращать тот же тип, что и вы. push, Возвращение Node дает пользователю опасный доступ к вашему связанному списку. Вместо этого вы должны вернуть фактический элемент.

Answer 2

В методе popты не возвращаешься headвозвращаешься head.getNext(),

Так что измени свою логику. Вы можете попробовать это:

В методе pop

Node tem = head;
if( !isEmpty())
    {
        head = head.getNext();
        size--;
    }
    else // no need to check head again
    {
        System.out.println("empty stack");

     }

     return  tem;