Introduction to Doubly Linked List

What are Doubly Linked Lists?

Doubly linked lists are an extension to singly linked lists and provide a little more additional features and security to singly-linked lists. Let us see what these linked lists are –

Linked Lists

 Doubly Linked list

Doubly linked lists have the following –

  • Data: Like Singly-linked lists, it also contains data that is stored.
  • Pointer (next) – Contains the address of the next node in the doubly linked list
  • Pointer (previous) – Contains the address of the previous node in the doubly linked list

Apart from these basic terminologies are same – Node, Head, Tail

doubly linked list

Advantages

  1. It is better as unlike singly linked list, in a doubly-linked list we can traverse in both directions. Thus, if in case any pointer is lost we can still traverse.
  2. Thus, in Doubly Linked List we can traverse from Head to Tail as well as Tail to Head.
  3. Delete operation is quicker if the pointer to the node to be deleted is given to us already.
  4. Insertion is quicker in doubly-linked lists.

Disadvantages

  1. Extra space is required for the previous pointer for doubly-linked lists(DLL)
  2. All operations require an additional modification of the previous pointer as well along with next pointer.

Creation of Doubly linked lists

Now we are discussing How to create a Node for a Doubly linked list.

struct Node {
int Data;
Struct Node* next;
Struct Node*  prev;
};

Code for Insertion and Access for Linked list

//We are creating program for doubly linked list creation
#include <stdio.h>
#include <stdlib.h>
//stdlib used to provide a declaration of ‘malloc’

// structure of linked list
struct Node {
int data;
struct Node* next;
struct Node* prev;
// Pointer pointing towards next node
};

//function to print the doubly linked list
void display(struct Node* node)
{
struct Node *end;
printf("List in Forward direction: ");
while (node != NULL) {
printf(" %d ", node->data);
end = node;
node = node->next;
}

printf("\nList in backward direction: ");

while (end != NULL) {
printf(" %d ", end->data);
end = end->prev;
}


}

// main function
int main()
{
//creating 4 pointers of type struct Node
//So these can point to address of struct type variable
struct Node* head = NULL;
struct Node* node2 = NULL;
struct Node* node3 = NULL;
struct Node* node4 = NULL;

// allocate 4 nodes in the heap
head = (struct Node*)malloc(sizeof(struct Node));
node2 = (struct Node*)malloc(sizeof(struct Node));
node3 = (struct Node*)malloc(sizeof(struct Node));
node4 = (struct Node*)malloc(sizeof(struct Node));

/* Using malloc method we have created 4 memory blocks
Each memory block is of type struct and has int data and Pointer of type Node
So it can point towards a node type struct.

head node2 node3 node4
| | | |
| | | |
+---++---+-----+ +----+----+----+ +----+----+----+ +----+----+----+
|prev|data|next| |prev|data|next| |prev|data|next| |prev|data|next|
+---++---+-----+ +----+----+----+ +----+----+----+ +----+----+----+

# As of now data has garbage value and its pointer
points towards random addresses*/

head->data = 5; // data set for head node
head->next = node2; // next pointer assigned to address of node2
head->prev = NULL;

node2->data = 10;
node2->next = node3;
node2->prev = head;

node3->data = 12;
node3->next = node4;
node3->prev = node2;

node4->data = 3;
node4->next = NULL;
node4->prev = node3;

//last node assigned to Null as linked list ends here
/*
head node2 node3 node4
| | | |
| | | |
+---++---+-----+ +----+----+----+ +----+----+----+ +----+----+----+
|prev| 5 |next|--->|prev| 10 |next|--->|prev| 12 |next|--->|prev| 3 |next|
+---++---+-----+ +----+----+----+ +----+----+----+ +----+----+----+

*/


display(head);

return 0;
}