Doubly Linked List

Doubly linked list is a complicated linked list which contains three parts- data which contain useful information, a pointer to the next node and a pointer to the previous node.

The main advantages of using this is that we can traverse in any direction forward or backward. The previous node pointer of the first element and last node pointer of the last element contain NULL value. The main disadvantages of doubly linked list are that it requires more memory as it takes extra pointers to the previous node.

Doubly Linked List Insertion

We need four reference assignments for insertion in a doubly linked list-

prev_node = curr.prev;
new_node.prev = prev_node;
prev_node.next = new_node;
curr.prev = new_node;
new_node.next = curr;

Doubly Linked List Deletion

To delete an element in a doubly linked list, simply link the predecessor of the deleting element to the successor of the deleting element.

prev_node = curr.prev;
succ_node = curr.next;
succ_node.prev = prev_node;
prev_node.next = succ_node;

Double Linked List Program in C

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

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

struct node *start = NULL;

void insert_node_last(int);
void insert_node_first(int);
void delete(int);
void display();

int main()
{
    int n, che;
    do
    {
	printf("\nChoice Options\n\tEnter 1 to insert node at last");
	printf("\nEnter 2 to insert node at first");
	printf("\nEnter 3 to delete node");
	printf("\nEnter 4 to display list from beginning to end");
	printf("\nEnter 5 to exit\n");
	printf("\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
	printf("\nEnter your choice - \n");
	scanf("%d", &che);
        switch (che)
        {
            case 1:
                printf("\nInserting node at first position -");
                scanf("%d", &n);
                insert_node_first(n);
                break;
            case 2:
                printf("\nInserting node at last position - ");
                scanf("%d", &n);
                insert_node_last(n);
                break;
            case 3:
            	printf("\nDeleting node from any position - ");
                scanf("%d", &n);
                delete(n);
                break;
            case 4:
		printf("\nDisplaying List - \n");
		display();
		break;
	case 5:
		return 1;	
	default:
		printf("\nPlease Enter Valid Choice:");
		}	
    }while (che != 0);
	return 0;
}
/*
 * Insert Node at Last
 */
void insert_node_last(int num)
{
    struct node *nptr,  *temp = start;

    /*create a new node */
    nptr = malloc(sizeof(struct node));
    nptr->data = num;
    nptr->next = NULL;
    nptr->prev = NULL;

    /* check for empty linked list */
    if (start == NULL)
    {
        start = nptr;
    } 
    else
    {
        /* reach till the last node */
        while (temp->next != NULL)
		temp = temp->next;

        nptr->prev = temp;
        temp->next = nptr;
    }
}
/*
 * Insert Node at First
 */
void insert_node_first(int num)
{
    struct node *nptr;

    /* allocate space for a new node */
    nptr = malloc(sizeof(struct node));

    nptr->prev = NULL;
    nptr->data = num;
    nptr->next = start;

    if (start != NULL)
        start->prev = nptr;
		start = nptr;
}
/*
 * Delete Node
 */
void delete(int num)
{
    struct node *temp = start;

    
    while (temp != NULL)
    {
        
        if (temp->data == num)
        {
            /* if deleted node to be the first node */
            if (temp == start)
            {
                start = start->next;
                start->prev = NULL;
            } 
            else
            {
                /* if deleted node to be the last node */
                if (temp->next == NULL)
                    temp->prev->next = NULL;
                else
                /* if deleted node to be inside */
                {
                    temp->prev->next = temp->next;
                    temp->next->prev = temp->prev;
                }
                free(temp);
            }
            return ; 
        }
        temp = temp->next;
    }
    printf("\n%d not found.", num);
}

/*
 * Display List
 */
void display()
{
	struct node *temp = start;
    printf("\n");

    while (temp != NULL)
    {
        printf("%d\t", temp->data);
        temp = temp->next;
    } 
}

Output -

Choice Options
	Enter 1 to insert node at last
Enter 2 to insert node at first
Enter 3 to delete node
Enter 4 to display list from beginning to end
Enter 5 to exit

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Enter your choice - 
2

Inserting node at last position - 30

Choice Options
	Enter 1 to insert node at last
Enter 2 to insert node at first
Enter 3 to delete node
Enter 4 to display list from beginning to end
Enter 5 to exit

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Enter your choice - 
1

Inserting node at first position -23

Choice Options
	Enter 1 to insert node at last
Enter 2 to insert node at first
Enter 3 to delete node
Enter 4 to display list from beginning to end
Enter 5 to exit

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Enter your choice - 
2

Inserting node at last position - 90

Choice Options
	Enter 1 to insert node at last
Enter 2 to insert node at first
Enter 3 to delete node
Enter 4 to display list from beginning to end
Enter 5 to exit

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Enter your choice - 
4

Displaying List - 

23	30	90	
Choice Options
	Enter 1 to insert node at last
Enter 2 to insert node at first
Enter 3 to delete node
Enter 4 to display list from beginning to end
Enter 5 to exit

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Enter your choice - 
3

Deleting node from any position - 90

Choice Options
	Enter 1 to insert node at last
Enter 2 to insert node at first
Enter 3 to delete node
Enter 4 to display list from beginning to end
Enter 5 to exit

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Enter your choice - 
4

Displaying List - 

23	30	
Choice Options
	Enter 1 to insert node at last
Enter 2 to insert node at first
Enter 3 to delete node
Enter 4 to display list from beginning to end
Enter 5 to exit

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Enter your choice -