Close Menu
Data Structures

Understanding Doubly Linked List: A Comprehensive Guide

By

In the world of data structures, a doubly linked list is a vital concept that extends the functionality of a singly linked list by allowing bidirectional traversal. This guide dives deeply into the doubly linked list, its structure, memory representation, and essential operations.

What is a Doubly Linked List?

A doubly linked list is an advanced type of linked list where each node contains three components:

  1. Node Data: Stores the actual information or value of the node.
  2. Next Pointer: Points to the next node in the sequence.
  3. Previous Pointer: Points to the preceding node in the sequence.
Structure of Doubly Linked List in Data Structure
Node Structure of Doubly Linked List in Data Structure
Structure of Doubly Linked List
Representation of Doubly Linked List

This additional pointer to the previous node makes doubly linked lists more versatile than singly linked lists, as it allows traversal in both forward and backward directions.

Structure of a Node in Programming Language

In the C programming language, a node in a doubly linked list can be defined as:

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

Here:

  • prev holds the address of the previous node (or NULL if it is the first node).
  • data stores the value of the node.
  • next holds the address of the next node (or NULL if it is the last node).

Structure of Node in Multiple Programming Language

Here’s how a node in a doubly linked list can be defined in C, C++, C#, Java, JavaScript, and Python, along with a step-by-step explanation for each implementation.

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.

Summary Table of Syntax

LanguageCode SnippetPointers Used
Cstruct node { struct node *prev, *next; int data; };prev, next
C++struct Node { Node* prev, *next; int data; };prev, next
C#class Node { public Node Prev, Next; int Data; }Prev, Next
Javaclass Node { Node prev, next; int data; }prev, next
JavaScriptclass Node { constructor(data) { this.prev, next; } }prev, next
Pythonclass Node: def __init__(self, data): prev, nextprev, next

All these implementations represent the same conceptual doubly linked list structure but in a language-specific syntax.

Advantages of Doubly Linked List

The doubly linked list overcomes the limitations of the singly linked list in the following ways:

  • Bidirectional Traversal: Unlike the singly linked list, where traversal is limited to one direction, a doubly linked list allows traversal both forward and backward.
  • Efficient Node Manipulation: Inserting and deleting nodes becomes more flexible, as pointers to both previous and next nodes are maintained.

However, this flexibility comes with a tradeoff: doubly linked lists require additional memory to store the extra pointer, making them more memory-intensive than their singly linked counterpart.

Memory Representation of Doubly Linked List

The memory representation of a doubly linked list illustrates how each node connects to its predecessor and successor:

  • The first node has its prev pointer set to NULL, indicating that there is no preceding node.
  • Each node’s next pointer connects to the address of the subsequent node, forming a chain in the forward direction.
  • Similarly, each node’s prev pointer links to the address of the preceding node, enabling backward traversal.

Example 1:

Imagine a doubly linked list containing three nodes with data values 13, 26, and 39. In memory:

  • The head pointer points to the first node (13).
  • The prev pointer of 13 is NULL, while its next pointer points to 26.
  • The second node (26) links back to 13 through its prev pointer and forward to 39 through its next pointer.
  • The third node (39) has its next pointer set to NULL, marking the end of the list.

This structure allows seamless traversal in either direction, depending on the operation or requirement.

Example 2:

In the image given below, the first element of the list i.e. 15 stored at address 100. The head pointer points to the starting address 100. Since this is the first element being added to the list therefore the prev of the list contains null. The next node of the list resides at address 400 therefore the first node contains 400 in its next pointer.

Example of Memory Representation of Doubly Linked List
Memory Representation of Doubly Linked List

We can traverse the list in this way until we find any node containing null in its next part.

Key Operations on Doubly Linked List

The doubly linked list supports various operations essential for dynamic data management. These operations are briefly outlined below:

1. Node Creation

A node in a doubly linked list can be created using the following code snippet in C:

struct node {
    struct node *prev;
    int data;
    struct node *next;
};
struct node *head; // Points to the first node

Node Creation In Multiple Programming Languages

Here’s how to create a node in a doubly linked list in C, C++, C#, Java, JavaScript, and Python, along with a detailed explanation of each step.

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.

Summary Table of Node Creation

LanguageHead Pointer DeclarationConstructor Required?
Cstruct node *head = NULL;No
C++Node* head = nullptr;Yes
C#Node head = null;Yes
JavaNode head = null;Yes
JavaScriptlet head = null;Yes
Pythonhead = NoneYes

Each implementation adapts the doubly linked list node to the syntax and paradigms of the programming language while maintaining its core structure and functionality.

2. Insertion at the Beginning

This operation involves adding a new node at the start of the list. It requires updating:

  • The next pointer of the new node to point to the current head.
  • The prev pointer of the current head to point back to the new node.
  • The head pointer to the new node.

3. Insertion at End

To insert a node at the end:

  • Traverse to the last node.
  • Set its next pointer to the new node.
  • Update the prev pointer of the new node to point to the last node.

4. Insertion After a Specific Node

Inserting after a specific node involves:

  • Traversing to the specified node.
  • Updating the pointers of the new and existing nodes to ensure the new node is correctly placed in the sequence.

5. Deletion at the Beginning

To delete the first node:

  • Update the head pointer to the second node.
  • Set the prev pointer of the new head to NULL.
  • Free the memory of the removed node.

6. Deletion at the End

Deleting the last node involves:

  • Traversing to the last node.
  • Updating the next pointer of the second-last node to NULL.
  • Freeing the memory of the last node.

7. Deletion of a Node with Given Data

For this operation:

  • Locate the node with the matching data.
  • Update the next pointer of the preceding node and the prev pointer of the succeeding node to bypass the target node.
  • Free the memory of the removed node.

8. Searching

To search for a specific value:

  • Traverse the list node by node.
  • Compare each node’s data with the target value.
  • Return the node’s address if found; otherwise, return NULL.

9. Traversing

Traversal involves visiting each node to perform operations like displaying data or searching for elements. Traversal can occur:

  • Forward Traversal: Using the next pointer.
  • Backward Traversal: Using the prev pointer.

Applications of Doubly Linked List

Due to their flexible structure, doubly linked lists are widely used in:

  1. Implementation of Deques (Double-Ended Queues).
  2. Navigation Systems: For maintaining forward and backward movement.
  3. Undo/Redo Functionality: In text editors and other applications.
  4. Complex Data Structures: Such as trees, graphs, and LRU (Least Recently Used) caches.

Conclusion

The doubly linked list is a powerful data structure offering enhanced flexibility over the singly linked list. Despite its higher memory consumption, its bidirectional traversal and efficient manipulation capabilities make it a preferred choice in numerous programming scenarios. Understanding its structure and mastering its operations are critical for any programmer or computer scientist aiming to excel in data structures and algorithm design.

Here is a detailed example of a menu-driven program to perform all operations of a doubly linked list (insertion, deletion, searching, and traversal) implemented in C, C++, C#, Java, JavaScript, and Python.

The example includes a step-by-step explanation of each operation and its corresponding output. Let’s begin with one language at a time.

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.

Key Similarities Across Languages

  • Node Structure:
    • In all languages, a Node is the fundamental building block of the doubly linked list. Each node contains:
      • Data: Stores the value of the node.
      • Prev: Pointer/reference to the previous node.
      • Next: Pointer/reference to the next node.
  • Doubly Linked List Class/Structure:
    • A Doubly Linked List contains methods to manage nodes:
      • Insert at Beginning: Adds a node at the start of the list, updating the head and next/prev pointers as required.
      • Insert at End: Traverses to the last node and appends the new node by adjusting the next and prev pointers.
      • Delete at the Beginning: Updates the head to point to the second node, and clear the first node’s next pointer.
      • Delete at End: Traverses to the second-to-last node, removes the last node, and updates the next pointer of the second-to-last node to null.
      • Traversal: Loops through the list using the next pointer, starting from the head, to access each node.
  • Menu-Driven Approach:
    • All languages implement a menu-driven program for user interaction, providing operations like Insert, Delete, Display, and Exit.
    • The program continues running in a loop (e.g., while or do-while) until the user chooses to exit.
  • Pointer/Reference Management:
    • Each node’s prev and next pointers (or references) are updated during insertion and deletion to maintain the integrity of the list.
  • Display Operation:
    • In all implementations, traversal starts from the head pointer and continues until null (or equivalent, such as nullptr or None) is encountered.
    • The data of each node is printed sequentially.
  • Dynamic Memory Management:
    • In C and C++, dynamic memory is allocated using malloc or new, and freed using free or delete.
    • In Java, JavaScript, C#, and Python, memory is managed automatically via garbage collection.
  • Input Handling:
    • Each language takes input for menu options and node data:
      • C: scanf for input.
      • C++: cin.
      • Java: Scanner.
      • C#: Console.ReadLine.
      • JavaScript: prompt-sync or readline.
      • Python: input().
  • Output Handling:
    • Each language provides its way of displaying output:
      • C: printf.
      • C++: cout.
      • Java: System.out.println.
      • C#: Console.WriteLine.
      • JavaScript: console.log.
      • Python: print.
  • Exit Operation:
    • Each program has an option to exit the loop:
      • C, C++, Java, C#: Break the loop when the exit choice is selected.
      • Python, JavaScript: Use a condition to exit the loop.
  • Logic for Operations:
    • The core logic of the operations (insertion, deletion, and traversal) is similar in all languages:
    • Nodes are created dynamically and linked using pointers or references.
    • Deletion operations ensure that adjacent nodes’ pointers are updated to maintain the list’s structure.

Frequently Asked Questions (FAQs) on Doubly Linked List

What is a Doubly Linked List, and how is it different from a Singly Linked List?

A doubly linked list is a type of linked list where each node contains three parts:

  1. Node data (the actual value).
  2. Pointer to the next node in the sequence.
  3. Pointer to the previous node in the sequence.

In contrast, a singly linked list only contains a pointer to the next node, allowing traversal in a single direction. The primary advantage of a doubly linked list is its ability to traverse both forwards and backward due to the additional pointer to the previous node.

What are the key components of a Node in a Doubly Linked List in C?

In C programming, the structure of a node in a doubly linked list can be defined as:

struct node {
    struct node *prev; // Pointer to the previous node
    int data;          // Node's data
    struct node *next; // Pointer to the next node
};

Here:

  • prev holds the address of the previous node or NULL if it’s the first node.
  • data stores the value or information of the node.
  • next holds the address of the next node or NULL if it’s the last node.

What are the advantages of using a Doubly Linked List?

The doubly linked list offers several advantages:

  • Bidirectional Traversal: Nodes can be traversed in both forward and backward directions, unlike singly linked lists.
  • Efficient Node Manipulation: It allows easy insertion and deletion of nodes at both ends or in the middle of the list.
  • Flexibility: It is better suited for applications requiring frequent movement in both directions, such as navigation systems or undo/redo functionality.

However, it uses more memory compared to a singly linked list due to the extra pointer in each node.

How is memory represented in a Doubly Linked List?

In a doubly linked list:

  • The prev pointer of the first node is set to NULL since there is no node before it.
  • The next pointer of the last node is also set to NULL, marking the end of the list.
  • Each node maintains a connection to both its predecessor and successor through prev and next pointers.

For example, if nodes have data values 13, 26, and 39:

  • Node 13 has prev = NULL, data = 13, and next = 26.
  • Node 26 connects back to 13 via prev and forward to 39 via next.
  • Node 39 has next = NULL and prev = 26.

What are the steps for inserting a node at the beginning of a Doubly Linked List?

To insert a node at the beginning:

  1. Create a new node.
  2. Set the next pointer of the new node to the current head.
  3. Set the prev pointer of the current head to the new node.
  4. Update the head pointer to the new node.
  5. If the list was empty, set both the next and prev pointers of the new node to NULL.

How can we delete the last node in a Doubly Linked List?

To delete the last node:

  1. Traverse to the last node.
  2. Update the next pointer of the second-last node to NULL.
  3. Free the memory of the last node using a function like free() in C programming.
  4. If the node being deleted is the only node, update the head pointer to NULL.

What is the process for searching for an element in a Doubly Linked List?

To search for an element:

  1. Start from the head node.
  2. Compare the data of each node with the target value.
  3. If a match is found, return the node’s address or position.
  4. If the traversal reaches the end without a match, return NULL or indicate that the element is not found.

This operation has a time complexity of O(n), where n is the number of nodes in the list.

How does backward traversal work in a Doubly Linked List?

Backward traversal in a doubly linked list is achieved using the prev pointers. Starting from the last node:

  1. Access the prev pointer to move to the previous node.
  2. Repeat this process until the first node (where prev = NULL) is reached.

Backward traversal is particularly useful in applications like undo/redo operations in text editors or backward navigation in multimedia players.

What are the disadvantages of a Doubly Linked List?

While doubly linked lists have significant advantages, they also come with some disadvantages:

  • Increased Memory Usage: Each node requires an additional pointer to store the address of the previous node.
  • More Complex Operations: Operations like insertion and deletion involve updating two pointers (next and prev), increasing complexity.
  • Higher Overhead: The additional memory and pointer management make it less efficient for simple use cases compared to singly linked lists.

What are the practical applications of a Doubly Linked List?

Doubly linked lists are widely used in various applications, including:

  1. Deque Implementation: Supports operations from both ends efficiently.
  2. Undo/Redo Functionality: In text editors and other applications, where traversing back and forth is necessary.
  3. Navigation Systems: For bidirectional traversal in routes or paths.
  4. LRU Cache: Used in Least Recently Used (LRU) caching for fast addition and removal of elements.
  5. Binary Tree Conversion: Converting binary trees to linked lists for specific algorithms.
Share.
Examsmeta Logo

Examsmeta is your one-stop destination for comprehensive educational resources across a wide array of disciplines. At Examsmeta, we are dedicated to providing high-quality, topic-wise notes and articles that cater to students, educators, researchers, and lifelong learners. Our mission is to make learning accessible, engaging, and effective for everyone. Our mission is to empower learners by offering detailed, accurate, and up-to-date educational content. We strive to foster a love for learning and to support the academic and professional growth of our users. Whether you're preparing for exams, conducting research, or simply expanding your knowledge, Examsmeta is here to guide you every step of the way.