CODEWITHSUNDEEP
ccircular-list
Humble
Humble

Reputation: 39

adding node to the beginning of double circular linked list in c

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.

Upvotes: 2

Views: 121

Answers (3)

Ian Abbott
Ian Abbott

Reputation: 17403

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;

Upvotes: 0

Armali
Armali

Reputation: 19375

(*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.

Upvotes: 1

virolino
virolino

Reputation: 2201

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;   */
    }
 }

Upvotes: 0

Related Questions