2

I am trying to add 'n' number of nodes to the beginning of double circular linked list here is the function for adding the node:

//the **head is assigned the address of the original head pointer which is being passed from the main function.

void insert(struct node**head,int n){
 while(n-- >0){
    int num;
    //to input the data for the linked list
    scanf("%d",&num);
    struct node* newnode=(struct node*)malloc(sizeof(struct node));
    newnode->data=num;

    if(*head==NULL){
        newnode->next=newnode;
        newnode->prev=newnode;

        *head=newnode;
    }
    else{

        newnode->next=*head;
        newnode->prev=(*head)->prev;

        //to make the previously first node point to the new first node
        newnode->next->prev=newnode;
        //to make the last node point to the new first node
        (*head)->prev->next=newnode;
        *head=newnode;

    }
 }
}

when I execute it, it is not showing any ouput but when I change 

//to make the last node point to the new first node
            (*head)->prev->next=newnode;

this line to 

newnode->prev->next=newnode;

the code is running. I am not able to understand what is the difference between the two statement.

Humble
  • 39
  • 9
  • 2
    @virolino `*head` makes perfect sense as it means the updated value of `head` is passed to the calling function – Chris Turner Feb 27 '20 at 12:40
  • @ChrisTurner: just brainstorming - `*head` makes sense only if `head` is defined something like `struct node** head` - which is overkill. – virolino Feb 27 '20 at 12:46
  • 1
    @virolino no guess work required - passing in a pointer to something allows you to update it since C only has passing by value and is one of two ways to write this kind of function – Chris Turner Feb 27 '20 at 12:58
  • Post the declaration of the `struct` all this is based on. ( Really should be a [mcve] to allow for more understanding. ) – ryyker Feb 27 '20 at 12:58
  • This does not address the core issue, but because this is `C` (and not `C++`) the statement: `struct node* newnode=(struct node*)malloc(sizeof(struct node));` would be properly written as `struct node* newnode=malloc(sizeof(* newnode));`. i.e. [it is not necessary or optimal to cast the return of malloc() in C](https://stackoverflow.com/a/605858/645128). – ryyker Feb 27 '20 at 13:03
  • What is the "beginning" of a circular list? IMO, for a circular list, every node should be considered equal, and you can at any time swap your head pointer with any node in the list. There is no "beginning". (This is just a nit on the title, really.) – William Pursell Feb 27 '20 at 13:45

3 Answers3

1
(*head)->prev->next=newnode;
...
newnode->prev->next=newnode;

I am not able to understand what is the difference between the two statement.

newnode->prev has been correctly set to the node before the head. In contrast, (*head)->prev at this time has already been altered by newnode->next->prev=newnode, since newnode->next=*head. Hence (*head)->prev no longer points to the node before the head, but to the new node. That's the difference.

Armali
  • 18,255
  • 14
  • 57
  • 171
0

The next code assumes that head is defines as: struct node* head;. I just removed some extra dereferencing operators(*).

It is not directly testable, as a minimally reproducible example was not provided.

 while(n-- >0){
    int num;
    //to input the data for the linked list
    scanf("%d",&num);
    struct node* newnode=(struct node*)malloc(sizeof(struct node));
    newnode->data=num;

    if(head==NULL){              /*   was: if(*head==NULL){   */
        newnode->next=newnode;
        newnode->prev=newnode;

        head=newnode;{              /*   was: *head=newnode;{   */
    }
    else{

        newnode->next=head;              /*   was: newnode->next=*head;   */
        newnode->prev=(*head)->prev;

        //to make the previously first node point to the new first node
        newnode->next->prev=newnode;
        //to make the last node point to the new first node
        (*head)->prev->next=newnode;
        head=newnode;              /*   was: *head=newnode;   */
    }
 }
virolino
  • 2,073
  • 5
  • 21
  • I have edited my question as it was not clear what *head was about. – Humble Feb 27 '20 at 13:27
  • Your original code is wrong either way. These two lines `newnode->next=*head;newnode->prev=(*head)->prev;` cannot lead to the desired result at the same time. – virolino Feb 27 '20 at 13:29
  • could you please review it again and help me understand my problem. – Humble Feb 27 '20 at 13:30
  • can you please elaborate ? – Humble Feb 27 '20 at 13:30
  • My hunch is that you need to understand pointers and struct's better (and pointers to struct's), before undergoing handling double-linked circular lists. I have this hunch because to ask me to elaborate. With a good understanding of these (complicated) features, no elaboration should be necessary. So my best advice is: go back to the earlier lessons in your C manual and learn these topics better. Maybe use other manuals too. When you will understand by yourself this answer without elaboration, you can say that you actually (start to) understand things. – virolino Feb 27 '20 at 13:34
0

The original code goes wrong when the list contains a single node before the new node is added. Let's call that node A for reference. Before inserting the new node, the situation is as follows:

/* List with single node. */
(*head) = &A;
A.next = &A;
A.prev = &A;

Let's call the node pointed to by newnode B:

newnode = &B;

The code to prepend newnode is currently as follows (with added comments //>):

    newnode->next=*head;         //> B.next=&A;
    newnode->prev=(*head)->prev; //> B.prev=&A;

    //to make the previously first node point to the new first node
    newnode->next->prev=newnode; //> A.prev=&B;
    //to make the last node point to the new first node
    (*head)->prev->next=newnode; //> B.next=&B; !!! want A.next = &B;
    *head=newnode;

The situation after the above code sequence:

(*head) = &B;
B.next = &B; // !!! want B.next = &A;
B.prev = &A;
A.next = &A; // !!! want A.next = &B;
A.prev = &B;

The list has been broken because the wrong link pointer was changed. It can be fixed by using a temporary variable lastnode set to the old value of (*head)->prev. The updated code is as follows:

    struct node *lastnode;
    lastnode=(*head)->prev;      //> lastnode=&A;
    newnode->next=*head;         //> B.next=&A;
    newnode->prev=lastnode;      //> B.prev=&A;

    //to make the previously first node point to the new first node
    newnode->next->prev=newnode; //> A.prev=&B;
    //to make the last node point to the new first node
    lastnode->next=newnode;      //> A.next=&B;
    *head=newnode;

The situation after the updated code sequence:

(*head) = &B;
B.next = &A;
B.prev = &A;
A.next = &B;
A.prev = &B;
Ian Abbott
  • 15,083
  • 19
  • 33