В чем причина использования двойного указателя при добавлении узла в связанный список?

Question

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

пример кода 1:

struct node* push(struct node **head, int data)
{
        struct node* newnode = malloc(sizeof(struct node));
        newnode->data = data;
        newnode->next = *head;
        return newnode;
}

push(&head,1);

пример кода 2:

struct node* push(struct node *head, int data)
{
        struct node* newnode = malloc(sizeof(struct node));
        newnode->data = data;
        newnode->next = head;
        return newnode;
}

push(head,1)

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

Есть ли случаи, когда один указатель не работает, поэтому нам нужно использовать двойной указатель?

Answer 1

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

Пример:

void swap(int* a,int* b){
  int tmp=*a;
  *a=*b;
  *b=tmp;
}

int main(void){
  int a=10,b=20;

  // To ascertain that changes made in swap reflect back here we pass the memory address
  // instead of the copy of the values

  swap(&a,&b);
}

Аналогично передаем адрес памяти главы списка.

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

Таким образом, этот подход уменьшает вероятность утечек памяти, поскольку мы потеряли бы указатель на недавно выделенный узел, если бы мы забыли обновить Head в вызывающей функции.

Кроме того, второй код будет работать быстрее, поскольку при копировании и возврате не тратится время, поскольку мы работаем непосредственно с памятью.

Answer 2

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

#include <iostream>
#include <math.h>

using namespace std;

class LL
{
    private:
        struct node 
        {
            int value;
            node* next;
            node(int v_) :value(v_), next(nullptr) {};
        };
        node* head;

    public:
        LL() 
        {
            head = nullptr;
        }
        void print() 
        {
            node* temp = head;
            while (temp) 
            {
                cout << temp->value << " ";
                temp = temp->next;
            }
        }
        void insert_sorted_order(int v_) 
        {
            if (!head)
                head = new node(v_);
            else
            {
                node* insert = new node(v_);
                node** temp = &head;
                while ((*temp) && insert->value > (*temp)->value)
                    temp = &(*temp)->next;
                insert->next = (*temp);
                (*temp) = insert;
            }
        }

        void remove(int v_)
        {
            node** temp = &head;
            while ((*temp)->value != v_)
                temp = &(*temp)->next;
            node* d = (*temp);
            (*temp) = (*temp)->next;
            delete d;
        }

        void insertRear(int v_)//single pointer
        {
            if (!head)
                head = new node(v_);
            else
            {
                node* temp = new node(v_);
                temp->next = head;
                head = temp;
            }
        }
};

Answer 3

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

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