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

Ответ 1

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

// note that there no return value: it not needed
void push(struct node** head, int data)
{
    struct node* newnode = malloc(sizeof(struct node));
    newnode->data=data;
    newnode->next=*head;
    *head = newnode; // *head stores the newnode in the head
}

// and call like this:
push(&head,1);

Реализация, которая не принимает указателя на указатель головы, должна возвращать новый заголовок, а вызывающий отвечает за его обновление:

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

// note the assignment of the result to the head pointer
head = push(head,1);

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

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

Ответ 2

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

struct node* push(struct node** head, int data)
{
struct node* newnode = malloc(sizeof(struct node));
newnode->data=data;
newnode->next=*head;
//vvvvvvvvvvvvvvvv
*head = newnode; //you say that now the new node is the head.
//^^^^^^^^^^^^^^^^
return newnode;
}

Ответ 3

Возьмем этот простой пример:

void my_func(int *p) {
        // allocate space for an int
        int *z = (int *) malloc(sizeof(int));
        // assign a value
        *z = 99;

        printf("my_func - value of z: %d\n", *z);

        printf("my_func - value of p: %p\n", p);
        // change the value of the pointer p. Now it is not pointing to h anymore
        p = z;
        printf("my_func - make p point to z\n");
        printf("my_func - addr of z %p\n", &*z);
        printf("my_func - value of p %p\n", p);
        printf("my_func - value of what p points to: %d\n", *p);
        free(z);
}

int main(int argc, char *argv[])
{
        // our var
        int z = 10;

        int *h = &z;

        // print value of z
        printf("main - value of z: %d\n", z);
        // print address of val
        printf("main - addr of z: %p\n", &z);

        // print value of h.
        printf("main - value of h: %p\n", h);

        // print value of what h points to
        printf("main - value of what h points to: %d\n", *h);
        // change the value of var z by dereferencing h
        *h = 22;
        // print value of val
        printf("main - value of z: %d\n", z);
        // print value of what h points to
        printf("main - value of what h points to: %d\n", *h);


        my_func(h);

        // print value of what h points to
        printf("main - value of what h points to: %d\n", *h);

        // print value of h
        printf("main - value of h: %p\n", h);


        return 0;
}

Вывод:

main - value of z: 10
main - addr of z: 0x7ffccf75ca64
main - value of h: 0x7ffccf75ca64
main - value of what h points to: 10
main - value of z: 22
main - value of what h points to: 22
my_func - value of z: 99
my_func - value of p: 0x7ffccf75ca64
my_func - make p point to z
my_func - addr of z 0x1906420
my_func - value of p 0x1906420
my_func - value of what p points to: 99
main - value of what h points to: 22
main - value of h: 0x7ffccf75ca64

мы имеем эту подпись для my_func:

void my_func(int *p);

Если вы посмотрите на результат, в конце, значение, на которое указывает h, равно 22, а значение h - одно и то же, хотя в my_func оно было изменено. Почему?

Ну, в my_func мы манипулируем значением p, которое является только локальным указателем. после вызова:

my_func(ht);

в main(), p будет удерживать значение h, которое представляет адрес переменной z, объявленной в основной функции.

В my_func(), когда мы меняем значение p, чтобы удерживать значение z, которое является указателем на местоположение в памяти, для которого мы выделили пространство, мы не изменяем значение h, что мы прошли, но только значение локального указателя p. В принципе, p больше не удерживает значение h, оно будет содержать адрес ячейки памяти, на которую указывает z.

Теперь, если мы немного изменим наш пример:

#include <stdio.h>
#include <stdlib.h>

void my_func(int **p) {
    // allocate space for an int
    int *z = (int *) malloc(sizeof(int));
    // assign a value
    *z = 99;

    printf("my_func - value of z: %d\n", *z);

    printf("my_func - value of p: %p\n", p);
    printf("my_func - value of h: %p\n", *p);
    // change the value of the pointer p. Now it is not pointing to h anymore
    *p = z;
    printf("my_func - make p point to z\n");
    printf("my_func - addr of z %p\n", &*z);
    printf("my_func - value of p %p\n", p);
    printf("my_func - value of h %p\n", *p);
    printf("my_func - value of what p points to: %d\n", **p);
    // we are not deallocating, because we want to keep the value in that
    // memory location, in order for h to access it.
    /* free(z); */
}

int main(int argc, char *argv[])
{
    // our var
    int z = 10;

    int *h = &z;

    // print value of z
    printf("main - value of z: %d\n", z);
    // print address of val
    printf("main - addr of z: %p\n", &z);

    // print value of h.
    printf("main - value of h: %p\n", h);

    // print value of what h points to
    printf("main - value of what h points to: %d\n", *h);
    // change the value of var z by dereferencing h
    *h = 22;
    // print value of val
    printf("main - value of z: %d\n", z);
    // print value of what h points to
    printf("main - value of what h points to: %d\n", *h);


    my_func(&h);

    // print value of what h points to
    printf("main - value of what h points to: %d\n", *h);

    // print value of h
    printf("main - value of h: %p\n", h);
    free(h);


    return 0;
}

мы имеем следующий результат:

main - value of z: 10
main - addr of z: 0x7ffcb94fb1cc
main - value of h: 0x7ffcb94fb1cc
main - value of what h points to: 10
main - value of z: 22
main - value of what h points to: 22
my_func - value of z: 99
my_func - value of p: 0x7ffcb94fb1c0
my_func - value of h: 0x7ffcb94fb1cc
my_func - make p point to z
my_func - addr of z 0xc3b420
my_func - value of p 0x7ffcb94fb1c0
my_func - value of h 0xc3b420
my_func - value of what p points to: 99
main - value of what h points to: 99
main - value of h: 0xc3b420

Теперь мы фактически изменили значение, которое h имеет, из my_func, следующим образом:

• измененная подпись функции
• вызов из main(): my_func (& h); В основном мы передаем адрес h указателя на двойной указатель p, объявленный как параметр в сигнатуре функции.
• в my_func() мы делаем: * p = z; мы разыменовываем двойной указатель p на один уровень. В основном это было переведено так, как вы бы сделали: h = z;

Значение p теперь содержит адрес h-указателя. h указатель имеет адрес z.

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

Ответ 4

Как @R. Мартинхо Фернандес указал в своем ответе, указав указатель на аргумент в void push(struct node** head, int data) позволяет вам менять указатель head непосредственно из функции push вместо того, чтобы возвращать новый указатель.

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

КСТАТИ: Если посчитать с Линус Торвальдс мнению, вы бы лучше узнать, как использовать указатель на указатель. ;-)

Линус Торвальдс: (...) На противоположном конце спектра я на самом деле желаю, чтобы больше людей понимали действительно основной низкоуровневый вид кодирования. Не большой, сложный материал, такой как беззаботный поиск имени, но просто хорошее использование указателей для указателей и т.д. Например, я видел слишком много людей, которые удаляют запись с односвязным списком, отслеживая запись "prev", а затем удалить запись, сделав что-то вроде

if (prev)
prev->next = entry->next;
else
list_head = entry->next;

и всякий раз, когда я вижу такой код, я просто иду "Этот человек не понимает указателей". И это, к сожалению, довольно распространено.

Люди, которые понимают указатели, просто используют "указатель на указатель ввода" и инициализируют это с адресом list_head. И затем, когда они пересекают список, они могут удалить запись без каких-либо условностей, просто сделав "* pp = entry-> next". (...)

Другие ресурсы, которые могут быть полезны:

• C двойные указатели
• Указатели на указатели
• Зачем использовать двойной указатель? или Зачем использовать указатели для указателей?

Ответ 5

Хотя предыдущие ответы достаточно хороши, я думаю, что гораздо легче думать о терминах "копировать по значению".

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

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

Надеюсь, это ответит не только на ваш вопрос, но и на другие вопросы, связанные с указателем.

Ответ 6

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

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

Ответ 7

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

#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;
            }
        }
};

Ответ 8

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

Пример:

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);
}

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

Таким образом, если добавлен какой-либо node и значение "Голова" изменено, тогда это изменение "Отражает назад", и нам не нужно вручную reset Head внутри вызывающей функции.

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

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

Ответ 9

Наблюдение и поиск, ПОЧЕМУ...

Я решил сделать некоторые эксперименты и сделать некоторые выводы,

ЗАМЕЧАНИЕ 1 - Если связанный список не пуст, мы можем добавить в него узлы (очевидно, в конце), используя только один указатель.

int insert(struct LinkedList *root, int item){
    struct LinkedList *temp = (struct LinkedList*)malloc(sizeof(struct LinkedList));
    temp->data=item;
    temp->next=NULL;
    struct LinkedList *p = root;
    while(p->next!=NULL){
        p=p->next;
    }
    p->next=temp;
    return 0;
}


int main(){
    int m;
    struct LinkedList *A=(struct LinkedList*)malloc(sizeof(struct LinkedList));
    //now we want to add one element to the list so that the list becomes non-empty
    A->data=5;
    A->next=NULL;
    cout<<"enter the element to be inserted\n"; cin>>m;
    insert(A,m);
    return 0;
}

Его просто объяснить (Basic). У нас есть указатель на нашу основную функцию, которая указывает на первый node (корень) списка. В функции insert() мы передаем адрес корня node и используя этот адрес, мы доходим до конца списка и добавляем к нему node. Таким образом, мы можем заключить, что если мы имеем адрес переменной в функции (а не главную функцию), мы можем внести постоянные изменения в значение этой переменной из этой функции, которая отразится на основной функции.

ЗАМЕЧАНИЕ 2 - Вышеупомянутый метод добавления node завершился неудачно, когда список был пуст.

int insert(struct LinkedList *root, int item){
    struct LinkedList *temp = (struct LinkedList*)malloc(sizeof(struct LinkedList));
    temp->data=item;
    temp->next=NULL;
    struct LinkedList *p=root;   
    if(p==NULL){
        p=temp;
    }
    else{
      while(p->next!=NULL){
          p=p->next;
      }
      p->next=temp;
    }
    return 0;
}



int main(){
    int m;
    struct LinkedList *A=NULL; //initialise the list to be empty
    cout<<"enter the element to be inserted\n";
    cin>>m;
    insert(A,m);
    return 0;
}

Если вы продолжаете добавлять элементы и, наконец, отображаете список, вы обнаружите, что список не претерпел изменений и все еще пуст. Вопрос, который ударил меня в этом случае, и в этом случае мы передаем адрес корня node, то почему изменения не происходят, поскольку постоянные изменения и список в основной функции не претерпевает никаких изменений. ЗАЧЕМ? ЗАЧЕМ? ЗАЧЕМ?

Тогда я заметил одно: когда я пишу A=NULL, адрес A становится 0. Это означает, что теперь A не указывает на какое-либо местоположение в памяти. Поэтому я удалил строку A=NULL; и внес некоторые изменения в функцию вставки.

некоторые изменения, (ниже insert() функция может добавить только один элемент в пустой список, просто написала эту функцию для целей тестирования)

int insert(struct LinkedList *root, int item){
    root= (struct LinkedList *)malloc(sizeof(struct LinkedList));
    root->data=item;
    root->next=NULL;
    return 0;
}



int main(){
    int m;
    struct LinkedList *A;    
    cout<<"enter the element to be inserted\n";
    cin>>m;
    insert(A,m);
    return 0;
}

указанный выше метод также терпит неудачу, поскольку в функции insert() root хранит тот же адрес, что и A в функции main(), но после строки root= (struct LinkedList *)malloc(sizeof(struct LinkedList)); изменяется адрес, хранящийся в root. Таким образом, теперь root (в функции insert()) и A (в функции main()) хранят разные адреса.

Итак, правильная финальная программа будет

int insert(struct LinkedList *root, int item){
    root->data=item;
    root->next=NULL;
    return 0;
}



int main(){
    int m;
    struct LinkedList *A = (struct LinkedList *)malloc(sizeof(struct LinkedList));
    cout<<"enter the element to be inserted\n";
    cin>>m;
    insert(A,m);
    return 0;
}

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

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

Теперь вот полная программа, а затем объясните понятия.

int insert(struct LinkedList **root,int item){
    if(*root==NULL){
        (*root)=(struct LinkedList *)malloc(sizeof(struct LinkedList));
        (*root)->data=item;
        (*root)->next=NULL;
    }
    else{
        struct LinkedList *temp=(struct LinkedList *)malloc(sizeof(struct LinkedList));
        temp->data=item;
        temp->next=NULL;
        struct LinkedList *p;
        p=*root;
        while(p->next!=NULL){
            p=p->next;
        }
        p->next=temp;
    }
    return 0;
}


int main(){
    int n,m;
    struct LinkedList *A=NULL;
    cout<<"enter the no of elements to be inserted\n";
    cin>>n;
    while(n--){
        cin>>m;
        insert(&A,m);
    }
    display(A);
    return 0;
}

следуют наблюдения,

1. root хранит адрес указателя A (&A), *root сохраняет адрес, хранящийся с помощью указателя A и **root, сохраняет значение по адресу, сохраненному A. На простом языке root=&A, *root= A и **root= *A.

2., если мы пишем *root= 1528, то это означает, что значение по адресу, хранящемуся в root, становится 1528, а поскольку адрес, хранящийся в root, является адресом указателя A (&A) теперь A=1528 (т.е. адрес, хранящийся в A, равен 1528), и это изменение является постоянным.

когда мы меняем значение *root, мы действительно меняем значение по адресу, хранящемуся в root, и поскольку root=&A (адрес указателя A) мы косвенно меняем значение A или адрес, хранящийся в A.

Итак, если A=NULL (список пуст) *root=NULL, мы создаем первый node и сохраняем его адрес в *root, то есть косвенно сохраняем адрес первого node в A. Если список не пуст, все будет таким же, как в предыдущих функциях, используя один указатель, за исключением того, что мы изменили корень на *root, так как то, что было сохранено в корне, теперь хранится в *root.

Ответ 10

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

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

Ответ 11

Подумайте о местоположении памяти для головы, например [HEAD_DATA].

Теперь во втором сценарии вызывающая функция main_head является указателем на это местоположение.

main_head --- > [HEAD_DATA]

В вашем коде он отправил значение указателя main_head в функцию (то есть адрес ячейки памяти head_data) Вы скопировали это в local_head в функции. так что теперь

local_head --- > [HEAD_DATA]

и

main_head --- > [HEAD_DATA]

Оба указывают на одно и то же место, но по существу независимы друг от друга. Поэтому, когда вы пишете local_head = newnode; что вы сделали, это

local_head -/- > [HEAD_DATA]

local_head ----- > [NEWNODE_DATA]

Вы просто заменили адрес памяти предыдущей памяти на новый в локальном указателе. Основная_точка (указатель) по-прежнему указывает на старый [HEAD_DATA]

Ответ 12

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

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

1) Пропустите адрес указателя головы. (Указатель на указатель головы)

2) Верните новый указатель на голову и полагайтесь на вызывающего абонента, чтобы обновить указатель на голову.

Вариант 1) является самым простым, хотя сначала немного запутанным.

Ответ 13

Допустим, я записал ваш домашний адрес на карточке-1. Теперь, если я хочу рассказать ваш домашний адрес кому-то другому, я могу либо скопировать адрес с карты-1 на карточку-2, либо дать карточку-2, либо я могу напрямую передать карту-1. В любом случае человек узнает адрес и сможет связаться с вами. Но когда я напрямую передаю карту-1, адрес можно изменить на карточке-1, но если я дал карточку-2, только адрес на карте-2 можно изменить, но не на карточке-1.

Передача указателя на указатель похожа на предоставление доступа к карточке-1 напрямую. Передача указателя аналогична созданию новой копии адреса.