Почему динамическое распределение используется для связанных списков?

Question

Struct node { char ch; node *link;}; 

node * temp = new node; 
node *temp1; 

Мой вопрос в том, почему мы используем первый способ объявления динамической структуры, а не второй. Я попытался использовать второй, связанный с классом, чтобы имитировать стек, но функция display() превратила его в бесконечный цикл, в то время как использование первого исправляло его. Зачем?

Answer 1

Ваш вопрос не совсем понятно, но это

Node *temp1; 

просто создает указатель, который не указывает на Node объекта. Фактически, это указывает на место, которое вы можете считать случайным. Вы не можете удалить ссылку на этот указатель, сначала нужно указать на Node.

Это, с другой стороны

Node * temp = new Node; 

динамически выделяет Node на РИТ, возвращая указатель на Node, значение которого используется для инициализации temp. Таким образом, temp указывает на действительный объект Node. Имейте в виду, что в какой-то момент вам нужно будет позвонить delete обо всем, что выделено new. В современном C++ вы избегаете этого ручного управления памятью и делегируете его типу, например интеллектуальному указателю.

Примечание Вышеупомянутый предполагает, что указанный тип называется Node, а не node.

Answer 2

Связанный список МОЖЕТ быть построен без использования new, но в большинстве случаев это не очень практичное решение. Причина, по которой мы используем связанные списки (и деревья, и другие «связанные» структуры данных), должна иметь некоторый способ хранения произвольного количества элементов в структуре, где легко добавлять/удалять элементы в середине. Если бы это было не так, мы могли бы использовать массив или вектор.

Мы могли бы сделать короткий связный список, делая это:

Node a, b, c; 
Node *head = &a; // Head is the pointer to the first element. 
a.link = &b; 
b.link = &c; 
c.link = NULL; 
// Clearly we want to set ch in each node as well, but I'm ignoring it for shortness. 

Но это становится очень грязным, если мы не знаем, сколько ссылок нам нужно.

Итак, мы используем кучу для выделения элементов, потому что мы не знаем заранее, сколько они.

Связанный список использует указатели на «ближайшие» (или «предыдущие») узлы в списке - таким образом мы можем легко вставить элемент в середине списка. Или удалите элемент из середины.

В векторе из 1000 элементов, чтобы удалить первый элемент означает перемещение 999 элементов «на один шаг». Для удаления первого элемента в связанном списке требуется существенно одно изменение: переместите головку списка в следующий элемент.

Удаление 500-го элемента вектора требует перемещения 499 элементов на «один шаг». Удаление 500-го элемента связанного списка требует, чтобы ссылка из 499-го была пропечена, чтобы указать на 501-й элемент. Это займет одну операцию. (Конечно, нам также нужно найти правильный элемент для удаления, но если элементы в векторе не отсортированы каким-то образом, что помогает искать, это по существу то же самое).