Как удалить первый элемент однонаправленного списка в с++?

Question

[Menfice]

Как следует из вопроса - у меня возникла трудность с удалением именно первого элемента, все прочие удаляются без проблем. Код с моими комментариями вот здесь с пометкой // ? в месте проблемы. Задачу решал методом "работает - не трогай", поэтому заранее прошу прощения за то, что вы там можете увидеть).
Пробовал способом:

if (curr->val == to_del) {
			node* temp = curr;
			curr = curr->next;
			delete temp;
		}

Но, хоть и, на мой взгляд, это выглядит логичным методом, оно не помогает.

Answer 1

[Wataru]

С односвязными списками сложно - надо знать предыдущий элемент, чтобы у него поменять ссылку на следующий через удаляемый элемент. Можно или поддерживать 2 указателя на 2 соседних элемента, или смореть на следующий элемент через next, пока у вас есть указатель на предыдущий к нему.

Еще отдельная проблема с удалением первого элемента, потому что там менятся должна не ссылка next у предыдущего элемента, а ссылка на начало списка. Эту проблему можно решить по разному. Например, можно вместо указателя head держать один элемент списка без значения. Тогда указатель на начало списка будет менятся также как и любой другой. Фактически, в любом списке всегда будет один фиктивный элемент. Этот способ также предподчителен для работы с двусвязными списками. Тогда список как бы замыкается в кольцо и не надо разбирать отдельно ни случай первого, ни случай последнего элемента. Мне больше нравится другой метод - можно помнить не предыдущий элемент, а указатель-на-указатель, который надо будет поменять.

node** prev_link = &head;
node* cur = head;
for  (node* cur = head; cur != nullptr; cur = cur->next) {
  if (cur->val == to_del) {
    *prev_link = cur->next;
    delete cur;
    break;
  }
  prev_link = &cur->next;
}

Comments

[Menfice]

Спасибо большое)

Answer 2

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

Нужно два разных варианта кода – для первого элемента и для остальных. Твой код правильный для первого элемента. Осталось написать для остальных.

Comments

[Menfice]

да, я понимаю это, но вопрос как раз в том - как этот самый вариант должен выглядеть?

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

Kiber Cyber, нужно помнить предыдущий элемент и текущий. next предыдущего присвоить next текущего. Удалить текущий.