What is Doubly Linked List?

Share

A doubly linked list is the collection of nodes in which every node has three fields previous pointer, data field and next pointer. or A doubly linked list is one in which all nodes are linked together by multiple links which help in accessing both the successor node (next node) and predecessor node (previous node) from any arbitrary node within the list.

  • *prev – address of the previous node
  • data – data item
  • *next – address of next node
fig. doubly linked list

If you want to read about Linked list you should check this article: Linked List and Basic Linked List

Difference between doubly linked list and singly linked list:

Singly Linked List (SLL)Doubly Linked List (DLL)
1. Each node consists of a data value and a pointer to the next node.1. Each node consists of a data value, a pointer to the next node, and a pointer to the previous node.
2. Traversal can occur in one way only (forward direction).2. Traversal can occur in both ways.
3. It requires less space.3. It requires more space because of an extra pointer.
4. It can be implemented on the stack.4. It has multiple usages. It can be implemented on the stack, heap, and binary tree.
SLL Vs DLL

Representation of Doubly Linked List

A node of doubly linked list is represented as:

struct node {
    int data; //actual data
    struct node *next; //pointer for next node
    struct node *prev; //pointer for previous node
}

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

A three-member doubly linked list can be created as:

/* Initialize nodes */
struct node *head;
struct node *one = NULL;//first node
struct node *two = NULL; //second node
struct node *three = NULL; //third node

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

/* Assign data values */
one->data = 1;  //assign data in first node
two->data = 2;  //assign data in second node
three->data = 3; // assign data in third node

/* Connect nodes */
one->next = two; // Link first node and second node ( next node )
one->prev = NULL; //assign null to previous of first node

two->next = three;// Link second node and third node ( next node )
two->prev = one ;// Link second and first node ( previous node )

three->next = NULL;//assign NULL to  next of last node
three->prev = two;// Link third and second node ( previous node )

/* Save address of first node in head */
head = one;

In the above code, onetwo, and three are the nodes with data items 12, and 3 respectively.

  • For node onenext stores the address of two and prev stores null (there is no node before it)
  • For node twonext stores the address of three and prev stores the address of one
  • For node threenext stores null (there is no node after it) and prev stores the address of two.

C program for Doubly linked list

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

// node creation
struct Node {
  int data;
  struct Node* next;
  struct Node* prev;
};

// insert node at the front
void insertFront(struct Node** head, int data) {
  // allocate memory for newNode
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

  // assign data to newNode
  newNode->data = data;

  // make newNode as a head
  newNode->next = (*head);

  // assign null to prev
  newNode->prev = NULL;

  // previous of head (now head is the second node) is newNode
  if ((*head) != NULL)
    (*head)->prev = newNode;

  // head points to newNode
  (*head) = newNode;
}

// insert a node after a specific node
void insertAfter(struct Node* prev_node, int data) {
  // check if previous node is null
  if (prev_node == NULL) {
    printf("previous node cannot be null");
    return;
  }

  // allocate memory for newNode
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

  // assign data to newNode
  newNode->data = data;

  // set next of newNode to next of prev node
  newNode->next = prev_node->next;

  // set next of prev node to newNode
  prev_node->next = newNode;

  // set prev of newNode to the previous node
  newNode->prev = prev_node;

  // set prev of newNode's next to newNode
  if (newNode->next != NULL)
    newNode->next->prev = newNode;
}

// insert a newNode at the end of the list
void insertEnd(struct Node** head, int data) {
  // allocate memory for node
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

  // assign data to newNode
  newNode->data = data;

  // assign null to next of newNode
  newNode->next = NULL;

  // store the head node temporarily (for later use)
  struct Node* temp = *head;

  // if the linked list is empty, make the newNode as head node
  if (*head == NULL) {
    newNode->prev = NULL;
    *head = newNode;
    return;
  }

  // if the linked list is not empty, traverse to the end of the linked list
  while (temp->next != NULL)
    temp = temp->next;

  // now, the last node of the linked list is temp

  // assign next of the last node (temp) to newNode
  temp->next = newNode;

  // assign prev of newNode to temp
  newNode->prev = temp;
}

// delete a node from the doubly linked list
void deleteNode(struct Node** head, struct Node* del_node) {
  // if head or del is null, deletion is not possible
  if (*head == NULL || del_node == NULL)
    return;

  // if del_node is the head node, point the head pointer to the next of del_node
  if (*head == del_node)
    *head = del_node->next;

  // if del_node is not at the last node, point the prev of node next to del_node to the previous of del_node
  if (del_node->next != NULL)
    del_node->next->prev = del_node->prev;

  // if del_node is not the first node, point the next of the previous node to the next node of del_node
  if (del_node->prev != NULL)
    del_node->prev->next = del_node->next;

  // free the memory of del_node
  free(del_node);
}

// print the doubly linked list
void displayList(struct Node* node) {
  struct Node* last;

  while (node != NULL) {
    printf("%d->", node->data);
    last = node;
    node = node->next;
  }
  if (node == NULL)
    printf("NULL\n");
}

int main() {
  // initialize an empty node
  struct Node* head = NULL;

  insertEnd(&head, 5);
  insertFront(&head, 1);
  insertFront(&head, 6);
  insertEnd(&head, 9);

  // insert 11 after head
  insertAfter(head, 11);

  // insert 15 after the seond node
  insertAfter(head->next, 15);

  displayList(head);

  // delete the last node
  deleteNode(&head, head->next->next->next->next->next);

  displayList(head);
}

Output:

Application of Doubly Linked list

  1. Redo and undo functionality in software.
  2. Forward and backward navigation in browsers.
  3. For navigation systems where forward and backward navigation is required.
Share
Raj Tuladhar

Raj Tuladhar

learning everything from everywhere!!

%d bloggers like this: