Creation and Insertion in Doubly Circular Linked List : Algo and Program

by

In this tutorial we will learn how to create doubly circular linked list. We will see the algorithm and program to create doubly circular linked list.

Algorithm to Create Doubly Circular Linked List

  1. Start with an Empty List:
    • Initialize the head pointer to NULL. This will indicate that the list is initially empty.
    • head -> NULL
  2. Create a New Node:
    • When adding a new element, create a new node.
    • Allocate memory for the node and set its data field.
    • Initially, set the next and prev pointers of the node to point to itself. This sets up the circular structure for a single-node list.
  3. Insert the New Node:
    • If the list is empty (i.e., head is NULL), set head to the new node.
    • If the list is not empty, insert the new node at the end (or any other preferred position):
      • Link the new node with the existing nodes by adjusting the next and prev pointers.
      • Ensure the last node’s next points to the new node and the new node’s prev points to the last node.
      • Update the next pointer of the new node to point to head and the prev pointer of head to point to the new node.
  4. Repeat for More Nodes:
    • Repeat the process for each new element you want to add to the list.

Example to Demonstrate the Algorithm

1. Start with an Empty List

  • Initial State: We begin with an empty list. So, head is initialized to NULL.
  • Visualization: head -> NULL

2. Create a New Node

  • Add Element: Suppose we want to add 10 to the list.
  • Action: A new node is created with data = 10. The next and prev pointers of this node point to itself.
  • Node State: [Prev: itself | Data: 10 | Next: itself]

3. Insert the New Node

  • List is Empty (head is NULL): Since the list is empty, head is set to this new node.
  • The list now contains one node, which points to itself, forming a circular structure.

4. Add Another Node

  • Add Element: Let’s add another element, say 20.
  • Create Node: A new node for 20 is created.
  • Node State: [Prev: itself | Data: 20 | Next: itself]
  • Insertion: Since the list is not empty:
    • The next of the new node (20) points to head (10).
    • The prev of head (10) points to the new node (20).
    • The next of the last node (10) points to the new node (20).
    • The prev of the new node (20) points to the last node (10).

Similar we can add any number of nodes in the doubly circular linked list.

C Program to Create and Insert in Doubly Circular Linked List

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

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

typedef struct Node Node;

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

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

// 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");
}

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

Output

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

Explanation of the Program

Struct Node Definition

typedef struct Node {
    int data;
    struct Node *next;
    struct Node *prev;
} 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.