Реализация pop_back со связанным списком игнорирует указатель на nullptr
Давайте предположим, что мне разрешено использовать только new а также delete и никаких умных указателей в моей реализации. Я не использую дозорные узлы.
Ниже моя реализация для pop_back:
void sLinkedList::pop_back()
{
if(begin == nullptr)
{
std::cerr << "There is nothing to pop." << std::endl;
}
else
{
node* nodeToDelete = begin;
while(nodeToDelete->next != nullptr)
{
nodeToDelete = nodeToDelete->next;
}
delete nodeToDelete;
nodeToDelete = nullptr;
--mSize;
}
}
Что он делает, это создает указатель на узел nodeToDelete и выполняет итерацию по всему списку, пока не достигнет последнего узла (узла, который указывает на nullptr). Затем я удаляю этот последний узел, устанавливаю его равным nullptr, и все должно быть в порядке, потому что узел перед этим (ранее второй-последний узел) теперь указывает на nullptr, отмечая конец списка.
Когда я запустил основной со следующими инструкциями:
int main()
{
sLinkedList newList;
std::cout << "Length is " << newList.length() << std::endl;
newList.print();
newList.push_front(4);
std::cout << "Length is " << newList.length() << std:: endl;
newList.print();
newList.pop_back();
std::cout << "Length is " << newList.length() << std::endl;
newList.print();
}
Я получаю вывод:
Length is 0
The list is empty.
Length is 1
4
Length is 0
4 // should print "There is nothing to pop."Добавление другого pop_back непосредственно после первых результатов в Aborted (core dumped) сигнал.
Почему идея не работает?
Решение
Хорошо, но так ли?
Когда вы назначаете nodeToDelete = nodeToDelete-> next; вы говорите, что ваш локальный указатель nodeToDelete теперь ссылается на то же место в памяти, что и nodeToDelete-> next. Между этими двумя указателями нет никаких других отношений. Поэтому, когда вы затем назначаете nodeToDelete = nullptr; вы на самом деле ничего не делаете: этот локальный указатель больше никогда не используется, поэтому не имеет особого значения, на какую область памяти он указывает.
К сожалению, конечный узел, который должен быть, по-прежнему указывает на то место, где он использовался, даже если вы удалили этот узел, и поэтому ваш следующий вызов pop_back благополучно переходит в недоступную память.
Я предполагаю, что это домашнее задание, поэтому я не должен переписывать его для вас. Но вы можете исправить это, фактически изменив последний узел, а не просто локальную копию его следующего указателя.
Конечно, если это реальный проект, может помочь std :: forward_list. : v
Другие решения
все должно быть хорошо, потому что узел перед этим (ранее второй-последний узел) теперь указывает на nullptr, отмечая конец списка.
Хорошо, но так ли?
Когда вы назначаете nodeToDelete = nodeToDelete->next; вы говорите, что ваш локальный указатель nodeToDelete теперь относится к тому же месту в памяти, что и nodeToDelete->next, Между этими двумя указателями нет никаких других отношений. Поэтому, когда вы назначаете nodeToDelete = nullptr; вы на самом деле ничего не делаете: этот локальный указатель больше никогда не используется, поэтому не имеет особого значения, на какую область памяти он указывает.
К сожалению, конечный узел, который должен быть, по-прежнему указывает на то место, где он использовался deleteд этот узел, и поэтому ваш следующий pop_back Звонок счастливо перебирает в недоступную память.
Я предполагаю, что это домашнее задание, поэтому я не должен переписывать его для вас. Но вы можете исправить это, фактически изменив последний узел, а не просто локальную копию его next указатель.
Конечно, если это настоящий проект, std::forward_list может помочь. : v