C program to create and traverse Doubly Linked List

Write a C program to implement Doubly linked list data structure. Write a C program to create a doubly linked list and display all nodes of the created list. How to create and display a doubly linked list in C. Algorithm to create and traverse doubly linked list.

Required knowledge

Basic C programming, Functions, Dynamic memory allocation, Doubly linked list

Algorithm to create a Doubly linked list

Algorithm to create Doubly Linked list
Begin:
    alloc (head)
    If (head == NULL) then
        write ('Unable to allocate memory')
    End if
    Else then 
        read (data)
        head.data ← data;
        head.prev ← NULL;
        head.next ← NULL;
        last ← head;
        write ('List created successfully')
    End else
End

Algorithm to traverse or display Doubly linked list from beginning

Algorithm to traverse Doubly Linked list from beginning
%% Input :  head {Pointer to the first node of the list}
Begin:
    If (head == NULL) then
        write ('List is empty')
    End if
    Else then
        temp ← head;
        While (temp != NULL) do
            write ('Data = ', temp.data)
            temp ← temp.next;
        End while
    End else
End

Algorithm to traverse or display Doubly linked list from end

Algorithm to traverse Doubly Linked list from end
%% Input :  last {Pointer to the last node of the list}
Begin:
    If (last == NULL) then
        write ('List is empty')
    End if
    Else then
        temp ← last;
        While (temp != NULL) do
            write ('Data = ', temp.data)
            temp ← temp.prev;
        End while
    End else
End

Steps to create Doubly linked list

1. Create a head node and assign some data to its data field.
2. Make sure that the previous and next address field of the head node must point to NULL.
3. Make the head node as last node.

   

1. Create a new node and assign some data to its data field.

   

2. Make sure that the next address field of new node must point to NULL.

   

3. Link the new node previous address field with lastNode.

1. Link the lastNode next address field with newNode.
   
2. Move the lastNode to newNode i.e. last node will now point to new node.

   

3. Repeat Steps 4-8 if you want to add more nodes to the list.

Program to create and traverse doubly linked list

/**
 * C program to create and display Doubly linked list
 */

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

/* 
 * Basic structure of Node
 */
struct node {
    int data;
    struct node * prev;
    struct node * next;
}*head, *last;


/*
 * Function used in this program 
 */
void createList(int n);
void displayListFromFirst();
void displayListFromEnd();


int main()
{
    int n, choice;

    head = NULL;
    last = NULL;
    
    printf("Enter the number of nodes you want to create: ");
    scanf("%d", &n);

    createList(n); // Create list of n nodes

    printf("\nPress 1 to display list from First");
    printf("\nPress 2 to display list from End : ");
    scanf("%d", &choice);

    if(choice==1)
    {
        displayListFromFirst();
    }
    else if(choice == 2)
    {
        displayListFromEnd();
    }

    return 0;
}


/**
 * Create a doubly linked list of n nodes.
 * @n Number of nodes to be created
 */
void createList(int n)
{
    int i, data;
    struct node *newNode;

    if(n >= 1)
    {
        head = (struct node *)malloc(sizeof(struct node));

        if(head != NULL)
        {
            printf("Enter data of 1 node: ");
            scanf("%d", &data);

            head->data = data;
            head->prev = NULL;
            head->next = NULL;

            last = head;

            /*
             * Create rest of the n-1 nodes
             */
            for(i=2; i<=n; i++)
            {
                newNode = (struct node *)malloc(sizeof(struct node));

                if(newNode != NULL)
                {
                    printf("Enter data of %d node: ", i);
                    scanf("%d", &data);

                    newNode->data = data;
                    newNode->prev = last; // Link new node with the previous node
                    newNode->next = NULL;

                    last->next = newNode; // Link previous node with the new node
                    last = newNode;          // Make new node as last/previous node
                }
                else
                {
                    printf("Unable to allocate memory.");
                    break;
                }
            }

            printf("\nDOUBLY LINKED LIST CREATED SUCCESSFULLY\n");
        }
        else
        {
            printf("Unable to allocate memory");
        }
    }
}


/**
 * Displays the content of the list from beginning to end
 */
void displayListFromFirst()
{
    struct node * temp;
    int n = 1;

    if(head == NULL)
    {
        printf("List is empty.");
    }
    else
    {
        temp = head;
        printf("\n\nDATA IN THE LIST:\n");

        while(temp != NULL)
        {
            printf("DATA of %d node = %d\n", n, temp->data);

            n++;
            
            /* Move the current pointer to next node */
            temp = temp->next;
        }
    }
}


/**
 * Display the content of the list from last to first
 */
void displayListFromEnd()
{
    struct node * temp;
    int n = 0;

    if(last == NULL)
    {
        printf("List is empty.");
    }
    else
    {
        temp = last;
        printf("\n\nDATA IN THE LIST:\n");

        while(temp != NULL)
        {
            printf("DATA of last-%d node = %d\n", n, temp->data);

            n++;
            
            /* Move the current pointer to previous node */
            temp = temp->prev; 
        }
    }
}

Enter the number of nodes you want to create: 5
Enter data of 1 node: 10
Enter data of 2 node: 20
Enter data of 3 node: 30
Enter data of 4 node: 40
Enter data of 5 node: 50

DOUBLY LINKED LIST CREATED SUCCESSFULLY

Press 1 to display list from First
Press 2 to display list from End : 1

DATA IN THE LIST:
DATA of 1 node = 10
DATA of 2 node = 20
DATA of 3 node = 30
DATA of 4 node = 40
DATA of 5 node = 50