double linked list

Doubly Linked Lists are a type of sequential data structure that differs from a singly linked list in that each node contains two pointers: one pointing to the next node and the other pointing to the previous node.
                                 

In a doubly linked list:

1. Each node has two pointers: one pointing to the next node in the list and the other pointing to the previous node.
2. The "prev" pointer of the head node is NULL since there is no previous node before the head.
3. The "next" pointer of the last node in the list is NULL because there is no node after the last node.

These properties of doubly linked lists enable efficient traversal in both directions (forward and backward) and provide flexibility for various operations on the list, such as insertion and deletion at both ends.

 Sample of double linked list node in C++:

struct Node { 
    int data; 
    struct Node* next; // Pointer to next node in DLL 
    struct Node* prev; // Pointer to previous node in DLL 
};

 Sample of double-linked list node in Java:

   class Node { 
        int data; 
        Node prev; 
        Node next; 
  
        // Constructor to create a new node 
        // next and prev is by default initialized as null 
        Node(int d) { data = d; } 
    } 

Advantages of doubly-linked lists over singly-linked lists:

1. Bidirectional traversal: A doubly linked list can be traversed in both forward and backward directions. This allows for more flexible navigation within the list compared to singly linked lists, which can only be traversed in one direction.

2. Efficient delete operation: When a pointer to the node to be deleted is given, the delete operation in a doubly linked list is more efficient. This is because, in a singly linked list, deleting a node requires knowledge of the previous node, which may involve traversing the list. In a doubly linked list, the previous node can be accessed directly through the previous pointer, resulting in faster deletion.

3. Easy insertion before a given node: Inserting a new node before a given node is quick and efficient in a doubly linked list. With the help of the previous pointer, the new node can be easily inserted before the desired node without the need for extensive traversal.

Disadvantages of doubly-linked lists over singly-linked lists:

1. Extra space requirement: Each node in a doubly linked list requires additional memory to store the previous pointer. This increases the overall space consumption compared to singly linked lists, which only require a single next pointer for each node.

2. Maintenance of additional pointers: All operations on a doubly linked list, such as insertion and deletion, require the additional pointer for the previous node to be maintained. This adds complexity and overhead to the list operations compared to singly linked lists.

Creating and traversing a doubly linked list:

Is a process similar to that of singly linked lists, with the additional requirement of maintaining a previous pointer for each node during list creation.

To create a doubly linked list, each node is initialized with the necessary data and two pointers: one pointing to the next node and another pointing to the previous node. This enables bidirectional traversal within the list.

During the creation process, the previous pointer of the head node is typically set to NULL since there is no previous node before the head. As nodes are added to the list, the previous pointers are appropriately updated to maintain the correct linkages between nodes.

Traversing a doubly linked list involves starting from the head node and moving forward using the next pointers. This allows for straightforward access to the data in each node. Additionally, the previous pointers can be utilized to traverse the list in the reverse direction if needed.

By understanding the concept of doubly linked lists and following the steps for creating and traversing them, one can effectively utilize this data structure to accommodate various requirements.

complete Java program that demonstrates the creation and traversal of a doubly linked list:

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

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

class DoublyLinkedList {
    Node head;

    public DoublyLinkedList() {
        this.head = null;
    }

    public void insert(int data) {
        Node newNode = new Node(data);

        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
            newNode.prev = current;
        }
    }

    public void display() {
        Node current = head;
        System.out.println("Doubly Linked List:");
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        DoublyLinkedList list = new DoublyLinkedList();

        // Inserting nodes in the doubly linked list
        list.insert(1);
        list.insert(2);
        list.insert(3);
        list.insert(4);
        list.insert(5);

        // Displaying the doubly linked list
        list.display();
    }
}

In this program, we have two classes: Node representing a node in the doubly linked list and DoublyLinkedList representing the doubly linked list itself. The Node class contains the data, previous pointer (prev), and next pointer (next). The DoublyLinkedList class has a head pointer and methods to insert nodes at the end of the list (insert) and display the list (display).

In the main function, we create a DoublyLinkedList object, insert nodes with data values 1, 2, 3, 4, and 5, and then display the contents of the doubly linked list.

When you run the program, it will output the elements of the doubly linked list as follows:

Doubly Linked List:
1 2 3 4 5

complete C++ program that demonstrates the creation and traversal of a doubly linked list:

#include <iostream>
using namespace std;

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

    Node(int data) {
        this->data = data;
        this->prev = nullptr;
        this->next = nullptr;
    }
};

class DoublyLinkedList {
public:
    Node* head;

    DoublyLinkedList() {
        this->head = nullptr;
    }

    void insert(int data) {
        Node* newNode = new Node(data);

        if (head == nullptr) {
            head = newNode;
        }
        else {
            Node* current = head;
            while (current->next != nullptr) {
                current = current->next;
            }
            current->next = newNode;
            newNode->prev = current;
        }
    }

    void display() {
        Node* current = head;
        cout << "Doubly Linked List:" << endl;
        while (current != nullptr) {
            cout << current->data << " ";
            current = current->next;
        }
        cout << endl;
    }
};

int main() {
    DoublyLinkedList list;

    // Inserting nodes in the doubly linked list
    list.insert(1);
    list.insert(2);
    list.insert(3);
    list.insert(4);
    list.insert(5);

    // Displaying the doubly linked list
    list.display();

    return 0;
}