Definition: : A doubly linked list is a linear data structure that is similar to a singly linked list, but each node has a value and two pointers: one to the next node and one to the previous node.

Diagram:

Creation:

Approach:

• Create a class node with int data which will contain value and a pointer node*next which will contain the address of next node.
• Make a constructor which points the next pointer in node to null.
• In the main function, create variables of node* type, assign data to them and link nodes.

Code:

#include <bits/stdc++.h>

using namespace std;

// Structure of Node

class node {

public:

int data;

node* next;

node* prev;

//Constructor

node(int d){

next=NULL;

prev=NULL;

data=d;

}

};

int main()

{

node* head;

node* second;

// Allocate 2 nodes in the heap

head = new node(4);

second = new node(2);

// Point first node’s next pointer to second

head->next = second;

// Point second node’s prev pointer to first

second->prev = first;

printList(head);

return 0;

}

Traversal:

Approach:

• Start from n=head node and print its data.
• Make n=n->next
• Iterate through the list till n!=NULL

Code:

#include <bits/stdc++.h>

using namespace std;

// Structure of Node

class node {

public:

int data;

node* next;

node* prev

//Constructor

node(){

next=NULL;

}

};

void printList(node* n)

{

while (n != NULL) {

cout << n->data << " ";

n = n->next;

}

}

int main()

{

node* head;

node* second;

node* third;

// Allocate 3 nodes in the heap

head = new node(1);

second = new node(2);

third = new node(3);

// Point first node’s next pointer to second

head->next = second;

// Point second node’s prev pointer to first

second->prev = first;

// Point second node’s next pointer to third

second->next = third;

// Point third node’s prev pointer to second

third->prev = second;

printList(head);

return 0;

}

Insertion: Insertion in a singly linked list can be done in 3 ways:

1. At head (In the beginning)
2. At any position
3. At tail (In the end)

Insertion at head

Approach:

• Create a new node ‘n’ and assign the value to node
• If the linked list is empty, make n as the head and tail of list
• Else, n->next= head (Make next of new node as head), make the prev of head as n and move the head to point at n.

Code:

void insertatHead(node*&head, node*&tail, data){

//Create a new node

node*n= new node (data);

//Check if the linked list is empty

if(head==NULL){

head=n;

tail=n;

}

else{

//Add new node before head

n->next=head;

//Point prev of head to new node

head->prev=n;

//Point head to new node

head=n;

}

}

Insertion at tail

Approach:

• Create a new node ‘n’ and assign the value to node
• If the linked list is empty, make n as the head and tail of list
• Else, tail->next= n (Make next of tail as new node), prev of new node as tail and move the tail to point at n.

Code:

void insertatTail(node*&head, node*&tail, data){

//Create a new node

node*n= new node (data);

//Check if the linked list is empty

if(head==NULL){

head=n;

tail=n;

}

else{

//Add new node after tail

tail->next=n;

//Point prev of new node to tail

n->prev=tail;

//Point tail to new node

tail=n;

}

}

Insertion at any position

Approach:

• Create a new node ‘n’ and assign the value to node
• Traverse the linked list till position-1 and point node*temp to it
• Point the next pointer of n node to next pointer of temp node

(n->next=temp->next)

• Point prev of temp->next to ne
• Point next pointer of temp to n

(temp->next=n)

• Point prev of n to temp;

Code:

void insertatPosition(node*&head, node*&tail, int pos){

//Create a new node

node*n= new node (data);

//Create a temp pointer

node*temp=head;

//Traverse the list till position-1

for(int i=1; i<pos-1; i++){

temp=temp->next;

}

n->next=temp->next;

temp->next->prev=n;

temp->next=n;

n->prev=temp;

}

Deletion: Deletion in a singly linked list can be done in 3 ways:

1. At head (In the beginning)
2. At any position
3. At tail (In the end)

Deletion at head

Approach:

• If the linked list is empty, return
• Else if the linked list has a single node, delete head and point head and tail to NULL
• Else, create node*temp and point it to next node of head
• Point prev of temp to NULL
• Delete head
• Make temp as head

Code:

void deleteatHead(node*&head, node*&tail){

//Check if the linked list is empty

if(head==NULL){

return;

}

//Check single node condition

else if(head->next==NULL){

delete head;

head=NULL;

tail=NULL;

}

//Multiple node condition

else{

node*temp=head->next;

temp->prev=NULL;

delete head;

head=temp;

}

}

Deletion at tail

Approach:

• If the linked list is empty, return
• Else if the linked list has a single node, delete head and point head and tail to NULL
• Else, create node*temp and point it to head
• Traverse using temp till second last node of list
• Point next of temp to NULL
• Delete tail
• Make temp as tail

Code:

void deleteatTail(node*&head, node*&tail){

//Check if the linked list is empty

if(head==NULL){

return;

}

//Check single node condition

else if(head->next==NULL){

delete head;

head=NULL;

tail=NULL;

}

//Multiple node condition

else{

node*temp=tail->prev;

temp->next=NULL;

delete tail;

tail=temp;

}

}

Deletion at any position

Approach:

• If the linked list is empty, return
• Create a pointer temp which points to head
• Traverse through the list with temp until pos-1 or until NULL
• Create another pointer next which points to temp->next->next
• Delete temp->next
• Link temp to n
• Point prev of n to temp

Code:

void deleteatPosition(node*&head, node*&tail, int pos){

//Check if the linked list is empty

if(head==NULL){

return;

}

else{

node*temp=head;

for(int i=1; i<pos-1;i++){

temp=temp->next;

}

node*n=temp->next->next;

delete temp->next;

temp->next= n;

n->prev=temp;

}

}

Length: Length of a linked list represents the total number of nodes in it.

Length can be found iteratively or recursively. Both the approaches are discussed below.

Iteratively:

Approach:

• Initialize count to 0
• Create a node* temp which points to head
• Iterate till temp!=NULL and increment count by 1
• Return count

Code:

int length (node*head){

int count=0;

node*temp=head;

while(temp!=NULL){

count++;

temp=temp->next;

}

return count;

}

Recursively:

Approach:

• Base case will be if head is NULL, return 0
• Recursive case will be 1+ length(head->next);

Code:

int length (node*head){

//Base case

if(head==NULL){

return 0;

}

//Recursive case

else{

return 1+ length(head->next);

}

}

Searching: An element can be searched in a linked list either iteratively or recursively. Both the approaches are discussed below.

Iteratively:

Algorithm:

• Create a pointer that points to head
• Iterate through the list, if key is found return true
• Return false

Code:

bool searchIteratively (node* head, int key){

node*temp=head;

while(temp!=NULL){

if(temp->data==key){

return true;

}

temp=temp->next;

}

return false;

}

Recursively:

Algorithm:

• Return false if head is NULL
• Return true if head->data==key
• Return searchrecursively(head->next,key)

Code:

bool searchRecursively (node* head, int key){

//Base Case

if(head==NULL){

return false;

}

//Recursive case

if(head->data==key){

return true;

}

return searchRecursively(head->next,key);

}

Reversing: Reversing a doubly linked list is much easier than reversing a singly linked list as it contains both next as well as prev pointers. It can be reversed either iteratively and recursively. Both the approaches are discussed below.

Iteratively:

Algorithm:

• Initialize three pointers: ‘current’ pointing to the head of the list, ‘temp’ pointing to the next node, and ‘previous’ pointing to NULL.
• Traverse through the list using the ‘current’ pointer until it reaches the end of the list, i.e., when ‘current’ becomes NULL.
• Inside the loop, set ‘temp’ to the next node of ‘current’.
• Reverse the prev and next pointers of ‘current’. Set ‘current->prev’ to ‘temp’ and ‘current->next’ to ‘previous’.
• Move ‘previous’ to ‘current’ and ‘current’ to ‘temp’. This step prepares for the next iteration by moving the pointers forward in the list.
• After the loop ends, the ‘previous’ pointer will be pointing to the last node of the original list, which will be the new head of the reversed list.
• Return the ‘previous’ pointer as the new head of the reversed list.

Code:

Node* reverseIteratively(Node* head) {

Node* current = head;

Node* previous = NULL;

while (current != NULL) {

Node* temp = current->next;

current->next = previous;

current->prev = temp;

previous = current;

current = temp;

}

return previous;

}

Recursively:

Algorithm:

• Base case: If the current node is NULL or the list is empty, return the current node.
• Swap the prev and next pointers of the current node.
• Recursively call the reverse function on the next node.
• After the recursion returns, update the prev and next pointers of the current node based on the reversed next node.
• Return the current node as the new head of the reversed list.

Code:

Node* reverseRecursively(Node* current) {

// Base case: empty list or end of the list

if (current == NULL || current->next == NULL) {

// Set the previous pointer to NULL

if (current != NULL)

current->prev = NULL;

return current;

}

// Recursively reverse the rest of the list

Node* nextNode = current->next;

Node* newHead = reverseRecursively(nextNode);

// Swap the prev and next pointers of the current node

current->next = current->prev;

current->prev = nextNode;

// Update the prev and next pointers of the current node

if (nextNode != NULL)

nextNode->next = current;

return newHead;

}

Find mid:

Algorithm:

• Traverse the linked list using 2 pointers
• Move slow pointer by 1 and fast pointer by 2
• When fast pointer reaches NULL, slow pointer will be at middle

Code:

int middle(node* head){

node* slow=head;

node* fast=head;

if(head!=NULL){

while(fast!=NULL && fast->next!=NULL){

fast= fast->next->next;

slow=slow->next;

}

return slow->data;

}