Doubly Linked List with Code Implementation in C++

A doubly linked list is a linked list in which every node has two pointers (named previous and next) with one data element

  • Previous Pointer: This pointer is of type node which points to the address of the node before it and in case of the first node it is assigned as NULL denoting that it doesn't point to anything. 
  • Next Pointer: This pointer is of type node which points to the address of the node after it and in case of the last node it is assigned as NULL denoting that it doesn't point to anything.
  • Head: A pointer of type node which stores the address of the first node in the linked list.
  • Tail: A pointer of type node which stores the address of the last node in the linked list.

Operations associated with a doubly-linked list :

1. Traversal: Unlike a singly linked list that is unidirectional, a doubly-linked list is bidirectional. We can traverse from the head as well as from the tail.

2.  Insertion at any point: 
To insert a node e between b and c, we will be traversing till b, then 
temp = b.next ( temp is actually c )
e.next = temp
temp.prev = e
b.next = e
e.prev = b
3. Deletion at any point
To delete a node c, we need to traverse till b, then
temp = b.next ( temp is actually c )
temp2 = temp.next (temp2 is actually d)
b.next = temp.next
temp2.prev = temp.prev
free(temp)

  • Video Explanation

Implementation of doubly linked list:


#include <bits/stdc++.h>
void insert(int x, int pos);
void print(struct node *temp);
using namespace std;

struct node {
int data;
struct node *next; // pointer to point the address of
        // next node
struct node *prev; // pointer to point the address of
        // previous node
} *head = NULL; // to point to the first node of
        // linked list

int main() {
int i;
int n;
cin >> n; // Number of nodes
int num, p;
cout << "Enter the value and position " << endl;
for (i = 1; i <= n; i++) {
cin >> num >> p;
insert(num, p);
}
print(head);
return 0;
}

void insert(int x, int pos) {
struct node *nnode;
nnode = (struct node *)malloc(sizeof(struct node));
struct node *temp = head;
nnode->data = x;
if (head == NULL) {
temp = nnode;
nnode->next = NULL; // this is last node so its
            // next->NULL
nnode->prev = NULL; // previous pointer of first
            // node assigned as NULL
head = nnode; // here head is assigned to first
            // node as of now which will help us to iterate
            // through list
} else if (pos == 1) {
head = nnode;
nnode->next = temp;
temp->prev = nnode;
nnode->prev = NULL;
} else {
int i = 1;
while (i != pos - 1) {
temp = temp->next;
i++;
}
if (temp->next == NULL) {
nnode->prev = temp;
nnode->next = NULL;
(temp->next) = nnode;
} else {
nnode->next = (temp->next);
nnode->prev = temp;
(temp->next)->prev = nnode;
temp->next = nnode;
}
}
}

void print(struct node *temp) {
while (temp != NULL) {
cout << temp->data << endl;
temp = temp->next;
}
}


Practice Problems :
  1. Inserting a Node Into a Sorted Doubly Linked List
  2. Reverse a doubly linked list

We can use the concept of a linked list in designing web browsers where we can navigate both backward and forward from a given page. 

In our next article, we will be studying a circular linked list. If there is any error/doubt/ suggestions please comment below. 

Thank You for Reading.

Related Posts



If you like Learn DSA and would like to contribute please mail your article to info.learndsa@gmail.com and see your article appearing on the Learn DSA main page and help others.