Doubly Linked List Tutorial - Coding

A doubly linked list is a more complex data structure than a singly linked list, but it offers several advantages. The main advantage of a doubly linked list is that it allows for efficient traversal of the list in both directions. This is because each node in the list contains a pointer to the previous node and a pointer to the next node. This allows for quick and easy insertion and deletion of nodes from the list, as well as efficient traversal of the list in both directions.

Doubly Linked List in Data Structure

What is a Doubly Linked List?

A doubly linked list is a data structure that consists of a set of nodes, each of which contains a value and two pointers, one pointing to the previous node in the list and one pointing to the next node in the list. This allows for efficient traversal of the list in both directions, making it suitable for applications where frequent insertions and deletions are required.

Representation of Doubly Linked List in Data Structure:

In a data structure, a doubly linked list is represented using nodes that have three fields:

Data
A pointer to the next node (next)
A pointer to the previous node (prev).

Node Definition:

Here is how a node in a Doubly Linked List is typically represented:

C++

struct Node {

    // To store the Value or data.
    int data;

    // Pointer to point the Previous Element
    Node* prev;

    // Pointer to point the Next Element
    Node* next;
  
    // Constructor
    Node(int d) {
       data = d;
       prev = next = nullptr;      
    }
};

struct Node {

    // To store the Value or data.
    int data;

    // Pointer to point the Previous Element
    Node* prev;

    // Pointer to point the Next Element
    Node* next;
};

Java

class Node {

    // To store the Value or data.
    int data;

    // Referenxce to the Previous Node
    Node prev;
  
    // Referenxce to the next Node
    Node next;
  
    // Constructor
    Node(int d) {
       data = d;
       prev = next = null;      
    }
};

Python

class Node:
  
    def __init__(self, data):
        # To store the value or data.
        self.data = data

        # Reference to the previous node
        self.prev = None

        # Reference to the next node
        self.next = None

class Node
{
    public int Data; // Data stored in the node
    public Node Next; // Pointer to the next node
    public Node Prev; // Pointer to the previous node

    // Constructor
    public Node(int d)
    {
        Data = d;
        Prev = Next = null;      
    }
}

JavaScript

class Node {
    constructor(data)
    {
        // To store the value or data.
        this.data = data;

        // Reference to the previous node
        this.prev = null;

        // Reference to the next node
        this.next = null;
    }
}

Each node in a Doubly Linked List contains the data it holds, a pointer to the next node in the list, and a pointer to the previous node in the list. By linking these nodes together through the next and prev pointers, we can traverse the list in both directions (forward and backward), which is a key feature of a Doubly Linked List.

Operations on Doubly Linked List:

Traversal in Doubly Linked List
Searching in Doubly Linked List
Finding Length of Doubly Linked List
Insertion in Doubly Linked List:
- Insertion at the beginning of Doubly Linked List
- Insertion at the end of the Doubly Linked List
- Insertion at a specific position in Doubly Linked List
Deletion in Doubly Linked List:
- Deletion of a node at the beginning of Doubly Linked List
- Deletion of a node at the end of Doubly Linked List
- Deletion of a node at a specific position in Doubly Linked List

Let’s go through each of the operations mentioned above, one by one.

Traversal in Doubly Linked List:

To Traverse the doubly list, we can use the following steps:

a. Forward Traversal:

Initialize a pointer to the head of the linked list.
While the pointer is not null:
Visit the data at the current node.
Move the pointer to the next node.

b. Backward Traversal:

Initialize a pointer to the tail of the linked list.
While the pointer is not null:
Visit the data at the current node.
Move the pointer to the previous node.

Below are the implementation of the above approach:

C++

#include <iostream>
using namespace std;

// Define the Node structure
struct Node {
    int data; 
    Node* next; 
    Node* prev; 
  
    // Constructor to initialize Node with data
    Node(int data) : data(data), next(nullptr), prev(nullptr) {}
};

// Function to traverse the doubly linked list 
// in forward direction
void forwardTraversal(Node* head) {
  
    // Start traversal from the head of the list
    Node* curr = head;

    // Continue until current node is not null
    // (end of list)
    while (curr != nullptr) {
      
        // Output data of the current node
        cout << curr->data << " ";

        // Move to the next node
        curr = curr->next;
    }

    // Print newline after traversal
    cout << endl;
}

// Function to traverse the doubly linked list 
// in backward direction
void backwardTraversal(Node* tail) {
  
    // Start traversal from the tail of the list
    Node* curr = tail;

    // Continue until current node is not null 
    // (end of list)
    while (curr != nullptr) {
      
        // Output data of the current node
        cout << curr->data << " ";

        // Move to the previous node
        curr = curr->prev;
    }

    // Print newline after traversal
    cout << endl;
}

int main() {
  
    // Sample usage of the doubly linked list and 
    // traversal functions
    Node* head = new Node(1);
    Node* second = new Node(2);
    Node* third = new Node(3);

    head->next = second;
    second->prev = head;
    second->next = third;
    third->prev = second;

    cout << "Forward Traversal:" << endl;
    forwardTraversal(head);

    cout << "Backward Traversal:" << endl;
    backwardTraversal(third);

    return 0;
}

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

// Define the Node structure
struct Node {
    int data; // Data stored in the node
    struct Node* next; // Pointer to the next node
    struct Node* prev; // Pointer to the previous node
};

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = 
      (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

// Function to traverse the doubly linked list 
// in forward direction
void forwardTraversal(struct Node* head) {
  
    // Start traversal from the head of the list
    struct Node* curr = head;

    // Continue until the current node is not
    // null (end of list)
    while (curr != NULL) {
      
        // Output data of the current node
        printf("%d ", curr->data);
      
        // Move to the next node
        curr = curr->next;
    }

    // Print newline after traversal
    printf("\n");
}

// Function to traverse the doubly linked list 
// in backward direction
void backwardTraversal(struct Node* tail) {
  
    // Start traversal from the tail of the list
    struct Node* curr = tail;

    // Continue until the current node is not 
    // null (end of list)
    while (curr != NULL) {
      
        // Output data of the current node
        printf("%d ", curr->data);
      
        // Move to the previous node
        curr = curr->prev;
    }

    // Print newline after traversal
    printf("\n");
}

int main() {
  
    // Sample usage of the doubly linked list and 
    // traversal functions
    struct Node* head = createNode(1);
    struct Node* second = createNode(2);
    struct Node* third = createNode(3);

    head->next = second;
    second->prev = head;
    second->next = third;
    third->prev = second;

    printf("Forward Traversal:\n");
    forwardTraversal(head);

    printf("Backward Traversal:\n");
    backwardTraversal(third);

    // Free memory allocated for nodes
    free(head);
    free(second);
    free(third);

    return 0;
}

Java

// Define the Node class
class Node {
    int data; // Data stored in the node
    Node next; // Pointer to the next node
    Node prev; // Pointer to the previous node

    // Constructor to initialize the node with data
    public Node(int data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

// Class to manage the doubly linked list
public class GfG {

    // Function to traverse the doubly linked list 
    // in forward direction
    static void forwardTraversal(Node head) {
      
        // Start traversal from the head of the list
        Node curr = head;

        // Continue until the current node is 
        // null (end of the list)
        while (curr != null) {
          
            // Output data of the current node
            System.out.print(curr.data + " ");
          
            // Move to the next node
            curr = curr.next;
        }

        // Print newline after traversal
        System.out.println();
    }

    // Function to traverse the doubly linked list in backward direction
    static void backwardTraversal(Node tail) {
      
        // Start traversal from the tail of the list
        Node curr = tail;

        // Continue until the current node is 
        // null (end of the list)
        while (curr != null) {
          
            // Output data of the current node
            System.out.print(curr.data + " ");
          
            // Move to the previous node
            curr = curr.prev;
        }

        // Print newline after traversal
        System.out.println();
    }

    public static void main(String[] args) {
      
        // Sample usage of the doubly linked
        // list and traversal functions
        Node head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);

        head.next = second;
        second.prev = head;
        second.next = third;
        third.prev = second;

        System.out.println("Forward Traversal:");
        forwardTraversal(head);

        System.out.println("Backward Traversal:");
        backwardTraversal(third);
    }
}

Python

# Define the Node class
class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

# Function to traverse the doubly linked list 
# in forward direction
def forward_traversal(head):
  
    # Start traversal from the head of the list
    curr = head
    
    # Continue until the current node is 
    # null (end of the list)
    while curr is not None:
      
        # Output data of the current node
        print(curr.data, end=" ")
        
        # Move to the next node
        curr = curr.next
        
    # Print newline after traversal
    print()

# Function to traverse the doubly linked 
# list in backward direction
def backward_traversal(tail):
  
    # Start traversal from the tail of the list
    curr = tail
    
    # Continue until the current node 
    # is null (end of the list)
    while curr is not None:
      
        # Output data of the current node
        print(curr.data, end=" ")
        
        # Move to the previous node
        curr = curr.prev
        
    # Print newline after traversal
    print()

# Sample usage of the doubly linked list 
# and traversal functions
if __name__ == "__main__":
  
    # Create a doubly linked list with 3 nodes
    head = Node(1)
    second = Node(2)
    third = Node(3)

    head.next = second
    second.prev = head
    second.next = third
    third.prev = second

    print("Forward Traversal:")
    forward_traversal(head)

    print("Backward Traversal:")
    backward_traversal(third)

using System;

// Define the Node class
class Node
{
    public int Data; // Data stored in the node
    public Node Next; // Pointer to the next node
    public Node Prev; // Pointer to the previous node

    // Constructor to initialize the node with data
    public Node(int data)
    {
        Data = data;
        Next = null;
        Prev = null;
    }
}

// Class to manage the doubly linked list
class GfG
{
    // Function to traverse the doubly linked list in forward direction
    static void ForwardTraversal(Node head)
    {
        // Start traversal from the head of the list
        Node curr = head;

        // Continue until the current node is null (end of the list)
        while (curr != null)
        {
            // Output data of the current node
            Console.Write(curr.Data + " ");

            // Move to the next node
            curr = curr.Next;
        }

        // Print newline after traversal
        Console.WriteLine();
    }

    // Function to traverse the doubly linked list in backward direction
    static void BackwardTraversal(Node tail)
    {
        // Start traversal from the tail of the list
        Node curr = tail;

        // Continue until the current node is null (end of the list)
        while (curr != null)
        {
            // Output data of the current node
            Console.Write(curr.Data + " ");

            // Move to the previous node
            curr = curr.Prev;
        }

        // Print newline after traversal
        Console.WriteLine();
    }

    public static void Main()
    {
        // Sample usage of the doubly linked list and traversal functions
        Node head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);

        head.Next = second;
        second.Prev = head;
        second.Next = third;
        third.Prev = second;

        Console.WriteLine("Forward Traversal:");
        ForwardTraversal(head);

        Console.WriteLine("Backward Traversal:");
        BackwardTraversal(third);
    }
}

JavaScript

// Define the Node class
class Node {
    constructor(data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

// Function to traverse the doubly linked list 
// in forward direction
function forwardTraversal(head) {

    // Start traversal from the head of the list
    let curr = head;
    
    // Continue until the current node is null 
    // (end of the list)
    while (curr !== null) {
    
        // Output data of the current node
        console.log(curr.data + " ");
        
        // Move to the next node
        curr = curr.next;
    }
    
    // Print newline after traversal
    console.log();
}

// Function to traverse the doubly linked list 
// in backward direction
function backwardTraversal(tail) {

    // Start traversal from the tail of the list
    let curr = tail;
    
    // Continue until the current node is null 
    // (end of the list)
    while (curr !== null) {
    
        // Output data of the current node
        console.log(curr.data + " ");
        
        // Move to the previous node
        curr = curr.prev;
    }
    
    // Print newline after traversal
    console.log();
}

// Sample usage of the doubly linked list and traversal functions
// Create a doubly linked list with 3 nodes
const head = new Node(1);
const second = new Node(2);
const third = new Node(3);

head.next = second;
second.prev = head;
second.next = third;
third.prev = second;

console.log("Forward Traversal:");
forwardTraversal(head);

console.log("Backward Traversal:");
backwardTraversal(third);

Output

Forward Traversal:
1 2 3 
Backward Traversal:
3 2 1

Finding Length of Doubly Linked List:

To find the length of doubly list, we can use the following steps:

Start at the head of the list.
Traverse through the list, counting each node visited.
Return the total count of nodes as the length of the list.

Below are the implementation of the above approach:

C++

#include <iostream>
using namespace std;

// Node structure for doubly linked list
struct Node {
    int data; 
    Node* prev; 
    Node* next;
   
    // Constructor
    Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

// Function to find the length of a doubly linked list
int findLength(Node* head) {
    int count = 0;
    for (Node* cur = head; cur != nullptr; cur = cur->next)
        count++;
    return count;
}

int main() {
  
    // Create a DLL with 3 nodes
    Node* head = new Node(1);
    Node* second = new Node(2);
    Node* third = new Node(3);
    head->next = second; second->prev = head;
    second->next = third; third->prev = second;

    cout << "Length of the doubly linked list: "
         << findLength(head) << endl;

    return 0;
}

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

// Node structure for doubly linked list
struct Node {
    int data; // Data stored in the node
    struct Node* prev; // Pointer to the previous node
    struct Node* next; // Pointer to the next node
};

// Constructor function to create a new node
struct Node* createNode(int val) {
    struct Node* newNode = 
         (struct Node*)malloc(sizeof(struct Node));
    newNode->data = val;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

// Function to find the length of a doubly linked list
int findLength(struct Node* head) {
    int count = 0;
    for (struct Node* cur = head; cur != NULL; cur = cur->next)
        count++;
    return count;
}

int main() {
    // Create a DLL with 3 nodes
    struct Node* head = createNode(1);
    struct Node* second = createNode(2);
    struct Node* third = createNode(3);

    head->next = second; 
    second->prev = head;
    second->next = third; 
    third->prev = second;

    printf("Length of the doubly linked list: %d\n", 
           findLength(head));

    return 0;
}

Java

class Node {
    int data; 
    Node prev; 
    Node next;

    // Constructor
    public Node(int val) { 
        data = val; 
        prev = null; 
        next = null; 
    }
}

class GfG {

    // Function to find the length of 
    // a doubly linked list
    static int FindLength(Node head) {
        int count = 0;
        for (Node cur = head; cur != null; cur = cur.next)
            count++;
        return count;
    }

    // Driver code
    public static void main(String[] args) {
      
        // Create a doubly linked list 
        // with 3 nodes
        Node head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);
        
        head.next = second; 
        second.prev = head;
        second.next = third; 
        third.prev = second;

        System.out.println("Length of the doubly linked list: " + 
                                 FindLength(head));
    }
}

Python

class Node:
    def __init__(self, val):
        self.data = val
        self.prev = None
        self.next = None

# Function to find the length of 
# a doubly linked list
def find_length(head):
    count = 0
    cur = head
    while cur is not None:
        count += 1
        cur = cur.next
    return count

# Driver code
if __name__ == "__main__":
  
    # Create a doubly linked list 
    # with 3 nodes
    head = Node(1)
    second = Node(2)
    third = Node(3)

    head.next = second
    second.prev = head
    second.next = third
    third.prev = second

    print("Length of the doubly linked list: " +
          str(find_length(head)))

class Node {
    public int data; 
    public Node prev; 
    public Node next;

    // Constructor
    public Node(int val) { 
        data = val; 
        prev = null; 
        next = null; 
    }
}

public class GfG {

    // Function to find the length of 
    // a doubly linked list
    static int FindLength(Node head) {
        int count = 0;
        for (Node cur = head; cur != null; cur = cur.next)
            count++;
        return count;
    }

    // Driver code
    public static void Main(string[] args) {
      
        // Create a doubly linked list 
        // with 3 nodes
        Node head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);
        
        head.next = second; 
        second.prev = head;
        second.next = third; 
        third.prev = second;

        System.Console.WriteLine("Length of the doubly linked list: " + 
                                 FindLength(head));
    }
}

JavaScript

class Node {
    constructor(val) {
        this.data = val;
        this.prev = null;
        this.next = null;
    }
}

// Function to find the length of
// a doubly linked list
function findLength(head) {
    let count = 0;
    let cur = head;
    while (cur !== null) {
        count++;
        cur = cur.next;
    }
    return count;
}

// Create a doubly linked list with 3 nodes
const head = new Node(1);
const second = new Node(2);
const third = new Node(3);

head.next = second;
second.prev = head;
second.next = third;
third.prev = second;

console.log("Length of the doubly linked list: " +
            findLength(head));

Output

Length of the doubly linked list: 3

Insertion at the Beginning in Doubly Linked List:

Insertion at the Beginning in Doubly Linked List

To insert a new node at the beginning of the doubly list, we can use the following steps:

Allocate memory for a new node and assign the provided value to its data field.
Set the previous pointer of the new node to nullptr.
If the list is empty:
- Set the next pointer of the new node to nullptr.
- Update the head pointer to point to the new node.
If the list is not empty:
- Set the next pointer of the new node to the current head.
- Update the previous pointer of the current head to point to the new node.
- Update the head pointer to point to the new node.

Below are the implementation of the above approach:

C++

#include <iostream>
using namespace std;

// Node structure for the doubly linked list
struct Node {
    int data;
    Node* prev;
    Node* next;

    // Constructor for creating a new node
    Node(int d) : data(d), prev(NULL), next(NULL) {}
};

// Insert a node at the beginning
Node* insertBegin(Node* head, int data) {
    
    // Create a new node
    Node* temp = new Node(data);
    
    // Make next of it as head
    temp->next = head;
    
    // Set previous of head as new node
    if (head != NULL) {
        head->prev = temp;
    }
    
    // Return new node as new head
    return temp;
}

// Print the doubly linked list
void printList(Node* head) {
    Node* curr = head;
    while (curr != NULL) {
        cout << curr->data << endl;
        curr = curr->next;
    }
}

int main() {
  
    // Initialize list with nodes 10, 20, 30
    Node* head = new Node(10);
    Node* temp1 = new Node(20);
    Node* temp2 = new Node(30);
    head->next = temp1;
    temp1->prev = head;
    temp1->next = temp2;
    temp2->prev = temp1;

    // Insert node with data 5 at the beginning
    head = insertBegin(head, 5);

    // Print the list
    printList(head);

    return 0;
}

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

// Node structure for the doubly linked list
struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
};

// Create a new node
struct Node* createNode(int data) {
    struct Node* newNode = 
      (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

// Insert a node at the beginning
struct Node* insertBegin(struct Node* head, int data) {
    
    // Create a new node
    struct Node* temp = createNode(data);
    
    // Make next of it as head
    temp->next = head;
    
    // Set previous of head as new node
    if (head != NULL) {
        head->prev = temp;
    }
    
    // Return new node as new head
    return temp;
}

// Print the doubly linked list
void printList(struct Node* head) {
    struct Node* curr = head;
    while (curr != NULL) {
        printf("%d\n", curr->data);
        curr = curr->next;
    }
}

int main() {
  
    // Initialize list with nodes 10, 20, 30
    struct Node* head = createNode(10);
    struct Node* temp1 = createNode(20);
    struct Node* temp2 = createNode(30);
    head->next = temp1;
    temp1->prev = head;
    temp1->next = temp2;
    temp2->prev = temp1;

    // Insert node with data 5 at the beginning
    head = insertBegin(head, 5);

    // Print the list
    printList(head);

    return 0;
}

Java

class Node {
    int data;
    Node prev, next;

    // Node structure for the doubly linked list
    Node(int d) {
        data = d;
        prev = null;
        next = null;
    }
}

class GfG {
    
    // Insert a node at the beginning
    static Node insertBegin(Node head, int data) {
        
        // Create a new node
        Node temp = new Node(data);
        
        // Make next of it as head
        temp.next = head;
        
        // Set previous of head as new node
        if (head != null) {
            head.prev = temp;
        }
        
        // Return new node as new head
        return temp;
    }

    // Print the doubly linked list
    static void printList(Node head) {
        Node curr = head;
        while (curr != null) {
            System.out.println(curr.data);
            curr = curr.next;
        }
    }

    public static void main(String[] args) {
        
        // Initialize list with nodes 10, 20, 30
        Node head = new Node(10);
        Node temp1 = new Node(20);
        Node temp2 = new Node(30);
        head.next = temp1;
        temp1.prev = head;
        temp1.next = temp2;
        temp2.prev = temp1;

        // Insert node with data 5 at the beginning
        head = insertBegin(head, 5);

        // Print the list
        printList(head);
    }
}

Python

# Node structure for the doubly linked list
class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

# Insert a node at the beginning
def insert_begin(head, data):
    
    # Create a new node
    temp = Node(data)
    
    # Make next of it as head
    temp.next = head
    
    # Set previous of head as new node
    if head is not None:
        head.prev = temp
    
    # Return new node as new head
    return temp

# Print the doubly linked list
def print_list(head):
    curr = head
    while curr is not None:
        print(curr.data)
        curr = curr.next

# Initialize list with nodes 10, 20, 30
head = Node(10)
temp1 = Node(20)
temp2 = Node(30)
head.next = temp1
temp1.prev = head
temp1.next = temp2
temp2.prev = temp1

# Insert node with data 5 at the beginning
head = insert_begin(head, 5)

# Print the list
print_list(head)

using System;

// Node structure for the doubly linked list
class Node {
    public int data;
    public Node prev, next;

    // Constructor for creating a new node
    public Node(int d) {
        data = d;
        prev = null;
        next = null;
    }
}

class GfG {
    
    // Insert a node at the beginning
    public static Node InsertBegin(Node head, int data) {
        
        // Create a new node
        Node temp = new Node(data);
        
        // Make next of it as head
        temp.next = head;
        
        // Set previous of head as new node
        if (head != null) {
            head.prev = temp;
        }
        
        // Return new node as new head
        return temp;
    }

    // Print the doubly linked list
    public static void PrintList(Node head) {
        Node curr = head;
        while (curr != null) {
            Console.WriteLine(curr.data);
            curr = curr.next;
        }
    }

    public static void Main(string[] args) {
        
        // Initialize list with nodes 10, 20, 30
        Node head = new Node(10);
        Node temp1 = new Node(20);
        Node temp2 = new Node(30);
        head.next = temp1;
        temp1.prev = head;
        temp1.next = temp2;
        temp2.prev = temp1;

        // Insert node with data 5 at the beginning
        head = InsertBegin(head, 5);

        // Print the list
        PrintList(head);
    }
}

JavaScript

// Node structure for the doubly linked list
function Node(data) {
    this.data = data;
    this.prev = null;
    this.next = null;
}

// Insert a node at the beginning
function insertBegin(head, data) {
    
    // Create a new node
    const temp = new Node(data);
    
    // Make next of it as head
    temp.next = head;
    
    // Set previous of head as new node
    if (head !== null) {
        head.prev = temp;
    }
    
    // Return new node as new head
    return temp;
}

// Print the doubly linked list
function printList(head) {
    let curr = head;
    while (curr !== null) {
        console.log(curr.data);
        curr = curr.next;
    }
}

// Initialize list with nodes 10, 20, 30
let head = new Node(10);
let temp1 = new Node(20);
let temp2 = new Node(30);
head.next = temp1;
temp1.prev = head;
temp1.next = temp2;
temp2.prev = temp1;

// Insert node with data 5 at the beginning
head = insertBegin(head, 5);

// Print the list
printList(head);

Output

Insertion at the End of Doubly Linked List

Insertion at the End in Doubly Linked List

To insert a new node at the end of the doubly linked list, we can use the following steps:

Allocate memory for a new node and assign the provided value to its data field.
Initialize the next pointer of the new node to nullptr.
If the list is empty:
- Set the previous pointer of the new node to nullptr.
- Update the head pointer to point to the new node.
If the list is not empty:
- Traverse the list starting from the head to reach the last node.
- Adjust pointers to insert the new node at the end:
  - Set the next pointer of the last node to point to the new node.
  - Set the previous pointer of the new node to point to the last node.’

Below are the implementation of the above approach:

C++

#include <bits/stdc++.h> 
using namespace std; 

// Node structure for the doubly linked list
struct Node {
    int data;
    Node* prev;
    Node* next;
    Node(int d) {
        data = d;
        prev = next = nullptr; 
    }
};

// Insert a node at the end
Node* insertEnd(Node* head, int data) {
    
    // Create a new node
    Node* temp = new Node(data);
    
    // If the list is empty, return the new node
    if (head == nullptr) return temp;  
  
    Node* curr = head;
    
    // Traverse to the end of the list
    while (curr->next != nullptr) 
        curr = curr->next;
    
    // Link the new node to the end of the list
    curr->next = temp;
    temp->prev = curr;
    
    // Return the unchanged head
    return head;
}

// Print the doubly linked list
void printList(Node* head) {
    Node* curr = head;
    while (curr != nullptr) {
        cout << curr->data << " ";
        curr = curr->next;
    }
    cout << endl;
}

int main() { 
  
    // Initialize list with nodes 10, 20, 30
    Node* head = new Node(10);
    Node* temp1 = new Node(20);
    Node* temp2 = new Node(30);
    head->next = temp1;
    temp1->prev = head;
    temp1->next = temp2;
    temp2->prev = temp1;

    // Insert node with data 40 at the end
    head = insertEnd(head, 40);

    // Print the list
    printList(head);
    
    return 0;
}

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

// Node structure for the doubly linked list
struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
};

// Create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

// Insert a node at the end
struct Node* insertEnd(struct Node* head, int data) {
    
    // Create a new node
    struct Node* temp = createNode(data);
    
    // If the list is empty, return the new node
    if (head == NULL) return temp;  
  
    struct Node* curr = head;
    
    // Traverse to the end of the list
    while (curr->next != NULL) 
        curr = curr->next;
    
    // Link the new node to the end of the list
    curr->next = temp;
    temp->prev = curr;
    
    // Return the unchanged head
    return head;
}

// Print the doubly linked list
void printList(struct Node* head) {
    struct Node* curr = head;
    while (curr != NULL) {
        printf("%d ", curr->data);
        curr = curr->next;
    }
    printf("\n");
}

int main() { 
  
    // Initialize list with nodes 10, 20, 30
    struct Node* head = createNode(10);
    struct Node* temp1 = createNode(20);
    struct Node* temp2 = createNode(30);
    head->next = temp1;
    temp1->prev = head;
    temp1->next = temp2;
    temp2->prev = temp1;

    // Insert node with data 40 at the end
    head = insertEnd(head, 40);

    // Print the list
    printList(head);
    
    return 0;
}

Java

class Node {
    int data;
    Node prev, next;

    // Constructor for creating a new node
    Node(int d) {
        data = d;
        prev = null;
        next = null;
    }
}

// Insert a node at the end
class GfG {
    
    public static Node insertEnd(Node head, int data) {
        
        // Create a new node
        Node temp = new Node(data);
        
        // If the list is empty, return the new node
        if (head == null) return temp;  
  
        Node curr = head;
        
        // Traverse to the end of the list
        while (curr.next != null) 
            curr = curr.next;
        
        // Link the new node to the end of the list
        curr.next = temp;
        temp.prev = curr;
        
        // Return the unchanged head
        return head;
    }

    // Print the doubly linked list
    static void printList(Node head) {
        Node curr = head;
        while (curr != null) {
            System.out.print(curr.data + " ");
            curr = curr.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        
        // Initialize list with nodes 10, 20, 30
        Node head = new Node(10);
        Node temp1 = new Node(20);
        Node temp2 = new Node(30);
        head.next = temp1;
        temp1.prev = head;
        temp1.next = temp2;
        temp2.prev = temp1;

        // Insert node with data 40 at the end
        head = insertEnd(head, 40);

        // Print the list
        printList(head);
    }
}

Python

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None


# Insert a node at the end
def insert_end(head, data):
    
    # Create a new node
    temp = Node(data)
    
    # If the list is empty, return the new node
    if head is None:
        return temp

    curr = head
    
    # Traverse to the end of the list
    while curr.next is not None:
        curr = curr.next
    
    # Link the new node to the end of the list
    curr.next = temp
    temp.prev = curr
    
    # Return the unchanged head
    return head


# Print the doubly linked list
def print_list(head):
    curr = head
    while curr is not None:
        print(curr.data, end=" ")
        curr = curr.next
    print()


if __name__ == "__main__":
  
    # Initialize list with nodes 10, 20, 30
    head = Node(10)
    temp1 = Node(20)
    temp2 = Node(30)
    head.next = temp1
    temp1.prev = head
    temp1.next = temp2
    temp2.prev = temp1

    # Insert node with data 40 at the end
    head = insert_end(head, 40)

    # Print the list
    print_list(head)

using System;

// Node structure for the doubly linked list
class Node {
    public int Data;
    public Node Prev;
    public Node Next;

    public Node(int data) {
        Data = data;
        Prev = null;
        Next = null;
    }
}

// Class for the doubly linked list operations
class GfG {

    // Insert a node at the end
    public static Node InsertEnd(Node head, int data) {
        
        // Create a new node
        Node temp = new Node(data);
        
        // If the list is empty, return the new node
        if (head == null) return temp;

        Node curr = head;
        
        // Traverse to the end of the list
        while (curr.Next != null) {
            curr = curr.Next;
        }
        
        // Link the new node to the end of the list
        curr.Next = temp;
        temp.Prev = curr;
        
        // Return the unchanged head
        return head;
    }

    // Print the doubly linked list
    public static void PrintList(Node head) {
        Node curr = head;
        while (curr != null) {
            Console.Write(curr.Data + " ");
            curr = curr.Next;
        }
        Console.WriteLine();
    }

    public static void Main() {
        
        // Initialize list with nodes 10, 20, 30
        Node head = new Node(10);
        Node temp1 = new Node(20);
        Node temp2 = new Node(30);
        head.Next = temp1;
        temp1.Prev = head;
        temp1.Next = temp2;
        temp2.Prev = temp1;

        // Insert node with data 40 at the end
        head = InsertEnd(head, 40);

        // Print the list
        PrintList(head);
    }
}

JavaScript

// Node structure for the doubly linked list
function Node(data) {
    this.data = data;
    this.prev = null;
    this.next = null;
}

// Insert a node at the end
function insertEnd(head, data) {
    
    // Create a new node
    const temp = new Node(data);
    
    // If the list is empty, return the new node
    if (head === null) return temp;

    let curr = head;
    
    // Traverse to the end of the list
    while (curr.next !== null) {
        curr = curr.next;
    }
    
    // Link the new node to the end of the list
    curr.next = temp;
    temp.prev = curr;
    
    // Return the unchanged head
    return head;
}

// Print the doubly linked list
function printList(head) {
    let curr = head;
    while (curr !== null) {
        console.log(curr.data);
        curr = curr.next;
    }
}

// Example usage
let head = new Node(10);
let temp1 = new Node(20);
let temp2 = new Node(30);
head.next = temp1;
temp1.prev = head;
temp1.next = temp2;
temp2.prev = temp1;

// Insert node with data 40 at the end
head = insertEnd(head, 40);

// Print the list
printList(head);

Output

10 20 30 40

Insertion at a Specific Position of Doubly Linked List

To insert a node at a specific Position in doubly linked list, we can use the following steps:

Traverse the list to find the node at the desired position.
Create a new node with the data you want to insert.
Adjust the pointers of the new node, the previous node, and the next node to include the new node in the list.
Update the pointers of the neighboring nodes to maintain the doubly linked list structure.

Below is the implementation of the above approach:

C++

#include <iostream>
using namespace std;

// Define the structure of a node in the doubly linked list
struct Node {
    int data;  
    Node* prev;
    Node* next; 
    Node(int d) {
        data = d;
        prev = next = nullptr;
    }
};

// Function to insert a node at a specific position in 
// the doubly linked list
Node* insertPos(Node* head, int pos, int data) {
  
    // Please note we return same head if the given
    // pos is invalid  
    
    // Return same head if the given position is invalid
    if (head == nullptr) 
        return (pos == 0) ? new Node(data) : head;

    if (pos == 0) {
        Node* temp = new Node(data);
        head->prev = temp;
        temp->next = head;
        return temp; // New node becomes the new head
    }

    // Find the node after which we need to insert 
    // the new node
    Node* prev = head; 
    for (int i = 0; i < pos - 1; i++) {
        
        // If position is invalid
        if (prev == nullptr) 
            return head;
        
        prev = prev->next;   
    }

    // Now we need to insert temp after prev
    Node* temp = new Node(data);
  
    // Please remember the ordering of these 
    // operations is important to make sure
    // that we do not break any link
    temp->next = prev->next;
    temp->prev = prev;
    if (prev->next != nullptr)
        prev->next->prev = temp;
    prev->next = temp;

    return head; // Return unchanged head
}

// Function to print the doubly linked list
void printList(Node* head) {
    while (head != nullptr) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

// Driver code to test the insertion function
int main() {
    
    // Create an empty list
    Node* head = nullptr;

    // Insert elements at various positions
    head = insertPos(head, 0, 10);
    head = insertPos(head, 1, 20); 
    head = insertPos(head, 2, 30);
    printList(head); 
    
    // Let us try some more insertions
    head = insertPos(head, 1, 40);
    head = insertPos(head, 2, 50);
    head = insertPos(head, 0, 5);
    printList(head); 
    
    return 0;
}

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

// Define the structure of a node in the doubly 
// linked list
struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
};

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = 
       (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

// Function to insert a node at a specific position 
// in the doubly linked list
struct Node* insertPos(struct Node* head, int pos, int data) {
    
    // Return the same head if the position is invalid
    if (head == NULL) {
        return (pos == 0) ? createNode(data) : head;
    }

    // Inserting at the head (position 0)
    if (pos == 0) {
        struct Node* temp = createNode(data);
        head->prev = temp;
        temp->next = head;
        return temp; // New node becomes the new head
    }

    // Find the node after which we need to 
    // insert the new node
    struct Node* prev = head; 
    for (int i = 0; i < pos - 1; i++) {
        
        // If position is invalid
        if (prev == NULL) {
            return head;
        }
        
        prev = prev->next;   
    }

    // Now we need to insert the new node after prev
    struct Node* temp = createNode(data);
  
    // Ordering of these operations is important 
    // to avoid breaking links
    temp->next = prev->next;
    temp->prev = prev;
    if (prev->next != NULL) {
        prev->next->prev = temp;
    }
    prev->next = temp;

    return head; // Return unchanged head
}

// Function to print the doubly linked list
void printList(struct Node* head) {
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}

// Driver code to test the insertion function
int main() {
    
    // Create an empty list
    struct Node* head = NULL;

    // Insert elements at various positions
    head = insertPos(head, 0, 10);
    head = insertPos(head, 1, 20); 
    head = insertPos(head, 2, 30);
    printList(head); 
    
    // Let us try some more insertions
    head = insertPos(head, 1, 40);
    head = insertPos(head, 2, 50);
    head = insertPos(head, 0, 5);
    printList(head); 
    
    return 0;
}

Java

class Node {
    int data;
    Node prev, next;
    
    // Node structure for the doubly linked list
    Node(int d) {
        data = d;
        prev = next = null;
    }
}

// Function to insert a node at a specific position in 
// the doubly linked list
class GfG {
    static Node insertPos(Node head, int pos, int data) {
        
        // Return same head if the given position is invalid
        if (head == null) 
            return (pos == 0) ? new Node(data) : head;

        if (pos == 0) {
            Node temp = new Node(data);
            head.prev = temp;
            temp.next = head;
            return temp; // New node becomes the new head
        }

        // Find the node after which we need to 
        // insert the new node
        Node prev = head; 
        for (int i = 0; i < pos - 1; i++) {
            
            // If position is invalid
            if (prev == null) 
                return head;
            
            prev = prev.next;   
        }

        // Now we need to insert temp after prev
        Node temp = new Node(data);
        
        // Ordering of these operations is important
        // to ensure we do not break any links
        temp.next = prev.next;
        temp.prev = prev;
        if (prev.next != null)
            prev.next.prev = temp;
        prev.next = temp;

        return head; // Return unchanged head
    }

    // Function to print the doubly linked list
    static void printList(Node head) {
        while (head != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
        System.out.println();
    }

    // Driver code to test the insertion function
    public static void main(String[] args) {
        
        // Create an empty list
        Node head = null;

        // Insert elements at various positions
        head = insertPos(head, 0, 10);
        head = insertPos(head, 1, 20); 
        head = insertPos(head, 2, 30);
        printList(head); 
        
        // Let us try some more insertions
        head = insertPos(head, 1, 40);
        head = insertPos(head, 2, 50);
        head = insertPos(head, 0, 5);
        printList(head); 
    }
}

Python

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

# Function to insert a node at a specific 
# position in the doubly linked list
def insertPos(head, pos, data):
  
    # Return the same head if the given position 
    # is invalid
    if head is None:
        return Node(data) if pos == 0 else head

    if pos == 0:
        temp = Node(data)
        head.prev = temp
        temp.next = head
        return temp  # New node becomes the new head

    # Find the node after which we need to insert 
    # the new node
    prev = head
    for i in range(pos - 1):
        # If position is invalid
        if prev is None:
            return head
        prev = prev.next

    # Now we need to insert temp after prev
    temp = Node(data)

    # Ordering of these operations is important 
    # to ensure we do not break any links
    temp.next = prev.next
    temp.prev = prev
    if prev.next is not None:
        prev.next.prev = temp
    prev.next = temp

    return head  # Return unchanged head

# Function to print the doubly linked list
def printList(head):
    while head is not None:
        print(head.data, end=" ")
        head = head.next
    print()

# Driver code to test the insertion function
if __name__ == "__main__":
  
    # Create an empty list
    head = None

    # Insert elements at various positions
    head = insertPos(head, 0, 10)
    head = insertPos(head, 1, 20) 
    head = insertPos(head, 2, 30)
    printList(head) 
    
    # Let us try some more insertions
    head = insertPos(head, 1, 40)
    head = insertPos(head, 2, 50)
    head = insertPos(head, 0, 5)
    printList(head)

using System;

class Node
{
    public int Data;
    public Node Prev;
    public Node Next;

    public Node(int data)
    {
        Data = data;
        Prev = null;
        Next = null;
    }
}

class GfG
{
    // Function to insert a node at a specific position 
    // in the doubly linked list
    public static Node InsertPos(Node head, int pos, int data)
    {
        // Return the same head if the given position is invalid
        if (head == null)
            return (pos == 0) ? new Node(data) : head;

        Node temp = new Node(data);
        if (pos == 0)
        {           
            head.Prev = temp;
            temp.Next = head;
            return temp; // New node becomes the new head
        }

        // Find the node after which we need to
        // insert the new node
        Node prev = head;
        for (int i = 0; i < pos - 1; i++)
        {
            // If position is invalid
            if (prev == null)
                return head;

            prev = prev.Next;
        }

        // Now we need to insert temp after prev
        // Ordering of these operations is important 
        // to ensure we do not break any links
        temp.Next = prev.Next;
        temp.Prev = prev;
        if (prev.Next != null)
            prev.Next.Prev = temp;
        prev.Next = temp;

        return head; // Return unchanged head
    }

    // Function to print the doubly linked list
    public static void PrintList(Node head)
    {
        while (head != null)
        {
            Console.Write(head.Data + " ");
            head = head.Next;
        }
        Console.WriteLine();
    }

    // Driver code to test the insertion function
    public static void Main()
    {
        // Create an empty list
        Node head = null;

        // Insert elements at various positions
        head = InsertPos(head, 0, 10);
        head = InsertPos(head, 1, 20);
        head = InsertPos(head, 2, 30);
        PrintList(head);

        // Let us try some more insertions
        head = InsertPos(head, 1, 40);
        head = InsertPos(head, 2, 50);
        head = InsertPos(head, 0, 5);
        PrintList(head);
    }
}

JavaScript

class Node {
    constructor(data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

// Function to insert a node at a specific position 
// in the doubly linked list
function insertPos(head, pos, data) {

    // Return the same head if the given position is invalid
    if (head === null) {
        return (pos === 0) ? new Node(data) : head;
    }

    if (pos === 0) {
        const temp = new Node(data);
        head.prev = temp;
        temp.next = head;
        return temp; // New node becomes the new head
    }

    // Find the node after which we need to insert
    // the new node
    let prev = head;
    for (let i = 0; i < pos - 1; i++) {
        // If position is invalid
        if (prev === null) {
            return head;
        }
        prev = prev.next;
    }

    // Now we need to insert temp after prev
    const temp = new Node(data);

    // Ordering of these operations is important
    // to ensure we do not break any links
    temp.next = prev.next;
    temp.prev = prev;
    if (prev.next !== null) {
        prev.next.prev = temp;
    }
    prev.next = temp;

    return head; // Return unchanged head
}

// Function to print the doubly linked list
function printList(head) {
    while (head !== null) {
        console.log(head.data + " ");
        head = head.next;
    }
    console.log();
}

// Driver code to test the insertion function
let head = null;

// Insert elements at various positions
head = insertPos(head, 0, 10);
head = insertPos(head, 1, 20); 
head = insertPos(head, 2, 30);
printList(head); 

// Let us try some more insertions
head = insertPos(head, 1, 40);
head = insertPos(head, 2, 50);
head = insertPos(head, 0, 5);
printList(head);

Output

10 20 30 
5 10 40 50 20 30

Deletion at the Beginning of doubly linked list

Deletion at the Beginning in Doubly Linked List

To delete a node at the beginning in doubly linked list, we can use the following steps:

Check If the list is empty, there is nothing to delete. Return.
Check if the node to be deleted is the head node, update the head pointer to point to the next node.
If the node to be deleted is not the head node, update the previous pointer of the next node to point to the previous node of the node to be deleted.
If the node to be deleted is not the tail node, update the next pointer of the previous node to point to the next node of the node to be deleted.
Free the memory allocated to the node to be deleted.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h> 
using namespace std; 

struct Node {
    int data;
    Node* prev;
    Node* next;
    Node(int d) : data(d), prev(nullptr), next(nullptr) {}
};

// Deletes the first node (head) of the list
// and returns the second node as new head
Node* delHead(Node* head) {
  
    // If empty
    if (!head) return nullptr;
   
    // Store in temp for deletion later
    Node* temp = head;
  
    // Move head
    head = head->next;
  
    // Set prev of the new head 
    if (head) head->prev = nullptr;
  
    // Free memory and return new head
    delete temp;
    return head;
}

void printList(Node* head) {
    for (Node* curr = head; curr != nullptr; curr = curr->next) 
        cout << curr->data << " ";
    cout << endl;
}

int main() { 
    Node* head = new Node(10);
    head->next = new Node(20);
    head->next->prev = head;
    head->next->next = new Node(30);
    head->next->next->prev = head->next;

    head = delHead(head);
    printList(head);
    
    return 0;
}

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

// Define the structure of a node in the doubly linked list
struct Node {
    int data;              
    struct Node* prev;     
    struct Node* next;     
};

// Function to delete the head node of the doubly linked list
struct Node* delHead(struct Node* head) {
  
    // If the list is empty
    if (head == NULL) return NULL;

    // Store the head in a temporary variable
    struct Node* temp = head;

    // Move the head pointer to the next node
    head = head->next;

    // Set the previous pointer of the new head to NULL
    if (head != NULL) head->prev = NULL;

    // Free the memory of the old head node
    free(temp);
    return head; // Return the new head
}

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = 
      (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;    
    newNode->prev = NULL;   
    newNode->next = NULL;  
    return newNode;
}

// Function to print the doubly linked list
void printList(struct Node* head) {
    struct Node* curr = head;
    while (curr != NULL) {
        printf("%d ", curr->data); 
        curr = curr->next;         
    }
    printf("\n"); 
}

// Main function to test the implementation
int main() {
    struct Node* head = createNode(10);
    head->next = createNode(20);
    head->next->prev = head;
    head->next->next = createNode(30);
    head->next->next->prev = head->next;

    head = delHead(head);
  
    printList(head);
    
    return 0;
}

Java

class Node {
    int data;         
    Node prev;     
    Node next;   
    Node(int d) {
        data = d;    
        prev = null; 
        next = null; 
    }
}

class GfG {
    
    // Deletes the first node (head) of the list
    // and returns the second node as new head
    public static Node delHead(Node head) {
      
        // If the list is empty
        if (head == null) return null;

        // Move head to the next node
        head = head.next;

        // Set the previous reference of the 
        // new head to null
        if (head != null) head.prev = null;

        return head; // Return the new head
    }

    // Driver code to test the implementation
    public static void main(String[] args) {

        Node head = new Node(10);
        head.next = new Node(20);
        head.next.prev = head;
        head.next.next = new Node(30);
        head.next.next.prev = head.next;

        // Delete the head node
        head = delHead(head);
        
        // Print the remaining list
        printList(head);
    }
  
    // Function to print the doubly linked list
    public static void printList(Node head) {
        Node curr = head;
        while (curr != null) {
            System.out.print(curr.data + " "); 
            curr = curr.next;                 
        }
        System.out.println();
    }

}

Python

class Node:
    def __init__(self, d):
        self.data = d      
        self.prev = None   
        self.next = None   

# Function to delete the first node (head) of
# the list and return the second node as new head
def del_head(head):
  
    # If the list is empty
    if head is None:
        return None

    # Move head to the next node
    head = head.next

    # Set the previous reference of the new
    # head to None
    if head is not None:
        head.prev = None

    return head  # Return the new head

# Function to print the doubly linked list
def print_list(head):
    curr = head
    while curr is not None:
        print(curr.data, end=" ")  
        curr = curr.next            
    print()

# Driver code to test the implementation
if __name__ == "__main__":
    head = Node(10)                 
    head.next = Node(20)            
    head.next.prev = head             
    head.next.next = Node(30)         
    head.next.next.prev = head.next 

    head = del_head(head)
    
    print_list(head)

using System;

class Node {
    public int Data;
    public Node Prev;
    public Node Next;

    public Node(int d) {
        Data = d;         
        Prev = null;      
        Next = null;      
    }
}

class GfG {
  
    // Deletes the first node (head) of the list
    // and returns the second node as new head
    public static Node DelHead(Node head) {
      
        // If the list is empty
        if (head == null) return null;

        // Move head to the next node
        head = head.Next;

        // Set the previous reference of the 
        // new head to null
        if (head != null) head.Prev = null;

        return head; // Return the new head
    }

    public static void PrintList(Node head) {
        Node curr = head;
        while (curr != null) {
            Console.Write(curr.Data + " ");
            curr = curr.Next;                
        }
        Console.WriteLine();
    }

    public static void Main(string[] args) {
        Node head = new Node(10);
        head.Next = new Node(20);
        head.Next.Prev = head;
        head.Next.Next = new Node(30);
        head.Next.Next.Prev = head.Next;

        head = DelHead(head);
        PrintList(head);
    }
}

JavaScript

class Node {
    constructor(data)
    {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

// Deletes the first node (head) of the list
// and returns the second node as new head
function delHead(head)
{

    // If the list is empty
    if (head == null)
        return null;

    // Move head to the next node
    head = head.next;

    // Set the previous reference of the
    // new head to null
    if (head != null)
        head.prev = null;

    return head; // Return the new head
}

// Function to print the doubly linked list
function printList(head)
{
    let curr = head;
    while (curr !== null) {
        console.log(curr.data + " ");
        curr = curr.next;
    }
    console.log();
}

// Driver code to test the implementation
let head = new Node(10);
head.next = new Node(20);
head.next.prev = head;
head.next.next = new Node(30);
head.next.next.prev = head.next;

head = delHead(head);
printList(head);

Output

20 30

Deletion at the End on doubly linked list:

Deletion at a End in Doubly Linked List

To delete a node at the end in doubly linked list, we can use the following steps:

Check if the doubly linked list is empty. If it is empty, then there is nothing to delete.
If the list is not empty, then move to the last node of the doubly linked list.
Update the second-to-last node’s next pointer to NULL, making it the new last node.
Free the memory allocated for the node that was deleted.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h> 
using namespace std; 

struct Node {
    int data;
    Node* prev;
    Node* next;
    Node(int d) {
        data = d;
        prev = NULL;
        next = NULL;
    }
};

// Function to delete the last node of the doubly 
// linked list
Node *delLast(Node *head) {
  
    // Corner cases
    if (head == NULL) 
        return NULL;
    if (head->next == NULL) {
        delete head;
        return NULL;
    }

    // Traverse to the last node
    Node *curr = head;
    while (curr->next != NULL) 
        curr = curr->next;

    // Update the previous node's next pointer
    curr->prev->next = NULL;
  
    delete curr; // Delete the last node

    // Return the updated head
    return head; 
}

// Function to print the doubly linked list
void printlist(Node *head) {
    Node *curr = head;
    while (curr != NULL) {
        cout << curr->data << " ";
        curr = curr->next;
    }
    cout << endl;
}

int main() { 
    Node *head = new Node(10);
    Node *temp1 = new Node(20);
    Node *temp2 = new Node(30);
    head->next = temp1;
    temp1->prev = head;
    temp1->next = temp2;
    temp2->prev = temp1;
  
    head = delLast(head);

    printlist(head); 

    return 0;
}

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

// Define the Node structure
struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
};

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = 
      (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

// Function to print the doubly linked list
void printList(struct Node* head) {
    struct Node* curr = head;
    while (curr != NULL) {
        printf("%d ", curr->data);
        curr = curr->next;
    }
    printf("\n");
}

// Function to delete the last node of the 
// doubly linked list
struct Node* delLast(struct Node* head) {
  
    // If the list is empty
    if (head == NULL)
        return NULL;

    // If there is only one node in the list
    if (head->next == NULL) {
        free(head);
        return NULL;
    }

    // Traverse to the last node
    struct Node* curr = head;
    while (curr->next != NULL)
        curr = curr->next;

    // Update the previous node's next pointer
    curr->prev->next = NULL;
    free(curr); // Delete the last node

    // Return the updated head
    return head;
}

int main() {
    struct Node* head = createNode(10);
    struct Node* temp1 = createNode(20);
    struct Node* temp2 = createNode(30);
    head->next = temp1;
    temp1->prev = head;
    temp1->next = temp2;
    temp2->prev = temp1;
  
    head = delLast(head);

    printList(head);

    return 0;
}

Java

class Node {
    int data;
    Node prev;
    Node next;

    // Constructor to initialize a new node
    Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

class GfG {


    // Function to delete the last node of the 
    // doubly linked list
    static Node delLast(Node head) {
      
        // If the list is empty
        if (head == null) 
            return null;

        // If there is only one node in the list
        if (head.next == null) {
            return null;
        }

        // Traverse to the last node
        Node curr = head;
        while (curr.next != null)
            curr = curr.next;

        // Update the previous node's next pointer
        curr.prev.next = null;

        // Return the updated head
        return head;
    }  
  
    // Function to print the doubly linked list
    static void printList(Node head) {
        Node curr = head;
        while (curr != null) {
            System.out.print(curr.data + " ");
            curr = curr.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node head = new Node(10);
        Node temp1 = new Node(20);
        Node temp2 = new Node(30);
        head.next = temp1;
        temp1.prev = head;
        temp1.next = temp2;
        temp2.prev = temp1;
      
        head = delLast(head);
        printList(head);
    }
}

Python

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

def del_last(head):
  
    # If the list is empty
    if head is None:
        return None

    # If there is only one node in the list
    if head.next is None:
        return None

    # Traverse to the last node
    curr = head
    while curr.next is not None:
        curr = curr.next

    # Update the previous node's next pointer
    curr.prev.next = None

    # Return the updated head
    return head

def print_list(head):
    curr = head
    while curr is not None:
        print(curr.data, end=" ")
        curr = curr.next
    print()  
  
# Create a doubly linked list
head = Node(10)
temp1 = Node(20)
temp2 = Node(30)
head.next = temp1
temp1.prev = head
temp1.next = temp2
temp2.prev = temp1

head = del_last(head)

print_list(head)

using System;

class Node {
    public int data;
    public Node prev;
    public Node next;

    // Constructor to initialize a new node
    public Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

class GfG {

    // Function to print the doubly linked list
    static void PrintList(Node head) {
        Node curr = head;
        while (curr != null) {
            Console.Write(curr.data + " ");
            curr = curr.next;
        }
        Console.WriteLine();
    }

    // Function to delete the last node of 
    // the doubly linked list
    static Node DelLast(Node head) {
        // If the list is empty
        if (head == null)
            return null;

        // If there is only one node in the list
        if (head.next == null) {
            return null;
        }

        // Traverse to the last node
        Node curr = head;
        while (curr.next != null)
            curr = curr.next;

        // Update the previous node's next pointer
        curr.prev.next = null;

        // Return the updated head
        return head;
    }

    public static void Main(string[] args) {
        Node head = new Node(10);
        Node temp1 = new Node(20);
        Node temp2 = new Node(30);
        head.next = temp1;
        temp1.prev = head;
        temp1.next = temp2;
        temp2.prev = temp1;

        head = DelLast(head);

        PrintList(head);
    }
}

JavaScript

class Node {
    constructor(data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

function delLast(head) {

    // If the list is empty
    if (head === null) 
        return null;

    // If there is only one node in the list
    if (head.next === null) {
        return null;
    }

    // Traverse to the last node
    let curr = head;
    while (curr.next !== null)
        curr = curr.next;

    // Update the previous node's next pointer
    curr.prev.next = null;

    // Return the updated head
    return head;
}

function printList(head) {
    // Function to print the doubly linked list
    let curr = head;
    while (curr !== null) {
        console.log(curr.data + " ");
        curr = curr.next;
    }
    console.log();
}


// Create a doubly linked list
let head = new Node(10);
let temp1 = new Node(20);
let temp2 = new Node(30);
head.next = temp1;
temp1.prev = head;
temp1.next = temp2;
temp2.prev = temp1;

head = delLast(head);

printList(head);

Output

10 20

Deletion at a Specific Position in doubly linked list

Deletion at a Specific Position in Doubly Linked List

To delete a node at a specific position in doubly linked list, we can use the following steps:

Traverse to the node at the specified position in the doubly linked list.
Adjust the pointers to skip the node to be deleted.
Update the next pointer of the node before the deleted node to point to the node after the deleted node.
Update the previous pointer of the node after the deleted node to point to the node before the deleted node.
Free the memory allocated for the deleted node.

Below is the implementation of the above approach:

C++

#include <iostream>

struct Node {
    int data;
    Node* prev;
    Node* next;    
    Node(int d) {
      data = d;
      prev = next = NULL;
    }
};

// Function to delete a node at a specific position
// in the doubly linked list
Node* delPos(Node* head, int pos) {
  
    // If the list is empty
    if (!head) {
        return head;
    }

    Node* curr = head;

    // Traverse to the node at the given position
    for (int i = 1; curr && i < pos; ++i) {
        curr = curr->next;
    }

    // If the position is out of range
    if (!curr) {
        return head;
    }

    // Update the previous node's next pointer
    if (curr->prev) {
        curr->prev->next = curr->next;
    }

    // Update the next node's prev pointer
    if (curr->next) {
        curr->next->prev = curr->prev;
    }

    // If the node to be deleted is the head node
    if (head == curr) {
        head = curr->next;
    }

    // Deallocate memory for the deleted node
    delete curr; 
    return head;
}

// Function to print the doubly linked list
void printList(Node* head) {
    Node* curr = head;
    while (curr != nullptr) {
        std::cout << curr->data << " ";
        curr = curr->next;
    }
    std::cout << std::endl;
}

int main() {
    // Create the doubly linked list
    Node* head = new Node(10);
    Node* temp1 = new Node(20);
    Node* temp2 = new Node(30);
    Node* temp3 = new Node(40);

    // Link the nodes together
    head->next = temp1;
    temp1->prev = head;
    temp1->next = temp2;
    temp2->prev = temp1;
    temp2->next = temp3;
    temp3->prev = temp2;

    head = delPos(head, 0);
  
    printList(head);

    return 0;
}

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

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

// Function to delete a node at a specific position
// in the doubly linked list
struct Node* delPos(struct Node* head, int pos) {
  
    if (!head) {
        return head;
    }

    struct Node* curr = head;

    // Traverse to the node at the given position
    for (int i = 1; curr && i < pos; ++i) {
        curr = curr->next;
    }

    // If the position is out of range
    if (!curr) {
        return head;
    }

    // Update the previous node's next pointer
    if (curr->prev) {
        curr->prev->next = curr->next;
    }

    // Update the next node's prev pointer
    if (curr->next) {
        curr->next->prev = curr->prev;
    }

    // If the node to be deleted is the head node
    if (head == curr) {
        head = curr->next;
    }

    // Deallocate memory for the deleted node
    free(curr); 
    return head;
}

struct Node* createNode(int data) {
    struct Node* newNode = 
      (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

// Function to print the doubly linked list
void printList(struct Node* head) {
    struct Node* curr = head;
    while (curr != NULL) {
        printf("%d ", curr->data);
        curr = curr->next;
    }
    printf("\n");
}

int main() {
    // Create the doubly linked list
    struct Node* head = createNode(10);
    struct Node* temp1 = createNode(20);
    struct Node* temp2 = createNode(30);
    struct Node* temp3 = createNode(40);

    // Link the nodes together
    head->next = temp1;
    temp1->prev = head;
    temp1->next = temp2;
    temp2->prev = temp1;
    temp2->next = temp3;
    temp3->prev = temp2;

    // Delete node at position 0 (head node)
    head = delPos(head, 0);

    // Print the list after deletion
    printList(head);

    return 0;
}

Java

class Node {
    int data;
    Node prev;
    Node next;
    Node(int data)
    {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

// Function to delete a node at a specific 
// position in the doubly linked list
class GfG {
    static Node delPos(Node head, int pos)
    {
        // If the list is empty
        if (head == null) {
            return head;
        }

        Node curr = head;

        // Traverse to the node at the given position
        for (int i = 1; curr != null && i < pos; ++i) {
            curr = curr.next;
        }

        // If the position is out of range
        if (curr == null) {
            return head;
        }

        // Update the previous node's next pointer
        if (curr.prev != null) {
            curr.prev.next = curr.next;
        }

        // Update the next node's prev pointer
        if (curr.next != null) {
            curr.next.prev = curr.prev;
        }

        // If the node to be deleted is the head node
        if (head == curr) {
            head = curr.next;
        }

        // Deallocate memory for the deleted node (Java
        // handles garbage collection)
        curr = null;

        return head;
    }

    public static void main(String[] args)
    {
        Node head = new Node(10);
        Node temp1 = new Node(20);
        Node temp2 = new Node(30);
        Node temp3 = new Node(40);
        head.next = temp1;
        temp1.prev = head;
        temp1.next = temp2;
        temp2.prev = temp1;
        temp2.next = temp3;
        temp3.prev = temp2;

        // Delete the node at position 0
        head = delPos(head, 0);

        // Print the remaining list
        printList(head);
    }
    static void printList(Node head)
    {
        Node curr = head;
        while (curr != null) {
            System.out.print(curr.data + " ");
            curr = curr.next;
        }
        System.out.println();
    }
}

Python

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

def del_pos(head, pos):
  
    # If the list is empty
    if head is None:
        return head

    curr = head

    # Traverse to the node at the given position
    for i in range(1, pos):
        if curr is None:
            break
        curr = curr.next

    # If the position is out of range
    if curr is None:
        return head

    # Update the previous node's next pointer
    if curr.prev is not None:
        curr.prev.next = curr.next

    # Update the next node's prev pointer
    if curr.next is not None:
        curr.next.prev = curr.prev

    # If the node to be deleted is the head node
    if head == curr:
        head = curr.next

    # Deallocate memory for the deleted node 
    # (Python handles garbage collection)
    curr = None

    return head

def print_list(head):
    curr = head
    while curr is not None:
        print(curr.data, end=" ")
        curr = curr.next
    print()

if __name__ == "__main__":
    head = Node(10)
    temp1 = Node(20)
    temp2 = Node(30)
    temp3 = Node(40)
    head.next = temp1
    temp1.prev = head
    temp1.next = temp2
    temp2.prev = temp1
    temp2.next = temp3
    temp3.prev = temp2

    head = del_pos(head, 0)

    print_list(head)

using System;

class Node {
    public int data;
    public Node prev;
    public Node next;

    public Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

class GfG {
  
    // Function to delete a node at a specific
    // position in the doubly linked list
    public static Node delPos(Node head, int pos) {
      
        // If the list is empty or position is invalid
        if (head == null || pos < 1) {
            return head;
        }

        Node curr = head;

        // Traverse to the node at the given position
        for (int i = 1; curr != null && i < pos; ++i) {
            curr = curr.next;
        }

        // If the position is out of range
        if (curr == null) {
            return head;
        }

        // Update the previous node's next pointer
        if (curr.prev != null) {
            curr.prev.next = curr.next;
        }

        // Update the next node's prev pointer
        if (curr.next != null) {
            curr.next.prev = curr.prev;
        }

        // If the node to be deleted is the head node
        if (head == curr) {
            head = curr.next;
        }

        // Deallocate memory for the deleted node 
        // (C# has garbage collection)
        curr = null;

        return head;
    }

    // Function to print the doubly linked list
    public static void PrintList(Node head) {
        Node curr = head;
        while (curr != null) {
            Console.Write(curr.data + " ");
            curr = curr.next;
        }
        Console.WriteLine();
    }

    // Example usage:
    public static void Main(string[] args) {
        Node head = new Node(10);
        Node temp1 = new Node(20);
        Node temp2 = new Node(30);
        Node temp3 = new Node(40);
        head.next = temp1;
        temp1.prev = head;
        temp1.next = temp2;
        temp2.prev = temp1;
        temp2.next = temp3;
        temp3.prev = temp2;

        head = delPos(head, 2);

        PrintList(head);
    }
}

JavaScript

class Node {
    constructor(data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

// Function to delete a node at a specific 
// position in the doubly linked list
function delPos(head, pos) {
    // If the list is empty
    if (head === null) {
        return head;
    }

    let curr = head;

    // Traverse to the node at the given position
    for (let i = 1; curr !== null && i < pos; ++i) {
        curr = curr.next;
    }

    // If the position is out of range
    if (curr === null) {
        return head;
    }

    // Update the previous node's next pointer
    if (curr.prev !== null) {
        curr.prev.next = curr.next;
    }

    // Update the next node's prev pointer
    if (curr.next !== null) {
        curr.next.prev = curr.prev;
    }

    // If the node to be deleted is the head node
    if (head === curr) {
        head = curr.next;
    }

    // Deallocate memory for the deleted
    // node (JavaScript handles garbage collection)
    curr = null;

    return head;
}

// Function to print the doubly linked list
function printList(head) {
    let curr = head;
    while (curr !== null) {
        console.log(curr.data + " ");
        curr = curr.next;
    }
    console.log();
}

// Example usage:
let head = new Node(10);
let temp1 = new Node(20);
let temp2 = new Node(30);
let temp3 = new Node(40);
head.next = temp1;
temp1.prev = head;
temp1.next = temp2;
temp2.prev = temp1;
temp2.next = temp3;
temp3.prev = temp2;

head = delPos(head, 0);

printList(head);

Output

20 30 40

Advantages of Doubly Linked List

Efficient traversal in both directions: Doubly linked lists allow for efficient traversal of the list in both directions, making it suitable for applications where frequent insertions and deletions are required.
Easy insertion and deletion of nodes: The presence of pointers to both the previous and next nodes makes it easy to insert or delete nodes from the list, without having to traverse the entire list.
Can be used to implement a stack or queue: Doubly linked lists can be used to implement both stacks and queues, which are common data structures used in programming.

Disadvantages of Doubly Linked List

More complex than singly linked lists: Doubly linked lists are more complex than singly linked lists, as they require additional pointers for each node.
More memory overhead: Doubly linked lists require more memory overhead than singly linked lists, as each node stores two pointers instead of one.

Applications of doubly linked lists:

Implementation of undo and redo functionality in text editors.
Cache implementation where quick insertion and deletion of elements are required.
Browser history management to navigate back and forth between visited pages.
Music player applications to manage playlists and navigate through songs efficiently.
Implementing data structures like Deque (double-ended queue) for efficient insertion and deletion at both ends.

Practice Questions on Doubly Linked List
MCQs on Linked List

Elevate your coding journey with a Premium subscription. Benefit from ad-free learning, unlimited article summaries, an AI bot, access to 35+ courses, and more-available only with GeeksforGeeks Premium! Explore now!

Reffered: https://www.geeksforgeeks.org

Data Structures

Related
Singly Linked List Tutorial
Quiz on Data Structures \| DSA MCQs
Inbuild Data Structures in Java
Introduction to Built-in Data Structures in C#
Cloning of Data Structures

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	15