Как удалить последний элемент в стеке, на основе односвязного списка?

Question

[Андрей Кулагин]

Метод должен возвращать значение и удалять его из коллекции

public T deleteLast() throws NoSuchElementException {
if (head == null) {
throw new NoSuchElementException("Список пуст");
}

Node ref = head;
for (int i = 0; i < size; i++) {
ref = ref.next;
}
size--;
T temp = ref.value;
ref.next = null;
return temp;
}

Есть тест:

@Test
public void whenPushPollThenPushPoll() {
SimpleStack stack = new SimpleStack<>();
stack.push(1);
stack.pop();
stack.push(2);
assertThat(stack.pop(), is(2));
}

Тест не работает так как не правильно реализован метод deleteLast(), вероятно не правильно удаляю последнюю node (я это делаю с помощью ref.next = null;

Answer 1

[Тимур Покровский]

Может так?
for (int i = 0; i < size - 1; i++) {...}

Comments

[Андрей Кулагин]

нет, так не работает тоже
Предполагаю, что надо правильно удалить последнюю ноду как-то

Answer 2

[Денис Загаевский]

В стеке нет операции удаления последнего элемента. В односвязном списке это вообще максимально затратная операция, зачем она?
Дальше, в тесте ты эту функцию не используешь.
Функция в любом случае реализована в корне неверно.
Нужно учитывать граничный случай size == 1 и обнулять head. Нужно итерироваться (size - 2) раз, чтобы встать на предпоследний элемент, и у него занулить next. Нужно брать value у элемента, следующего за тем, у которого обнуляется next. То есть у самого next'a.

Comments

[Андрей Кулагин]

public T deleteLast() throws NoSuchElementException {
if (head == null) {
throw new NoSuchElementException("Список пуст");
}
if (size == 1) {
head = null;
}
Node ref = head;
for (int i = 0; i < size - 2; i++) {
ref = ref.next;

}
ref.next = null;
size--;
return ref.next.next.value;
}

[Денис Загаевский]

Андрей Шалыгин, очевидно, что оно не работает. Не пойму, ты хочешь, чтобы написал за тебя?