Добавление узла в связанный список без явного выделения пространства памяти (без использования нового)

Question

Итак, я учился составлять связанный список, и мне было интересно, почему мы должны использовать «новый» при добавлении узла. Ниже приведена функция, которая правильно добавляет узел:

void addNode(int value){

    Node* new_node_ptr = new Node;

    new_node_ptr->value = value;

    if (root == NULL){
        root = new_node_ptr;
        traveler = new_node_ptr;
    } else {
        traveler->next = new_node_ptr;
        traveler = new_node_ptr;
    }
}

Но, поскольку я новичок в c ++, когда я попытался выяснить, как сделать это самостоятельно, вместо строки:

Node* new_node_ptr = new Node;

Я написал:

Node new_node;
Node* new_node_ptr = &new_node;

Это не работает. Кажется, что переменная new_node продолжает присваиваться одному и тому же адресу памяти каждый раз, когда вы пытаетесь добавить новый узел. Это одновременно увлекательно и бесит. Кто-нибудь может объяснить мне эту странную с ++ странность?

Спасибо!

Answer 1

Когда вы пишете

Node new_node;

Переменная создается в стеке и не должна использоваться после выхода addNode.addNode теряет «владение» этой памятью после выхода из функции, и память, связанная с new_node, может снова использоваться другими частями вашей программы.Попытка использовать его - неопределенное поведение, на которое нельзя положиться.

Необходимо динамически распределять память, чтобы срок действия данных выходил за рамки функции.

Во втором случае с выделением стека, если new_node всегда назначается память втот же адрес, вот как это происходит в вашем тестовом случае.В зависимости от порядка вызова других функций до addNode, это может происходить не всегда и, скорее всего, не всегда будет в «реальной программе».

Answer 2

Node* new_node_ptr = new Node;

Вышеприведенное означает «создать новый объект узла и хранить его неограниченно долго».

Node new_node;
Node* new_node_ptr = &new_node;

Выше не означает «создать новый объект узла и держать его бесконечно долго».

Если бы обе версии делали то, что вы от них хотите, то теперь , что будет странным, потому что тогда конструкция new, по-видимому, не будет служить никакой законной цели.

Answer 3

Когда вы объявляете переменную без использования new , вы сохраняете часть памяти, выделенную в стеке . Переменные, хранящиеся в стеке, находятся внутри функции, но не снаружи (например, счетчик, итераторы и т. Д.).

Когда вы объявляете с помощью new , вы сохраняете часть памяти, выделенную в куче . Переменные, хранящиеся в куче, могут быть доступны во всей вашей программе (и, в некоторых случаях, в других программах).

Более подробную информацию вы можете найти по следующей ссылке: https://www.gribblelab.org/CBootCamp/7_Memory_Stack_vs_Heap.html