Doubly Linked Lists

We strongly recommend to refer Linked lists post as a prerequisite of this post.

A Doubly Linked Lists (DLL) is a linked data structure that consists of sequentially linked nodes. Each node contains three fields: two link fields (prev and next) and one data field.

The beginning and ending nodes' previous and next links, respectively, point to NULL.

---

Following is the representation of a DLL node in C:

struct Node{
    int data; 
    struct Node* prev; // Pointer to previous node in DLL 
    struct Node* next; // Pointer to next node in DLL
};

---

Before moving forward we must discuss some points about DLL:

• As stated it can be traversed in both forward and backward direction.

• The delete operation in DLL is more efficient if pointer to the node to be deleted is given.

• Every node of DLL Require extra space for an previous pointer. It is possible to implement DLL with single pointer though.

• All operations require an extra pointer previous to be maintained

---

Operations that can be performed on DLL:

1) Insertion

2) Deletion

3) Traversing

Simple Implementation Using C:

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

struct Node
{
    int data;
    struct node *prev;
    struct node *next;
}*head=NULL,*tail=NULL,*temp=NULL,*q=NULL;
int count=0;
typedef struct Node node;

void insert_beg();
void insert_end();
void insert_pos();
void delete_pos();
void traverse_beg();
void traverse_end();

void main()
{
    while(1)
    {
        int ch;
        printf("\n-----------------------------");
        printf("\n 1 - Insert at beginning");
        printf("\n 2 - Insert at end");
        printf("\n 3 - Insert at position i");
        printf("\n 4 - Delete at i");
        printf("\n 5 - Display from beginning");
        printf("\n 6 - Display from end");
        printf("\n 7 - Exit");
        printf("\n-----------------------------");
        printf("\n\n Enter your choice (1-7)");
        scanf("%d",&ch);
        switch(ch)
        {
        case 1:
            printf("Inserting at beginning ->");
            insert_beg();
            break;
        case 2:
            printf("Inserting at end ->");
            insert_end();
            break;
        case 3:
            printf("Inserting at i");
            insert_pos();
            break;
        case 4:
            printf("Deleting at i");
            delete_pos();
            break;
        case 5:
            printf("Displaying from beginning");
            traverse_beg();
            break;
        case 6:
            q = head;
            if (q == NULL)
                printf("\n Error : List empty to display ");
            else
            {
                printf("\n Reverse order of linked list is : ");
                traverse_end(q->data);
            }
            break;
        case 7: exit(0);
        default: printf("\n Wrong choice menu");
    }

    }
}

void create()
{
    int data;
    temp=(node*)malloc(sizeof(node));
    printf("\n Enter value of the node: ");
    scanf("%d",&data);
    temp->data=data;
    temp->next=NULL;
    temp->prev=NULL;
    count++;
}

void insert_beg()
{
    if(head==NULL)
    {
        create();
        head=temp;
    }
    else
    {
        create();
        temp->next=head;
        head->prev=temp;
        head=temp;
    }
}

void insert_end()
{
    if(head == NULL)
    {
        create();
        head=temp;
        temp=tail;
    }
    else
    {
        tail=head;
        while(tail->next!=NULL)
        {
            tail=tail->next;
        }
        create();
        tail->next=temp;
        temp->prev=tail;
        tail=temp;
    }
}

void insert_pos()
{
    int pos,i=2;
    printf("\n Enter position to be inserted : ");
    scanf("%d", &pos);
    q = head;
    if(head == NULL && (pos == 1))
    {
        create();
        head=temp;
        tail=head;
        return;
    }
    if((pos < 1) || (pos >= count + 1))
    {
        printf("\n Position out of range");
        return;
    }
    if((head == NULL) && (pos != 1))
    {
        printf("\n Empty list cannot insert other than 1st position");
        return;
    }

    else
    {
        while(i<pos)
        {
            q=q->next;
            i++;
        }
        create();
       temp->prev=q;
       temp->next=q->next;
       q->next=temp->prev;
       q->next=temp;

    }
}
void traverse_beg()
{
    q=head;
    if(q == NULL)
    {
        printf("List empty to display \n");
        return;
    }
     printf("\n Linked list elements from beginning : ");
     while(q->next!=NULL)
     {
         printf("%d",q->data);
         q=q->next;
     }
     printf("%d",q->data);
}
void traverse_end(int i)
{
    if(q!=NULL)
    {
     i=q->data;
     q=q->next;
     traverse_end(i);
     printf("%d",i);
    }
}

void delete_pos()
{
    int i=1,pos;

    printf("Enter position to be deleted : ");
    scanf("%d",&pos);
    q = head;

    if((pos < 1) || (pos >= count +1))
    {
        printf("\n Error : Position out of range !!!!");
        return;
    }
    if(head == NULL)
    {
        printf("\n Error : Empty list no elements to be deleted");
        return;
    }
    else
    {
        while(i < pos)
        {
            q = q->next;
            i++;
        }
        if(i == 1)
        {
            if(q ->next == NULL)
            {
                printf("\n Node deleted from the list");
                free(q);
                q = head = NULL;
                return;
            }
        }
        if(q->next == NULL)
        {
            q->prev = NULL;
            q->next = NULL;
            free(q);
            printf("Node deleted from the list");
            return;
        }
        free(q);
    }
    count--;
}

---

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Recommended Posts:

Linked Lists

MySQL Joins

Quick sort

Linear search

Binary search

Follow programmers door for more.

#programming #DLL #blog