Doubly Linked List Example Using C Program

This example shows how to create, insert, append, remove nodes in doubly linked list using C program. We will use here Structure, which is a composite data type, in which we can define all data types under the same name or object. Size of the Structure is determined by computing the size of all data types, plus any internal padding. The key word struct is used to declare the Structure. In doubly linked list there are two links – one is left and another is right link.

The complete source code for doubly linked list is given below

/* 
 * File:   DoublyLinkedList.c
 * Author: https://www.roytuts.com
 */

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

typedef struct node {
    struct node *left;
    int data;
    struct node *right;
} node;

/*
 *Create a new node
 */
node* createSingleNode(int data) {
    //allocate the memory for new node
    node* newNode = (node*) malloc(sizeof (node));

    //error allocating memory to new node
    if (newNode == NULL) {
        printf("Error creating new node. So exiting...\n");
        exit(0);
    }

    //put the data
    newNode->data = data;

    //point to the left and right node
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

/*
 *Append new node at the end of the list
 */
node* appendNode(node* head, int data) {
    //if root node not found
    if (head == NULL) {
        return NULL;
    }

    //point to the first node
    node* current = head;

    //go to the last node
    while (current->right != NULL) {
        current = current->right;
    }

    //create the new node
    node* newNode = createSingleNode(data);

    //point current node to the new node
    current->right = newNode;
    newNode->left = current;
    newNode->right = NULL;

    return head;
}

/*
 * Create multiple nodes
 */
node* createMultipleNodes() {
    int i, noOfNodes, data;

    printf("Enter no. of nodes to be created: ");
    scanf("%d", &noOfNodes);

    printf("Enter data for node: ");
    scanf("%d", &data);

    node* head = createSingleNode(data);

    for (i = 1; i < noOfNodes; i++) {
        printf("Enter data for node: ");
        scanf("%d", &data);
        head = appendNode(head, data);
    }
    return head;
}

/*
 * Insert new node into the existing linked list
 */
node* insertNode(node* head, int position, node* newNode) {
    int j;
    node *current, *temp;

    //if root node not found
    if (head == NULL) {
        return NULL;
    }

    //if  new node not found
    if (newNode == NULL) {
        return head;
    }

    //if new node to be inserted at first position
    if (position == 0) {
        newNode->right = head;
        head->left = newNode;
        head = newNode;
        return head;
    }

    //point to the first node
    current = head;

    for (j = 1; j < position && current != NULL; j++) {
        current = current->right;
    }

    if (current != NULL) {
        temp = current;
        newNode->right = temp->right;
        newNode->left = temp->left;
        temp->right = newNode;
        return head;
    }

    return NULL;
}

/*
 *Remove node at specified position
 */
node* removeNode(node* head, int position) {
    int j;
    node *current, *temp;

    //if root node not found
    if (head == NULL) {
        return NULL;
    }

    current = head;

    if (position == 0) {
        head = head->right;
        free(current);
        return head;
    }

    //make next pointer of temp node to NULL
    temp = current->right;

    for (j = 1; j < position && temp != NULL; j++) {
        current = temp;
        temp = temp->right;
    }

    if (current != NULL) {
        current->right = temp->right;
        temp->left = NULL;
        temp->right = NULL;
        free(temp);
        return head;
    }

    return NULL;
}

/*
 * Concatenate two LinkedLists
 */
node* concatenate(node* p, node* q) {
    node* r;
    if (p = NULL) {
        p = q;
    }

    r = p;

    while (r->right != NULL) {
        r = r->right;
    }

    q->left = r;
    r->right = q;

    return p;
}

/*
 * Reverse LinkedList
 */
node* reverse(node* head) {
    if (head == NULL || head->right == NULL) {
        return head;
    }
    node *p;
    p = head;
    while (p->right != NULL) {
        node *temp = p->right;
        p->right = p->left;
        p->left = temp;
        p = temp;
    }
    p->right = p->left;
    p->left = NULL;
    return p;
}

/*
 * Print LinkedList
 */
void printLinkedList(node* head) {
    //if root node not found
    if (head == NULL) {
        return;
    }
    node* current = head;

    printf("\n");

    //traverse and print data
    while (current != NULL) {
        printf("%d", current->data);
        current = current->right;
        if (current != NULL) {
            printf("<->");
        }
    }

    printf("\n");

    head = current;
}

void main() {
    //create single node
    node* head = createSingleNode(5);
    //append node one after another
    appendNode(head, 10);
    appendNode(head, 15);
    appendNode(head, 20);
    appendNode(head, 25);
    printf("\nLinkedList with created nodes");
    printLinkedList(head);

    //create multiple nodes
    head = createMultipleNodes();
    //print nodes
    printf("\nLinkedList with created nodes");
    printLinkedList(head);

    //create single node
    node* newNode = createSingleNode(25);
    //insert new node at position 2
    head = insertNode(head, 2, newNode);
    //print nodes
    printf("\nLinkedList after inserting new node at position 2");
    printLinkedList(head);

    //remove node from position 2
    head = removeNode(head, 2);
    //print nodes
    printf("\nLinkedList after removing node from position 2");
    printLinkedList(head);

    //reverse LinkedList
    head = reverse(head);
    //print nodes
    printf("\nLinkedList after reversing");
    printLinkedList(head);
}

When you run the above program you will see below output

LinkedList with created nodes
5<->10<->15<->20<->25
Enter no. of nodes to be created: 5
Enter data for node: 1
Enter data for node: 2
Enter data for node: 3
Enter data for node: 4
Enter data for node: 5

LinkedList with created nodes
1<->2<->3<->4<->5

LinkedList after inserting new node at position 2
1<->2<->25<->3<->4<->5

LinkedList after removing node from position 2
1<->2<->3<->4<->5

LinkedList after reversing
5<->4<->3<->2<->1

Thanks for reading.

Soumitra Roy Sarkar

I am a professional Web developer, Enterprise Application developer, Software Engineer and Blogger. Connect me on JEE Tutorials Twitter Facebook  Google Plus Linkedin Or Email Me

Leave a Reply

Your email address will not be published. Required fields are marked *