почему мне нужно вернуть голову в связанном списке? c ++

Question

NODE* InsertAtHead(NODE* &head, int val){
    NODE *tmp = new NODE;

    //create a new node
    if (tmp == NULL)
        exit(1);

    //Initialize the new node
    tmp->data = val;
    tmp->next = NULL;

    //Insert by changing links
    tmp->next = head;
    head = tmp;         //update head
    return head;
}

Почему в конце концов нам нужно поставить возвратную головку?

Answer 1

Связанный список (когда люди говорят связанный список, они обычно имеют в виду один связанный список) имеет ссылку на следующий узел и не имеет ссылки на предыдущий. Итак, представьте, что если вы вернете узел, который находится в середине списка, вы можете перейти к следующему и следующему полностью до конца, это хорошо. Проблема заключается в том, что вы не сможете перейти к предыдущему узлу, если у вас нет ссылки на него, что сделает его двойным связанным списком или если у вас есть указатель на head первый узел в списке, который будет служить начать.

В вашем случае вы перемещаете узлы в начало списка, поэтому ваш код перемещает предыдущую головку в следующую и делает новый узел головным узлом.

EDIT: head должен быть передан по ссылке. val должно быть передано по значению. Зачем? Для head нам нужен адрес, чтобы мы могли сделать ссылку на него. Для val, если мы передадим его по ссылке, адрес может быть повторно использован в функции вызывающей стороны, и мы не хотим, чтобы наши данные изменились.

Answer 2

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

В этой функции вы готовите, что создает новое начало. Если вы не вернете новое начало, то вызывающая функция не будет знать об этом элементе.

Это очень важно, так как вы используете new для выделения памяти, и если он не будет освобожден, произойдет утечка памяти. Он не может быть освобожден, если вызывающая функция не имеет этого указателя.