C program to Implement Doubly Linked List

Doubly Linked List

In a single linked list, every node has link to its next node in the sequence. So, we can traverse from one node to other node only in one direction and we can not traverse back. We can solve this kind of problem by using double linked list. Double linked list can be defined as follows...

In double linked list, every node has link to its previous node and next node. So, we can traverse forward by using next field and can traverse backward by using previous field. Every node in a double linked list contains three fields and they are shown in the following figure...

Here is source code of the C Program to Implement Doubly Linked List using Dynamic Memory Allocation. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

#include<stdio.h>

struct linked_list_node{
    int num;
    struct linked_list_node *prev;
    struct linked_list_node *next;
};

typedef struct linked_list_node snode;

snode *first = NULL;
snode *last = NULL;

void insertNode(int value);
void insertAtFirst(int value);
void deleteFirst();
void deleteLast();
snode *createNode(int value);
void displayFromBeg();
void displayFromEnd();

void main()
{
    int choice, nValue;
    char ch='y';

    while (ch == 'y')
    {
        printf("\n------------------------------\n");
        printf("\tDoubly Linked List\n");
        printf("------------------------------\n");

        printf("\n1. Insert a node at last\n");
        printf("2. Insert a node at first\n");
        printf("3. Delete First Node\n");
        printf("4. Delete Last Node\n");
        printf("5. Display contents of list from beginning\n");
        printf("6. Display contents of list from end\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);

        switch(choice)
        {
            case 1:
                    printf("\nInserting a new node at last.....\n");
                    printf("Enter the value of node: ");
                    scanf("%d", &nValue);
                    insertNode(nValue);
                    break;
            case 2:
                    printf("\nInserting a node at first.....\n");
                    printf("Enter the value of node: ");
                    scanf("%d", &nValue);
                    insertAtFirst(nValue);
                    break;
            case 3:
                    printf("\nDeleteing first node.....\n");
                    deleteFirst();
                    break;
            case 4:
                    printf("\nDeleteing last node.....\n");
                    deleteLast();
                    break;
            case 5:
                    printf("\nContents of linked list from beginning are as follows\n");
                    displayFromBeg();
                    break;
            case 6:
                    printf("\nContents of linked list from end are as follows\n");
                    displayFromEnd();
                    break;
            default:
                    printf("\nInvalid choice!!!\n");
        }

        printf("\nDo you want to continue(y/n)?" );
        scanf(" %c", &ch);
    }
}

snode *createNode(int value)
{
    snode *newNode;

    newNode = (snode *)malloc(sizeof(snode));
    newNode->num = value;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

void insertNode(int value)
{
    snode *newNode;
    newNode = createNode(value);

    if (first == last && first == NULL)
    {
        first = last = newNode;
    }
    else
    {
        last->next = newNode;
        newNode->prev = last;
        last = newNode;
    }
}

void insertAtFirst(int value)
{
    snode *newNode;
    newNode = createNode(value);

    newNode->next = first;
    first->prev = newNode;
    first = newNode;
}

void deleteFirst()
{
    if (first == NULL)
    {
        printf("List is empty!!!\n");
    }
    else if (first == last)
    {
        first = last = NULL;
        printf("Node successfully deleted!!!\n");
    }
    else
    {
        first = first->next;
        printf("Node successfully deleted!!!\n");
    }
}

void deleteLast()
{
    snode *temp;
    if (first == NULL)
    {
        printf("List is empty!!!\n");
    }
    else if (first == last)
    {
        first = last = NULL;
        printf("Node successfully deleted!!!\n");
    }
    else
    {
        last = last->prev;
        printf("Node successfully deleted!!!\n");
    }
}

void displayFromBeg()
{
    snode *temp = first;

    if (first == NULL)
    {
        printf("List is empty!!!\n");
        return;
    }

    while (temp != last)
    {
        printf("%d-->", temp->num);
        temp = temp->next;
    }
    printf("%d", last->num);
}

void displayFromEnd()
{
    snode *temp = last;

    if (first == NULL)
    {
        printf("List is empty!!!\n");
        return;
    }

    while (temp != first)
    {
        printf("%d-->", temp->num);
        temp = temp->prev;
    }
    printf("%d", first->num);
}

Output:

----------------------------------------------------------
   Doubly Linked List
----------------------------------------------------------

1. Insert a node at last
2. Insert a node at first
3. Delete First Node
4. Delete Last Node
5. Display contents of list from beginning
6. Display contents of list from end
Enter your choice: 1

Inserting a new node at last.....
Enter the value of node: 5

Do you want to continue(y/n)?y

-----------------------------------------------------------
   Doubly Linked List
-----------------------------------------------------------

1. Insert a node at last
2. Insert a node at first
3. Delete First Node
4. Delete Last Node
5. Display contents of list from beginning
6. Display contents of list from end
Enter your choice: 2

Inserting a node at first.....
Enter the value of node: 4

Do you want to continue(y/n)?y

-----------------------------------------------------------
   Doubly Linked List
-----------------------------------------------------------

1. Insert a node at last
2. Insert a node at first
3. Delete First Node
4. Delete Last Node
5. Display contents of list from beginning
6. Display contents of list from end
Enter your choice: 1

Inserting a new node at last.....
Enter the value of node: 6

Do you want to continue(y/n)?y

-----------------------------------------------------------
   Doubly Linked List
-----------------------------------------------------------

1. Insert a node at last
2. Insert a node at first
3. Delete First Node
4. Delete Last Node
5. Display contents of list from beginning
6. Display contents of list from end
Enter your choice: 1

Inserting a new node at last.....
Enter the value of node: 7

Do you want to continue(y/n)?y

-----------------------------------------------------------
   Doubly Linked List
-----------------------------------------------------------

1. Insert a node at last
2. Insert a node at first
3. Delete First Node
4. Delete Last Node
5. Display contents of list from beginning
6. Display contents of list from end
Enter your choice: 5

Contents of linked list from beginning are as follows
4-->5-->6-->7
Do you want to continue(y/n)?y

-----------------------------------------------------------
   Doubly Linked List
-----------------------------------------------------------

1. Insert a node at last
2. Insert a node at first
3. Delete First Node
4. Delete Last Node
5. Display contents of list from beginning
6. Display contents of list from end
Enter your choice: 6

Contents of linked list from end are as follows
7-->6-->5-->4
Do you want to continue(y/n)?y

-----------------------------------------------------------
   Doubly Linked List
-----------------------------------------------------------

1. Insert a node at last
2. Insert a node at first
3. Delete First Node
4. Delete Last Node
5. Display contents of list from beginning
6. Display contents of list from end
Enter your choice: 3

Deleteing first node.....
Node successfully deleted!!!

Do you want to continue(y/n)?y

-----------------------------------------------------------
   Doubly Linked List
-----------------------------------------------------------

1. Insert a node at last
2. Insert a node at first
3. Delete First Node
4. Delete Last Node
5. Display contents of list from beginning
6. Display contents of list from end
Enter your choice: 5

Contents of linked list from beginning are as follows
5-->6-->7
Do you want to continue(y/n)?y

-----------------------------------------------------------
   Doubly Linked List
-----------------------------------------------------------

1. Insert a node at last
2. Insert a node at first
3. Delete First Node
4. Delete Last Node
5. Display contents of list from beginning
6. Display contents of list from end
Enter your choice: 4

Deleteing last node.....
Node successfully deleted!!!

Do you want to continue(y/n)?y

-----------------------------------------------------------
   Doubly Linked List
-----------------------------------------------------------

1. Insert a node at last
2. Insert a node at first
3. Delete First Node
4. Delete Last Node
5. Display contents of list from beginning
6. Display contents of list from end
Enter your choice: 5

Contents of linked list from beginning are as follows
5-->6
Do you want to continue(y/n)?

About AlgoStream

This is a short description in the author block about the author. You edit it by entering text in the "Biographical Info" field in the user admin panel.