Doubly Linked List

A doubly linked list or two way linked list is a type of linked list that contains a pointer to the next node as well as the previous node in the sequence.

doubly linked list node data structure 1
A doubly linked list node

That is, each node in a doubly-linked list consists of:

  • data – Data Item.
  • prev – Address of previous node.
  • next – Address of next node.

Representation of Doubly Linked List

In C, we can represent a doubly linked list node using structures as:

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

Each struct node contains a data item, a pointer to the previous struct node, and a pointer to the next struct node.

The following example creates a basic Linked List with three items and displays its elements.

Example: Creating a Doubly Linked List

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

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

int main()
{
    // Create and initialize nodes
    struct node *head;
    struct node *one = NULL;
    struct node *two = NULL;
    struct node *three = NULL;
    struct node *current = NULL;

    // Allocate memory for the nodes
    one = (struct node*) malloc(sizeof(struct node));
    two = (struct node*) malloc(sizeof(struct node));
    three = (struct node*) malloc(sizeof(struct node));

    // Assign data to nodes
    one->data = 1;
    two->data = 2;
    three->data = 3;

    // Connect first node
    // with the second node
    one->next = two;
    
    // Connect second node
    // with the third node
    two->next = three;

    // make next pointer of
    //third node to NULL
    //indicates last node
    three->next = NULL;

    //connect previous nodes
    one->prev = NULL;
    two->prev = one;
    three->prev = two;
   
    // Save address of first node in head
    head = one;
    current = head;

    // print the linked list values forward
    while(current != NULL)
    {
        printf("%d ", current->data);
        current = current->next;
    }

    return 0;
}

Now we’ve made a doubly-linked list with three nodes.

doubly linked list data structure representation
Output

1 2 3

Doubly Linked List Operations

Please follow this tutorial

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments