Insertion at Beginning in Doubly Circular Linked List

by

In this tutorial you will learn how to perform node insertion operation in Doubly Circular Linked List. We will also discuss its algorithm and program.

Algorithm to Insert a Node at Beginning in Doubly Circular Linked List

  1. Create a New Node:
    • Allocate memory for a new node. Set its data field to the given value.
    • Initially, set the next and prev pointers of the node to point to itself.
  2. Check if the List is Empty:
    • If the head pointer is NULL, the list is empty.
    • If the list is empty, set the next and prev pointers of the new node to point to itself and update head to the new node.
  3. Insert the Node at the Beginning:
    • If the list is not empty:
      • Set the next pointer of the new node to head.
      • Set the prev pointer of head to the new node.
      • Find the last node of the list (the node whose next points to head).
      • Set the next pointer of the last node to the new node.
      • Set the prev pointer of the new node to the last node.
      • Update head to the new node.
  4. The Node is Inserted:
    • The new node is now the first node in the list, and the list maintains its circular structure.

Step By Step Explanation

Here we will se how insertion at the beginning works in Doubly Circular Linked List.

Step 1: Start with an Empty List

Initial State:

head -> NULL

Step 2: Create a New Node with Value 10

  • Node Creation:
    • A new node with data 10 is created.
  • Initial Pointers:
    • The next and prev pointers of this new node point to itself.
[10] <-> [10]  (A self-referencing single-node circular list)

Step 3: Insert the New Node (10) at the Beginning

  • List is Empty (head is NULL):
    • Insert the node and update head to this new node.
head -> [10] <-> [10] (Points to itself)

Step 4: Add Another Node with Value 20

  • Node Creation:
    • A new node with data 20 is created.
  • Initial Pointers:
    • The next and prev of this node initially point to itself.
[20] <-> [20]  (A self-referencing node before insertion)

Step 5: Insert the New Node (20) at the Beginning

  • Adjust Pointers:
    • next of new node (20) points to head (10).
    • prev of head (10) now points to new node (20).
    • The next of the last node (which is 10 at this moment) points to new node (20).
    • prev of new node (20) points to the last node (10).
  • Update Head:
    • head is updated to point to the new node (20).
head -> [20] <--> [10]
        ^------------|

C Program to Insert a Node at the Beginning of a Doubly Circular Linked List

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

struct Node {
    int data;
    struct Node *next;
    struct Node *prev;
}; 

typedef struct Node Node;

// Create a new node
Node *createNode(int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = newNode;
    newNode->prev = newNode;
    return newNode;
}

// Insert at the Beginning of the Doubly Circular Linked List
void insertAtBeginning(Node** head, int data) {
    Node *newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node *last = (*head)->prev;
        newNode->next = *head;
        newNode->prev = last;
        last->next = newNode;
        (*head)->prev = newNode;
        *head = newNode;
    }
}

// Print the Doubly Circular Linked List
void printDoublyCircularLinkedList(Node *head) {
    if (head == NULL) {
        printf("The list is empty.\n");
        return;
    }
    Node *temp = head;
    printf("Doubly Circular Linked List After Insertion at Beginning: \n");
    do {
        printf("%d ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("\n");
}

int main() {
    Node *head = NULL;
    insertAtBeginning(&head, 10);
    insertAtBeginning(&head, 20);
    insertAtBeginning(&head, 30);
    insertAtBeginning(&head, 40);
    insertAtBeginning(&head, 50);
    printDoublyCircularLinkedList(head);
    return 0;
}

Output

Doubly Circular Linked List After Insertion at Beginning: 
50 40 30 20 10

Explanation of the Program

Struct Node Definition:

struct Node {
    int data;
    struct Node *next;
    struct Node *prev;
}; 
typedef struct Node Node;

A struct Node is defined with data to store the value, and next and prev pointers to point to the next and previous nodes in the list, respectively.

Function createNode:

// Create a new node
Node *createNode(int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = newNode;
    newNode->prev = newNode;
    return newNode;
}

This function creates a new node with the given data. It allocates memory for a Node, sets its data, and initializes next and prev to point to the node itself. This is useful for handling a single-node circular list.

Function insertAtBeginning:

// Insert at the Beginning of the Doubly Circular Linked List
void insertAtBeginning(Node** head, int data) {
    Node *newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node *last = (*head)->prev;
        newNode->next = *head;
        newNode->prev = last;
        last->next = newNode;
        (*head)->prev = newNode;
        *head = newNode;
    }
}

This function inserts a new node at the beginning of the doubly circular linked list.

If the list is empty (*head == NULL), the new node becomes the head of the list.

If the list is not empty, it adjusts the pointers to insert the new node before the current head. It sets newNode->next to the current head and newNode->prev to the last node. It also adjusts the previous head and last node to point to the new node. Finally, it updates head to point to the new node.

Function printDoublyCircularLinkedList:

// Print the Doubly Circular Linked List
void printDoublyCircularLinkedList(Node *head) {
    if (head == NULL) {
        printf("The list is empty.\n");
        return;
    }
    Node *temp = head;
    printf("Doubly Circular Linked List After Insertion at Beginning: \n");
    do {
        printf("%d ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("\n");
}

This function prints the elements of the doubly circular linked list starting from the head.

It traverses the list from head, printing each node’s data, until it completes a full cycle and returns to the head, indicating one full traversal of the circular list.

main Function:

int main() {
    Node *head = NULL;
    insertAtBeginning(&head, 10);
    insertAtBeginning(&head, 20);
    insertAtBeginning(&head, 30);
    insertAtBeginning(&head, 40);
    insertAtBeginning(&head, 50);
    printDoublyCircularLinkedList(head);
    return 0;
}

Initializes a head pointer to NULL, indicating an empty list.

Calls insertAtBeginning five times to insert numbers 10, 20, 30, 40 and 50 at the beginning of the list.

Finally, calls printDoublyCircularLinkedList to display the list.

Hope this post helped you to understand how to insert node at beginning in Doubly Circular Linked List.