CODEWITHSUNDEEP
cpointerslinked-list
user8657231
user8657231

Reputation: 67

Insertion at the beginning in circular linked list

I have been recently working on circular linked list and the way the most of the people write code is as given below:

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

/* structure for a node */
struct Node
{
    int data;
    struct Node *next;
};

/* Function to insert a node at the begining of a Circular
   linked list */
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 linked list is not NULL then set the next of last node */
    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;
}

/* Function to print nodes in a given Circular linked list */
void printList(struct Node *head)
{
    struct Node *temp = head;
    if (head != NULL)
    {
        do
        {
            printf("%d ", temp->data);
            temp = temp->next;
        }
        while (temp != head);
    }
}

/* Driver program to test above functions */
int main()
{
    /* Initialize lists as empty */
    struct Node *head = NULL;

    /* Created linked list will be 11->2->56->12 */
    push(&head, 12);
    push(&head, 56);
    push(&head, 2);
    push(&head, 11);

    printf("Contents of Circular Linked List\n ");
    printList(head);

    return 0;
}

However, there is one thing is never understand while inserting at the beginning of the circular linked list. If our last node always points to the first node which also is same as saying that the last node *next pointer has the same address as the the *first pointer has, then why for inserting the items after first node, we have to travel the whole list and update the *next pointer of the last node to point the newly added node at the beginning. Instead of while loop why can't we simply do like this:

Node *newadded newadded->next = first->next first = newadded

Because *first pointer has the address of the first node so if we update the *first pointer then the last pointer which already was pointing to the first pointer should also update itself. Why to travel the whole list?

Upvotes: 2

Views: 1437

Answers (1)

jxh
jxh

Reputation: 70392

Since the list is circular, the last element of the list needs to point to the first element of the list. When inserting a new element into the beginning of the list, the first element of the list has changed to be a different element. To maintain circularity, you must find the last element and make it point to the new first element.

One way to make the operation more efficient is to maintain the tail of the circular linked list, rather than the head. Then insertion to the tail and to the head can both be done in constant time.

Demo

Upvotes: 4

Related Questions