Understanding Doubly Linked List: A Comprehensive Guide

C Implementation

struct node {
    struct node *prev; // Pointer to the previous node
    int data;          // Data part of the node
    struct node *next; // Pointer to the next node
};

Explanation

• struct node *prev: This pointer stores the address of the previous node in the list or NULL for the first node.
• int data: Stores the actual data value of the node.
• struct node *next: This pointer stores the address of the next node in the list or NULL for the last node.

C++ Implementation

struct Node {
    Node* prev; // Pointer to the previous node
    int data;   // Data part of the node
    Node* next; // Pointer to the next node

    // Constructor to initialize a new node
    Node(int value) : prev(nullptr), data(value), next(nullptr) {}
};

Explanation

• Node* prev: A pointer to the previous node.
• int data: Stores the value of the node.
• Node* next: A pointer to the next node.
• Constructor: Node(int value) initializes a new node with data set to value, and both pointers (prev and next) set to nullptr (equivalent to NULL).

C# Implementation

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

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

Explanation

• Node Prev: A reference to the previous node in the list.
• int Data: Stores the node’s data value.
• Node Next: A reference to the next node in the list.
• Constructor: Initializes a node with data and sets both pointers to null.

Java Implementation

class Node {
    Node prev; // Pointer to the previous node
    int data;  // Data part of the node
    Node next; // Pointer to the next node

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

Explanation

• Node prev: A reference to the previous node.
• int data: Stores the value of the node.
• Node next: A reference to the next node.
• Constructor: Initializes a node with data and sets the references prev and next to null.

JavaScript Implementation

class Node {
    constructor(data) {
        this.prev = null; // Pointer to the previous node
        this.data = data; // Data part of the node
        this.next = null; // Pointer to the next node
    }
}

Explanation:

• this.prev: Holds the reference to the previous node or null if it’s the first node.
• this.data: Stores the value of the node.
• this.next: Holds the reference to the next node or null if it’s the last node.
• Constructor: Creates a new node with data and initializes the references prev and next to null.

Python Implementation

class Node:
    def __init__(self, data):
        self.prev = None  # Pointer to the previous node
        self.data = data  # Data part of the node
        self.next = None  # Pointer to the next node

Explanation

• self.next: Points to the next node, initialized to None.
• __init__ Method: Initializes the node with data and sets both pointers to None.
• self.prev: Points to the previous node, initialized to None.
• self.data: Stores the value of the node.

Node Creation in C

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

struct node {
    struct node *prev; // Pointer to the previous node
    int data;          // Data part of the node
    struct node *next; // Pointer to the next node
};

struct node *head = NULL; // Pointer to the head of the doubly linked list

Explanation:

• struct node: Defines the structure of a node in a doubly linked list, containing:
  • prev: A pointer to the previous node.
  • data: Stores the value of the node.
  • next: A pointer to the next node.
• struct node *head: Initializes the head pointer to NULL, indicating an empty list.

Node Creation in C++

#include <iostream>
using namespace std;

struct Node {
    Node* prev; // Pointer to the previous node
    int data;   // Data part of the node
    Node* next; // Pointer to the next node

    // Constructor to initialize a new node
    Node(int value) : prev(nullptr), data(value), next(nullptr) {}
};

Node* head = nullptr; // Pointer to the head of the doubly linked list

Explanation:

• Node* prev: A pointer to the previous node.
• int data: Stores the value of the node.
• Node* next: A pointer to the next node.
• Constructor: Node(int value) initializes a new node with:
  • prev set to nullptr.
  • data set to value.
  • next set to nullptr.
• Node* head: The head pointer is initialized to nullptr, representing an empty list.

Node Creation in C#

using System;

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

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

Node head = null; // Pointer to the head of the doubly linked list

Explanation:

• Node Prev: A reference to the previous node in the list.
• int Data: Holds the data of the node.
• Node Next: A reference to the next node.
• Constructor: The constructor initializes:
  • Prev to null.
  • mData with the given value.
  • Next to null.
• Node head: The head pointer starts as null, indicating an empty list.

Node Creation in Java

class Node {
    Node prev; // Pointer to the previous node
    int data;  // Data part of the node
    Node next; // Pointer to the next node

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

Node head = null; // Pointer to the head of the doubly linked list

Explanation:

• Node prev: A reference to the previous node.
• int data: Stores the node’s data.
• Node next: A reference to the next node.
• Constructor: Initializes:
  • prev to null.
  • data with the given value.
  • next to null.
• Node head: The head pointer is set to null, representing an empty list.

Node Creation in JavaScript

class Node {
    constructor(data) {
        this.prev = null; // Pointer to the previous node
        this.data = data; // Data part of the node
        this.next = null; // Pointer to the next node
    }
}

let head = null; // Pointer to the head of the doubly linked list

Explanation:

• this.prev: A reference to the previous node or null for the first node.
• this.data: Stores the data value of the node.
• this.next: A reference to the next node or null for the last node.
• Constructor: Initializes the node with prev, data, and next.
• let head: The head pointer is initialized to null, indicating an empty list.

Node Creation in Python

class Node:
    def __init__(self, data):
        self.prev = None  # Pointer to the previous node
        self.data = data  # Data part of the node
        self.next = None  # Pointer to the next node

head = None  # Pointer to the head of the doubly linked list

Explanation:

• self.prev: Points to the previous node, initialized to None.
• self.data: Stores the value of the node.
• self.next: Points to the next node, initialized to None.
• __init__ Method: Initializes a new node with:
  • prev set to None.
  • data assigned the given value.
  • next set to None.
• head: The head pointer is set to None, indicating the list is empty.

C Implementation

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

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

struct node* head = NULL; // Global head pointer

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

// Insert at the beginning
void insertAtBeginning(int data) {
    struct node* newNode = createNode(data);
    if (head != NULL) {
        newNode->next = head;
        head->prev = newNode;
    }
    head = newNode;
    printf("Inserted %d at the beginning.\n", data);
}

// Insert at the end
void insertAtEnd(int data) {
    struct node* newNode = createNode(data);
    if (head == NULL) {
        head = newNode;
        printf("Inserted %d at the end.\n", data);
        return;
    }
    struct node* temp = head;
    while (temp->next != NULL)
        temp = temp->next;
    temp->next = newNode;
    newNode->prev = temp;
    printf("Inserted %d at the end.\n", data);
}

// Delete at the beginning
void deleteAtBeginning() {
    if (head == NULL) {
        printf("List is empty.\n");
        return;
    }
    struct node* temp = head;
    head = head->next;
    if (head != NULL)
        head->prev = NULL;
    free(temp);
    printf("Deleted node from the beginning.\n");
}

// Delete at the end
void deleteAtEnd() {
    if (head == NULL) {
        printf("List is empty.\n");
        return;
    }
    struct node* temp = head;
    if (head->next == NULL) {
        head = NULL;
        free(temp);
        printf("Deleted node from the end.\n");
        return;
    }
    while (temp->next != NULL)
        temp = temp->next;
    temp->prev->next = NULL;
    free(temp);
    printf("Deleted node from the end.\n");
}

// Display the list
void displayList() {
    if (head == NULL) {
        printf("List is empty.\n");
        return;
    }
    struct node* temp = head;
    printf("Doubly Linked List: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

// Menu-driven program
int main() {
    int choice, data;
    while (1) {
        printf("\nMenu:\n");
        printf("1. Insert at Beginning\n");
        printf("2. Insert at End\n");
        printf("3. Delete at Beginning\n");
        printf("4. Delete at End\n");
        printf("5. Display List\n");
        printf("6. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                printf("Enter data to insert: ");
                scanf("%d", &data);
                insertAtBeginning(data);
                break;
            case 2:
                printf("Enter data to insert: ");
                scanf("%d", &data);
                insertAtEnd(data);
                break;
            case 3:
                deleteAtBeginning();
                break;
            case 4:
                deleteAtEnd();
                break;
            case 5:
                displayList();
                break;
            case 6:
                printf("Exiting program.\n");
                exit(0);
            default:
                printf("Invalid choice! Please try again.\n");
        }
    }
    return 0;
}

Steps of the Program

• Node Structure: Defines a doubly linked list node with prev, data, and next pointers.
• Create Node: Dynamically allocates memory for a new node.
• Insertion Operations: Implements insertion at the beginning and at the end of the list.
• Deletion Operations: Implements deletion at the beginning and at the end of the list.
• Traversal: Displays the current elements in the doubly linked list.
• Menu-Driven Interaction: Provides options for the user to choose operations.

Example Output

Menu:
1. Insert at Beginning
2. Insert at End
3. Delete at Beginning
4. Delete at End
5. Display List
6. Exit
Enter your choice: 1
Enter data to insert: 10
Inserted 10 at the beginning.

Menu:
Enter your choice: 2
Enter data to insert: 20
Inserted 20 at the end.

Menu:
Enter your choice: 5
Doubly Linked List: 10 20

C++ Implementation

#include <iostream>
using namespace std;

struct Node {
    Node* prev; // Pointer to the previous node
    int data;   // Data part of the node
    Node* next; // Pointer to the next node

    // Constructor to initialize a node
    Node(int value) : prev(nullptr), data(value), next(nullptr) {}
};

Node* head = nullptr; // Global head pointer

// Insert at the beginning
void insertAtBeginning(int data) {
    Node* newNode = new Node(data);
    if (head != nullptr) {
        newNode->next = head;
        head->prev = newNode;
    }
    head = newNode;
    cout << "Inserted " << data << " at the beginning." << endl;
}

// Insert at the end
void insertAtEnd(int data) {
    Node* newNode = new Node(data);
    if (head == nullptr) {
        head = newNode;
        cout << "Inserted " << data << " at the end." << endl;
        return;
    }
    Node* temp = head;
    while (temp->next != nullptr)
        temp = temp->next;
    temp->next = newNode;
    newNode->prev = temp;
    cout << "Inserted " << data << " at the end." << endl;
}

// Delete at the beginning
void deleteAtBeginning() {
    if (head == nullptr) {
        cout << "List is empty." << endl;
        return;
    }
    Node* temp = head;
    head = head->next;
    if (head != nullptr)
        head->prev = nullptr;
    delete temp;
    cout << "Deleted node from the beginning." << endl;
}

// Delete at the end
void deleteAtEnd() {
    if (head == nullptr) {
        cout << "List is empty." << endl;
        return;
    }
    Node* temp = head;
    if (head->next == nullptr) {
        head = nullptr;
        delete temp;
        cout << "Deleted node from the end." << endl;
        return;
    }
    while (temp->next != nullptr)
        temp = temp->next;
    temp->prev->next = nullptr;
    delete temp;
    cout << "Deleted node from the end." << endl;
}

// Display the list
void displayList() {
    if (head == nullptr) {
        cout << "List is empty." << endl;
        return;
    }
    Node* temp = head;
    cout << "Doubly Linked List: ";
    while (temp != nullptr) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

// Menu-driven program
int main() {
    int choice, data;
    while (true) {
        cout << "\nMenu:\n";
        cout << "1. Insert at Beginning\n";
        cout << "2. Insert at End\n";
        cout << "3. Delete at Beginning\n";
        cout << "4. Delete at End\n";
        cout << "5. Display List\n";
        cout << "6. Exit\n";
        cout << "Enter your choice: ";
        cin >> choice;

        switch (choice) {
            case 1:
                cout << "Enter data to insert: ";
                cin >> data;
                insertAtBeginning(data);
                break;
            case 2:
                cout << "Enter data to insert: ";
                cin >> data;
                insertAtEnd(data);
                break;
            case 3:
                deleteAtBeginning();
                break;
            case 4:
                deleteAtEnd();
                break;
            case 5:
                displayList();
                break;
            case 6:
                cout << "Exiting program." << endl;
                return 0;
            default:
                cout << "Invalid choice! Please try again." << endl;
        }
    }
}

Steps of the Program

• Node Structure:
  • The Node struct contains:
  • prev: Pointer to the previous node.
  • data: Value stored in the node.
  • next: Pointer to the next node.
• Insertion and Deletion:
  • Insertions and deletions are handled at both the beginning and the end of the doubly linked list.
• Traversal:
  • The list is traversed to display all elements.
• Menu Interaction:
  • A loop-based menu system allows dynamic interaction with the doubly linked list.

Example Output

Menu:
1. Insert at Beginning
2. Insert at End
3. Delete at Beginning
4. Delete at End
5. Display List
6. Exit
Enter your choice: 1
Enter data to insert: 10
Inserted 10 at the beginning.

Menu:
Enter your choice: 2
Enter data to insert: 20
Inserted 20 at the end.

Menu:
Enter your choice: 5
Doubly Linked List: 10 20

C# Implementation

using System;

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

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

class DoublyLinkedList {
    private Node head; // Head pointer

    public DoublyLinkedList() {
        head = null;
    }

    // Insert at the beginning
    public void InsertAtBeginning(int data) {
        Node newNode = new Node(data);
        if (head != null) {
            newNode.Next = head;
            head.Prev = newNode;
        }
        head = newNode;
        Console.WriteLine($"Inserted {data} at the beginning.");
    }

    // Insert at the end
    public void InsertAtEnd(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            Console.WriteLine($"Inserted {data} at the end.");
            return;
        }
        Node temp = head;
        while (temp.Next != null) {
            temp = temp.Next;
        }
        temp.Next = newNode;
        newNode.Prev = temp;
        Console.WriteLine($"Inserted {data} at the end.");
    }

    // Delete at the beginning
    public void DeleteAtBeginning() {
        if (head == null) {
            Console.WriteLine("List is empty.");
            return;
        }
        head = head.Next;
        if (head != null) {
            head.Prev = null;
        }
        Console.WriteLine("Deleted node from the beginning.");
    }

    // Delete at the end
    public void DeleteAtEnd() {
        if (head == null) {
            Console.WriteLine("List is empty.");
            return;
        }
        if (head.Next == null) {
            head = null;
            Console.WriteLine("Deleted node from the end.");
            return;
        }
        Node temp = head;
        while (temp.Next != null) {
            temp = temp.Next;
        }
        temp.Prev.Next = null;
        Console.WriteLine("Deleted node from the end.");
    }

    // Display the list
    public void DisplayList() {
        if (head == null) {
            Console.WriteLine("List is empty.");
            return;
        }
        Node temp = head;
        Console.Write("Doubly Linked List: ");
        while (temp != null) {
            Console.Write(temp.Data + " ");
            temp = temp.Next;
        }
        Console.WriteLine();
    }
}

class Program {
    static void Main() {
        DoublyLinkedList list = new DoublyLinkedList();
        while (true) {
            Console.WriteLine("\nMenu:");
            Console.WriteLine("1. Insert at Beginning");
            Console.WriteLine("2. Insert at End");
            Console.WriteLine("3. Delete at Beginning");
            Console.WriteLine("4. Delete at End");
            Console.WriteLine("5. Display List");
            Console.WriteLine("6. Exit");
            Console.Write("Enter your choice: ");
            int choice = int.Parse(Console.ReadLine());

            switch (choice) {
                case 1:
                    Console.Write("Enter data to insert: ");
                    int data1 = int.Parse(Console.ReadLine());
                    list.InsertAtBeginning(data1);
                    break;
                case 2:
                    Console.Write("Enter data to insert: ");
                    int data2 = int.Parse(Console.ReadLine());
                    list.InsertAtEnd(data2);
                    break;
                case 3:
                    list.DeleteAtBeginning();
                    break;
                case 4:
                    list.DeleteAtEnd();
                    break;
                case 5:
                    list.DisplayList();
                    break;
                case 6:
                    Console.WriteLine("Exiting program.");
                    return;
                default:
                    Console.WriteLine("Invalid choice! Please try again.");
                    break;
            }
        }
    }
}

Explanation

1. Node Definition:
   • A Node class is created with:
     • data to store the node’s value.
     • prev to point to the previous node.
     • next to point to the next node.
2. DoublyLinkedList Class:
   • Contains the head pointer (head).
   • Implements methods for operations:
     • Insert at Beginning: Creates a new node, links it to the current head, and updates the head.
     • Insert at End: Traverses to the last node, links the new node, and updates the last node’s next pointer.
     • Delete at Beginning: Updates the head to the second node and clears its prev pointer.
     • Delete at End: Traverses to the last node, adjusts the second last node’s next pointer, and removes the last node.
     • Display List: Traverses the list and collects node values for display.
3. Menu Interaction:
   • Provides a while loop for menu-driven functionality.
   • Takes user input for choices and calls the corresponding method.
   • Terminates the program when the user selects “Exit.”

Here are example outputs for the menu-driven doubly linked list programs in the respective languages.

Output for C# Program

Input:

1. Insert at Beginning
2. Insert at End
3. Delete at Beginning
4. Delete at End
5. Display List
6. Exit
Enter your choice: 1
Enter data to insert: 10
Enter your choice: 2
Enter data to insert: 20
Enter your choice: 5
Enter your choice: 4
Enter your choice: 5
Enter your choice: 6

Output:

Inserted 10 at the beginning.
Inserted 20 at the end.
Doubly Linked List: 10 20 
Deleted node from the end.
Doubly Linked List: 10 
Exiting program.

Java Implementation

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

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

class DoublyLinkedList {
    private Node head;

    public DoublyLinkedList() {
        head = null;
    }

    // Insert at the beginning
    public void insertAtBeginning(int data) {
        Node newNode = new Node(data);
        if (head != null) {
            newNode.next = head;
            head.prev = newNode;
        }
        head = newNode;
        System.out.println("Inserted " + data + " at the beginning.");
    }

    // Insert at the end
    public void insertAtEnd(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            System.out.println("Inserted " + data + " at the end.");
            return;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
        newNode.prev = temp;
        System.out.println("Inserted " + data + " at the end.");
    }

    // Delete at the beginning
    public void deleteAtBeginning() {
        if (head == null) {
            System.out.println("List is empty.");
            return;
        }
        head = head.next;
        if (head != null) {
            head.prev = null;
        }
        System.out.println("Deleted node from the beginning.");
    }

    // Delete at the end
    public void deleteAtEnd() {
        if (head == null) {
            System.out.println("List is empty.");
            return;
        }
        if (head.next == null) {
            head = null;
            System.out.println("Deleted node from the end.");
            return;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.prev.next = null;
        System.out.println("Deleted node from the end.");
    }

    // Display the list
    public void displayList() {
        if (head == null) {
            System.out.println("List is empty.");
            return;
        }
        Node temp = head;
        System.out.print("Doubly Linked List: ");
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        DoublyLinkedList list = new DoublyLinkedList();
        java.util.Scanner scanner = new java.util.Scanner(System.in);

        while (true) {
            System.out.println("\nMenu:");
            System.out.println("1. Insert at Beginning");
            System.out.println("2. Insert at End");
            System.out.println("3. Delete at Beginning");
            System.out.println("4. Delete at End");
            System.out.println("5. Display List");
            System.out.println("6. Exit");
            System.out.print("Enter your choice: ");
            int choice = scanner.nextInt();

            switch (choice) {
                case 1:
                    System.out.print("Enter data to insert: ");
                    int data1 = scanner.nextInt();
                    list.insertAtBeginning(data1);
                    break;
                case 2:
                    System.out.print("Enter data to insert: ");
                    int data2 = scanner.nextInt();
                    list.insertAtEnd(data2);
                    break;
                case 3:
                    list.deleteAtBeginning();
                    break;
                case 4:
                    list.deleteAtEnd();
                    break;
                case 5:
                    list.displayList();
                    break;
                case 6:
                    System.out.println("Exiting program.");
                    return;
                default:
                    System.out.println("Invalid choice! Please try again.");
                    break;
            }
        }
    }
}

Explanation

Node Definition:

• A Node class contains:
  • data: Holds the value of the node.
  • prev: Points to the previous node.
  • next: Points to the next node.

DoublyLinkedList Class:

• Contains a head pointer for the list’s start.
• Implements methods for:
  • Insert at Beginning/End: Adjusts pointers of adjacent nodes during insertion.
  • Delete at Beginning/End: Modifies the head pointer or second-last node pointers.
  • Display List: Uses a loop to traverse nodes and print their values.

Main Method (Menu Interaction):

• Uses a Scanner for user input.
• Contains a while loop that:
  • Displays menu options.
  • Takes the user’s choice and invokes the appropriate method.
  • Exits the loop when the user selects “Exit.”

Output for Java Program

Input:

1. Insert at Beginning
2. Insert at End
3. Delete at Beginning
4. Delete at End
5. Display List
6. Exit
Enter your choice: 1
Enter data to insert: 5
Enter your choice: 2
Enter data to insert: 15
Enter your choice: 5
Enter your choice: 3
Enter your choice: 5
Enter your choice: 6

Output:

Inserted 5 at the beginning.
Inserted 15 at the end.
Doubly Linked List: 5 15 
Deleted node from the beginning.
Doubly Linked List: 15 
Exiting program.

JavaScript Implementation

class Node {
    constructor(data) {
        this.data = data; // Data part of the node
        this.prev = null; // Pointer to the previous node
        this.next = null; // Pointer to the next node
    }
}

class DoublyLinkedList {
    constructor() {
        this.head = null; // Head pointer
    }

    // Insert at the beginning
    insertAtBeginning(data) {
        const newNode = new Node(data);
        if (this.head !== null) {
            newNode.next = this.head;
            this.head.prev = newNode;
        }
        this.head = newNode;
        console.log(`Inserted ${data} at the beginning.`);
    }

    // Insert at the end
    insertAtEnd(data) {
        const newNode = new Node(data);
        if (this.head === null) {
            this.head = newNode;
            console.log(`Inserted ${data} at the end.`);
            return;
        }
        let temp = this.head;
        while (temp.next !== null) {
            temp = temp.next;
        }
        temp.next = newNode;
        newNode.prev = temp;
        console.log(`Inserted ${data} at the end.`);
    }

    // Delete at the beginning
    deleteAtBeginning() {
        if (this.head === null) {
            console.log("List is empty.");
            return;
        }
        this.head = this.head.next;
        if (this.head !== null) {
            this.head.prev = null;
        }
        console.log("Deleted node from the beginning.");
    }

    // Delete at the end
    deleteAtEnd() {
        if (this.head === null) {
            console.log("List is empty.");
            return;
        }
        if (this.head.next === null) {
            this.head = null;
            console.log("Deleted node from the end.");
            return;
        }
        let temp = this.head;
        while (temp.next !== null) {
            temp = temp.next;
        }
        temp.prev.next = null;
        console.log("Deleted node from the end.");
    }

    // Display the list
    displayList() {
        if (this.head === null) {
            console.log("List is empty.");
            return;
        }
        let temp = this.head;
        let output = "Doubly Linked List: ";
        while (temp !== null) {
            output += temp.data + " ";
            temp = temp.next;
        }
        console.log(output.trim());
    }
}

// Menu-driven interaction
const list = new DoublyLinkedList();
const prompt = require("prompt-sync")();

while (true) {
    console.log("\nMenu:");
    console.log("1. Insert at Beginning");
    console.log("2. Insert at End");
    console.log("3. Delete at Beginning");
    console.log("4. Delete at End");
    console.log("5. Display List");
    console.log("6. Exit");
    const choice = parseInt(prompt("Enter your choice: "));

    switch (choice) {
        case 1:
            const data1 = parseInt(prompt("Enter data to insert: "));
            list.insertAtBeginning(data1);
            break;
        case 2:
            const data2 = parseInt(prompt("Enter data to insert: "));
            list.insertAtEnd(data2);
            break;
        case 3:
            list.deleteAtBeginning();
            break;
        case 4:
            list.deleteAtEnd();
            break;
        case 5:
            list.displayList();
            break;
        case 6:
            console.log("Exiting program.");
            process.exit();
        default:
            console.log("Invalid choice! Please try again.");
            break;
    }
}

Explanation

Node Definition:

• A Node class is defined using the constructor method with:
  • data: Node’s value.
  • prev: Points to the previous node (default is null).
  • next: Points to the next node (default is null).

DoublyLinkedList Class:

• Contains a head property initialized to null.
• Methods:
  • Insert at Beginning/End: Creates a new node and links it appropriately to other nodes.
  • Delete at Beginning/End: Adjusts the head pointer or modifies the previous/next references of nodes.
  • Display List: Traverses the list starting from head and logs node values.

Menu Interaction:

• Uses the prompt-sync package to take user input.
• Runs a while loop:
  • Displays the menu.
  • Takes user input for choices.
  • Calls the respective method.
  • Exits the loop when the user selects “Exit.”

Output for JavaScript Program

Input:

1. Insert at Beginning
2. Insert at End
3. Delete at Beginning
4. Delete at End
5. Display List
6. Exit
Enter your choice: 1
Enter data to insert: 30
Enter your choice: 1
Enter data to insert: 25
Enter your choice: 5
Enter your choice: 4
Enter your choice: 5
Enter your choice: 6

Output:

Inserted 30 at the beginning.
Inserted 25 at the beginning.
Doubly Linked List: 25 30
Deleted node from the end.
Doubly Linked List: 25
Exiting program.

Python Implementation

class Node:
    def __init__(self, data):
        self.data = data  # Data part of the node
        self.prev = None  # Pointer to the previous node
        self.next = None  # Pointer to the next node

class DoublyLinkedList:
    def __init__(self):
        self.head = None  # Head pointer

    # Insert at the beginning
    def insert_at_beginning(self, data):
        new_node = Node(data)
        if self.head is not None:
            new_node.next = self.head
            self.head.prev = new_node
        self.head = new_node
        print(f"Inserted {data} at the beginning.")

    # Insert at the end
    def insert_at_end(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            print(f"Inserted {data} at the end.")
            return
        temp = self.head
        while temp.next is not None:
            temp = temp.next
        temp.next = new_node
        new_node.prev = temp
        print(f"Inserted {data} at the end.")

    # Delete at the beginning
    def delete_at_beginning(self):
        if self.head is None:
            print("List is empty.")
            return
        self.head = self.head.next
        if self.head is not None:
            self.head.prev = None
        print("Deleted node from the beginning.")

    # Delete at the end
    def delete_at_end(self):
        if self.head is None:
            print("List is empty.")
            return
        if self.head.next is None:
            self.head = None
            print("Deleted node from the end.")
            return
        temp = self.head
        while temp.next is not None:
            temp = temp.next
        temp.prev.next = None
        print("Deleted node from the end.")

    # Display the list
    def display_list(self):
        if self.head is None:
            print("List is empty.")
            return
        temp = self.head
        output = "Doubly Linked List: "
        while temp is not None:
            output += f"{temp.data} "
            temp = temp.next
        print(output.strip())

# Menu-driven interaction
if __name__ == "__main__":
    list = DoublyLinkedList()

    while True:
        print("\nMenu:")
        print("1. Insert at Beginning")
        print("2. Insert at End")
        print("3. Delete at Beginning")
        print("4. Delete at End")
        print("5. Display List")
        print("6. Exit")
        choice = int(input("Enter your choice: "))

        if choice == 1:
            data = int(input("Enter data to insert: "))
            list.insert_at_beginning(data)
        elif choice == 2:
            data = int(input("Enter data to insert: "))
            list.insert_at_end(data)
        elif choice == 3:
            list.delete_at_beginning()
        elif choice == 4:
            list.delete_at_end()
        elif choice == 5:
            list.display_list()
        elif choice == 6:
            print("Exiting program.")
            break
        else:
            print("Invalid choice! Please try again.")

Explanation

Node Class:

• Defined with an __init__ method to initialize:
  • data: Stores the node’s value.
  • prev: Points to the previous node (default is None).
  • next: Points to the next node (default is None).

DoublyLinkedList Class:

• Contains a head attribute for the list’s start.
• Implements:
  • Insert at Beginning: Creates a node and updates the head’s previous pointer.
  • Insert at End: Traverses to the last node and links the new node.
  • Delete at Beginning/End: Adjusts pointers to remove the first or last node.
  • Display List: Traverses nodes starting from the head and prints their values.

Menu-Driven Interaction:

• Contains a while loop:
  • Displays menu options.
  • Takes user input using input() function.
  • Calls corresponding methods based on the user’s choice.
  • Breaks the loop on selecting “Exit.”

Output for Python Program

Input:

1. Insert at Beginning
2. Insert at End
3. Delete at Beginning
4. Delete at End
5. Display List
6. Exit
Enter your choice: 1
Enter data to insert: 50
Enter your choice: 2
Enter data to insert: 70
Enter your choice: 5
Enter your choice: 3
Enter your choice: 5
Enter your choice: 6

Output:

Inserted 50 at the beginning.
Inserted 70 at the end.
Doubly Linked List: 50 70
Deleted node from the beginning.
Doubly Linked List: 70
Exiting program.