Insertion at End in Doubly Circular Linked List

by

In this tutorial we will learn how to insert an element at the end of doubly circular linked list. We will see algorithm and program to perform insertion operation in doubly circular linked list at end.

Algorithm to Insert a Node at End 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 (this handles the case where the node being added is the first node).
  2. Check if the List is Empty:
    • If the head pointer is NULL, the list is empty.
    • If the list is empty, set head to the new node, making it both the first and last node. The next and prev of this node will point to itself, maintaining the circular structure.
  3. Insert the Node at the End:
    • If the list is not empty:
      • Find the last node (the node whose next points to head).
      • Set the next pointer of the new node to head.
      • Set the prev pointer of head to the new node.
      • Set the next pointer of the last node to the new node.
      • Set the prev pointer of the new node to the last node.
  4. The Node is Inserted:
    • The new node is now the last node in the list, and the list still maintains its circular structure.

Example: Inserting Nodes in a Doubly Circular Linked List at end

Start with an Empty List: Initially, our list is empty. So, head is NULL.

Step 1: Create a New Node (e.g., with value 10)

  • Action: Allocate memory for a new node. Set its data field to 10.
  • Initial Pointers: Set both the next and prev pointers of the node to point to itself.
[10] <-> [10]  (A self-referencing single-node circular list)

Step 2: Check if the List is Empty

  • List is Empty: Since head is NULL, the list is empty.

Step 3: Insert the Node (10) at the End

  • List is Empty Case:
    • Action: Set head to the new node.
head -> [10] <-> [10] (Points to itself)

Step 4: Add Another Node (e.g., with value 20)

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

Step 5: Insert the Node (20) at the End

  • List is Not Empty:
    • Find the Last Node: The current last node is 10 (as it’s the only node and head points to it).
    • Adjust Pointers:
      • Set the next pointer of new node (20) to head (10).
      • Set the prev pointer of head (10) to new node (20).
      • The next pointer of the last node (10) is set to new node (20).
      • Set the prev pointer of new node (20) to last node (10).
    • Update Head: head still points to the first node (10).
  • After Adding Node 20:
    • The list has two nodes 10 and 20, where 20 is added at the end.
    • The list maintains its circular nature.
head -> [10] <--> [20]
        ^------------|

This example demonstrates the process of adding nodes to the end of a doubly circular linked list, clearly showing how each node is linked to maintain the circular and doubly linked structure.

Program in C to Insert a Node at End of 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 End of the Doubly Circular Linked List
void insertionAtEnd(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;
    }
}

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

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

Output

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

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, containing an integer data and two pointers next and prev, pointing to the next and previous nodes in the list, respectively.

Function createNode:

// reate 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 new Node, sets its data field, and initializes both next and prev pointers to point to the node itself. This self-referencing setup is useful for handling a single-node circular list.

Function insertAtEnd:

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

This function inserts a new node at the end 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 finds the last node (the node before head) and inserts the new node between the last node and head, updating the next and prev pointers appropriately to maintain the circular nature of the list.

Function printDoublyCircularLinkedList:

// Print the Doubly Circular Linked List
void printDoublyCircularLinkedList(Node *head) {
    if (head == NULL) {
        printf("Doubly Circular Linked List is empty.\n");
        return;
    }
    Node* temp = head;
    printf("Doubly Circular Linked List After Insertion: \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 head.

It traverses the list starting from head and keeps printing the data of each node until it reaches the head again, indicating one full cycle through the circular list.

main Function:

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

A head pointer is initialized to NULL, indicating an empty list.

The insertAtEnd function is called six times to insert the numbers 10, 20, 30, 40, 50, and 60 at the end of the list.

Finally, printDoublyCircularLinkedList is called to display the list.

Hope this tutorial helped you to understand the concept of insertion in doubly circular linked list at end.