Doubly Linked List

As we know, Singly Linked List is unidirectional as we have the address of only next node. So it can travel only in forward direction.

Instead, Doubly Linked List is bidirectional. It is an ordered list of nodes in which, each node contains the address of its next (successor) as well as previous (predecessor) node.

Each node has three parts :

  • previous : It is a pointer field contains address of its previous node.
  • info or data : Contains actual value.
  • next : Contains address of next node.


Node declaration in Doubly Linked List

struct Node
{
int info; // Data values
struct Node *next; // Address of next Node
struct Node *prev; // Address of previous Node
};


Implementation of Doubly Linked List


  • Doubly Linked List Creation and Traversal
Source Code (Doubly Linked List Creation and Traversal)

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

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

void DoublyLinkedListTraversal(struct Node *head)
{
    struct Node *p = head;

    while (p != NULL)
    {
        printf("Element : %d\n", p->data);
        p = p->next;
    }
}

void DoublyLinkedListBackwardTraversal(struct Node *head)
{
    struct Node *p = head;
    while (p->next != NULL)
    {
        p = p->next;
    }
    while (p != NULL)
    {
        printf("Element : %d\n", p->data);
        p = p->prev;
    }
}

void main()
{

    struct Node *head = (struct Node *)malloc(sizeof(struct Node));
    struct Node *second = (struct Node *)malloc(sizeof(struct Node));
    struct Node *third = (struct Node *)malloc(sizeof(struct Node));
    struct Node *fourth = (struct Node *)malloc(sizeof(struct Node));

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

    second->data = 31;
    second->prev = head;
    second->next = third;

    third->data = 02;
    third->prev = second;
    third->next = fourth;

    fourth->data = 50;
    fourth->prev = third;
    fourth->next = NULL;

    // Doubly Linked List Traversal : Printing all data of Doubly Linked List
    printf("\nDoubly Linked List Traversal : \n");

    printf("\n1. Forward Traversal :\n");
    DoublyLinkedListTraversal(head);

    printf("\n2. Backward Traversal :\n");
    DoublyLinkedListBackwardTraversal(head);

    printf("\n");
}


Output

Doubly Linked List Traversal :

1. Forward Traversal :
Element : 25
Element : 31
Element : 2
Element : 50

2. Backward Traversal :
Element : 50
Element : 2
Element : 31
Element : 25

  • Doubly Linked List Insertion
Source Code (Doubly Linked List Insertion)

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

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

void DoublyLinkedListTraversal(struct Node *head)
{
    struct Node *p = head;

    while (p != NULL)
    {
        printf("Element : %d\n", p->data);
        p = p->next;
    }
}

void DoublyLinkedListBackwardTraversal(struct Node *head)
{
    struct Node *p = head;
    while (p->next != NULL)
    {
        p = p->next;
    }
    while (p != NULL)
    {
        printf("Element : %d\n", p->data);
        p = p->prev;
    }
}

struct Node *Doubly_InsertionAtBeginning(struct Node *head, int data)
{
    struct Node *ptr = (struct Node *)malloc(sizeof(struct Node));
    ptr->data = data;
    ptr->prev = NULL;
    ptr->next = head;
    head->prev = ptr;
    head = ptr;
    return (head);
}

struct Node *Doubly_InsertionAtEnd(struct Node *head, int data)
{
    struct Node *ptr = (struct Node *)malloc(sizeof(struct Node));
    ptr->data = data;
    ptr->next = NULL;
    struct Node *p = head;

    while (p->next != NULL)
    {
        p = p->next;
    }
    p->next = ptr;
    ptr->prev = p;
    return (head);
}

struct Node *Doubly_InsertionAtIndex(struct Node *head, int index, int data)
{
    struct Node *ptr = (struct Node *)malloc(sizeof(struct Node));
    ptr->data = data;
    struct Node *p, *q;
    p = head;
    int i = 0;
    while (i != index - 1)
    {
        p = p->next;
        i++;
    }
    q = p->prev;
    q->next = ptr;
    ptr->prev = q;
    ptr->next = p;
    p->prev = ptr;
    return (head);
}

void main()
{

    struct Node *head = (struct Node *)malloc(sizeof(struct Node));
    struct Node *second = (struct Node *)malloc(sizeof(struct Node));
    struct Node *third = (struct Node *)malloc(sizeof(struct Node));
    struct Node *fourth = (struct Node *)malloc(sizeof(struct Node));

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

    second->data = 31;
    second->prev = head;
    second->next = third;

    third->data = 02;
    third->prev = second;
    third->next = fourth;

    fourth->data = 50;
    fourth->prev = third;
    fourth->next = NULL;

    // Doubly Linked List Traversal : Printing all data of Doubly Linked List
    printf("\nDoubly Linked List Traversal : \n");
    printf("\n1. Forward Traversal :\n");
    DoublyLinkedListTraversal(head);
    printf("\n2. Backward Traversal :\n");
    DoublyLinkedListBackwardTraversal(head);
    printf("\n");

    // Insertion at beginning
    printf("\nDoubly Linked List Insertion at the beginning : \n");
    head = Doubly_InsertionAtBeginning(head, 100);
    DoublyLinkedListTraversal(head);
    printf("\n");

    // Insertion at the End
    printf("\nDoubly Linked List Insertion at the End : \n");
    head = Doubly_InsertionAtEnd(head, 500);
    DoublyLinkedListTraversal(head);
    printf("\n");

    // Insertion at the given index
    int index = 3;
    printf("\nDoubly Linked List Insertion at the Index : %d\n", index);
    head = Doubly_InsertionAtIndex(head, index, 800);
    DoublyLinkedListTraversal(head);
    printf("\n");
}

Output

Doubly Linked List Traversal : 

1. Forward Traversal :
Element : 25
Element : 31
Element : 2
Element : 50

2. Backward Traversal :
Element : 50
Element : 2
Element : 31
Element : 25


Doubly Linked List Insertion at the beginning :
Element : 100
Element : 25
Element : 31
Element : 2
Element : 50


Doubly Linked List Insertion at the End :
Element : 100
Element : 25
Element : 31
Element : 2
Element : 50
Element : 500


Doubly Linked List Insertion at the Index : 3
Element : 100
Element : 25
Element : 800
Element : 31
Element : 2
Element : 50
Element : 500

  • Doubly Linked List Deletion
Source Code (Doubly Linked List Deletion)

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

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

void DoublyLinkedListTraversal(struct Node *head)
{
    struct Node *p = head;

    while (p != NULL)
    {
        printf("Element : %d\n", p->data);
        p = p->next;
    }
}

void DoublyLinkedListBackwardTraversal(struct Node *head)
{
    struct Node *p = head;
    printf("\n2. Backward Traversal :\n");
    while (p->next != NULL)
    {
        p = p->next;
    }
    while (p != NULL)
    {
        printf("Element : %d\n", p->data);
        p = p->prev;
    }
}

struct Node *Doubly_DeletionAtBeginning(struct Node *head)
{
    struct Node *p = head;
    head = head->next;
    head->prev = NULL;
    free(p);
    return (head);
}

struct Node *Doubly_DeletionAtEnd(struct Node *head)
{
    struct Node *p = head;
    struct Node *q;
    while (p->next != NULL)
    {
        p = p->next;
    }
    q = p->prev;
    q->next = NULL;
    free(p);
    return (head);
}

struct Node *Doubly_DeletionAtIndex(struct Node *head, int index)
{
    struct Node *p, *q, *temp;
    p = head;
    int i = 0;
    while (i != index)
    {
        p = p->next;
        i++;
    }
    temp = p->prev;

    if (temp->prev == NULL)
    {
        head = Doubly_DeletionAtBeginning(head);
        return head;
    }

    if (temp->next == NULL)
    {
        head = Doubly_DeletionAtEnd(head);
        return head;
    }

    q = temp->prev;
    q->next = p;
    p->prev = q;
    free(temp);
    return (head);
}

struct Node *Doubly_DeletionAtGivenValue(struct Node *head, int val)
{
    struct Node *p, *q, *temp;
    temp = head;

    while (temp->data != val && temp->next != NULL)
    {
        temp = temp->next;
    }

    if (temp->data == val)
    {

        if (temp->prev == NULL)
        {
            head = Doubly_DeletionAtBeginning(head);
            return head;
        }

        if (temp->next == NULL)
        {
            head = Doubly_DeletionAtEnd(head);
            return head;
        }

        p = temp->next;
        q = temp->prev;

        q->next = p;
        p->prev = q;
        free(temp);
        return (head);
    }
}

void main()
{

    struct Node *head = (struct Node *)malloc(sizeof(struct Node));
    struct Node *second = (struct Node *)malloc(sizeof(struct Node));
    struct Node *third = (struct Node *)malloc(sizeof(struct Node));
    struct Node *fourth = (struct Node *)malloc(sizeof(struct Node));
    struct Node *fifth = (struct Node *)malloc(sizeof(struct Node));
    struct Node *sixth = (struct Node *)malloc(sizeof(struct Node));

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

    second->data = 31;
    second->prev = head;
    second->next = third;

    third->data = 02;
    third->prev = second;
    third->next = fourth;

    fourth->data = 50;
    fourth->prev = third;
    fourth->next = fifth;

    fifth->data = 50;
    fifth->prev = fourth;
    fifth->next = NULL;

    sixth->data = 50;
    sixth->prev = fifth;
    sixth->next = NULL;

    // Doubly Linked List Traversal : Printing all data of Doubly Linked List
    printf("\nDoubly Linked List Traversal : \n");
    printf("\n1. Forward Traversal :\n");
    DoublyLinkedListTraversal(head);
    DoublyLinkedListBackwardTraversal(head);
    printf("\n");

    // Deletion at beginning
    printf("Doubly Linked List Deletion at the beginning : \n");
    head = Doubly_DeletionAtBeginning(head);
    DoublyLinkedListTraversal(head);
    printf("\n");

    // Deletion at the End
    printf("Doubly Linked List Deletion at the End : \n");
    head = Doubly_DeletionAtEnd(head);
    DoublyLinkedListTraversal(head);
    printf("\n");

    // Deletion at the given index
    int index = 1;
    printf("Doubly Linked List Deletion at the Index : %d\n", index);
    head = Doubly_DeletionAtIndex(head, index);
    DoublyLinkedListTraversal(head);

    // Deletion of the given value
    int val = 2;
    printf("\nDoubly Linked List Deletion of the given value : %d\n", val);
    head = Doubly_DeletionAtGivenValue(head, val);
    DoublyLinkedListTraversal(head);
    printf("\n");
}

Output

Doubly Linked List Traversal :

1. Forward Traversal :
Element : 25
Element : 31
Element : 2
Element : 50
Element : 50

2. Backward Traversal :
Element : 50
Element : 50
Element : 2
Element : 31
Element : 25

Doubly Linked List Deletion at the beginning :
Element : 31
Element : 2
Element : 50
Element : 50

Doubly Linked List Deletion at the End :
Element : 31
Element : 2
Element : 50

Doubly Linked List Deletion at the Index : 1
Element : 2
Element : 50

Doubly Linked List Deletion of the given value : 2
Element : 50

Comments

Post a Comment

Popular posts from this blog

Searching Algorithms in Data Structure

Searching is a process of retriving or locating or finding information matching with some specific value. In data structure there are two types of searching. Linear or sequencial search Binary search   Linear or Sequencial Search It is a simplest form of searching and can be applied for sequencial storage such as array, stack, queue, linked list. Algorithm Linear/Sequencial Search Step 1: Start Step 2: Set 0 to i Step 3: Read and store value to search in val Step 4: if a(i) = val, print value is found at (i+1) position and go to step 8 Step 5: Set i to i + 1 Step 6: If i is less than n then, go to Step 4 Step 7: Print element not found Step 8: Stop n - size of array a - array val - value to be searched in array Source Code #include <stdio.h> #include <conio.h> #include <stdlib.h> int main() { int n; printf("Enter the size of array : "); scanf("%d", &n); int arr[n]; for...
Read more

Sorting Algorithms in Data Structure

Sorting is a process of arranging information either in ascending or in descending order of key values. In data structures there are techniques available to sort the data. Types of sorting algorithms Bubble sort Insertion sort Selection sort Quick sort Radix sort Merge sort   1. Bubble Sort It is one of the simplest & popular sorting method. The basic idea of this sorting is that in each pass we have to compare a successive pair of element i.e. a[i] & a[i+1]. Interchange these two values, if they are not place in proper order. Place the element in it's correct position in each pass. In first pass largest element is shifted at bottom. In second pass second largest will be shifted to the second last position & so on. Thus to sort n values n-1 passes are required. Algorithm Bubble Sort Step 1: Start Step 2: Set 1 to pass Step 3: Set o to i Step 4: if a[i]> a[i+1] then, Swap a[i] & a[i+1] Step 5: Add I to i. Step 6: If i...
Read more

Circular Linked List

Image
I n a Circular Linked List the first and the last elements are adjacent. A linked list can be made circular by storing the address of the first node in the next field of the last node. In a circular linked list, last node is connected back to the first node. In some applications, it is convenient to use circular linked list. A queue data structure can be implemented using a circular linked list, with a single pointer "rear" as the front node can be accessed through the rear node. Implementation of Circular Linked List Circular Linked List Creation and Traversal Algorithm for traversing a circular list is slightly different than the same algorithm for a singly linked list because "NULL" is not encountered. Source Code (Circular Linked List Creation and Traversal) #include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node *next; }; void CircularLinkedListTraversal(stru...
Read more