how to insert node in Circular Linked list in C

Question

Can someone explain the 'while part' of the code?- in the main() head is declared as struct node pointer initialized with value NULL. and a node is inserted by calling function = push(&head,12)

void push(struct Node **head_ref, int data)
{ 
    struct Node *ptr1 = (struct Node *)malloc(sizeof(struct Node)); 
    struct Node *temp = *head_ref; 
    ptr1->data = data; 
    ptr1->next = *head_ref; 
    if (*head_ref != NULL) 
    { 
        while (temp->next != *head_ref)
            temp = temp->next; 
        temp->next = ptr1; 
    }
    else
        ptr1->next = ptr1; /*For the first node */

    *head_ref = ptr1;
}

In the answer below I attempt to address your question, but if it is insufficient, please flag me (@ryyker) in a comment with any questions :)) — ryyker
– ryyker, Commented Sep 17, 2020 at 16:40
The lack of a pointer to the last node in the circular list (provided by the ->prev pointer in a doubly-linked list) requires that after adding the new 1st node, you have to traverse the entire list to find the last node and update the ->next pointer so it points to the new 1st node. (lesson: always keep a tail pointer or make the list a doubly-linked list to preserve O(1) insertions) — David C. Rankin
– David C. Rankin, Commented Sep 17, 2020 at 21:11

ryyker · Accepted Answer · 2020-09-17 20:00:30Z

Can someone explain the 'while part' of the code?

The while() part (also described in section 2.) below.) is to look for the node which points to the current head node so that the new node can be inserted just before it. While in the loop, notice that as nodes are found, and they are not yet the head node, they are incremented so as to prepare for the insertion when head node is finally located.

The last expression in the routine:

*head_ref = ptr1;

Is to handle the case described by section 1.) in the general steps below.

General approach for the following initial conditions:

Linked List is empty:
a) since new_node is the only node in CLL, make a self loop.
new_node->next = new_node;
b) change the head pointer to point to new node. *head_ref = new_node;
New node is to be inserted just before the head node:
(a) Find out the last node using a loop. while(current->next != *head_ref) current = current->next; (b) Change the next of last node. current->next = new_node; (c) Change next of new node to point to head. new_node->next = *head_ref; (d) change the head pointer to point to new node. *head_ref = new_node;
New node is to be inserted somewhere after the head: (a) Locate the node after which new node is to be inserted. while ( current->next!= *head_ref && current->next->data data) { current = current->next; } (b) Make next of new_node as next of the located pointer new_node->next = current->next; (c) Change the next of the located pointer current->next = new_node;

Details and implementation for doing this are shown in this example code

Collectives™ on Stack Overflow

how to insert node in Circular Linked list in C

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related