double linked list

Doubly Linked Lists are also a sequential data structure with the only difference from single linked list is that the doubly linked lists contain two pointers instead of one to store the address of both next node and previous node respectively.

                                 


*Each node contains two pointers, one pointing to the next node and the other pointing to the previous node.

*The prev of Head node is NULL, as there is no previous node of Head.

*The next of last node is NULL, as there is no node after the last node.


below is a sample of double linked list node:

c++:

struct Node { 
    int data; 
    struct Node* next; // Pointer to next node in DLL 
    struct Node* prev; // Pointer to previous node in DLL 
};
Java:
public class DLL { 
    Node head; // head of list 
  
    /* Doubly Linked list Node*/
    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 list:
A DLL can be traversed in both forward and backward direction.
The delete operation in DLL is more efficient if the pointer to the node to be deleted is given.
We can quickly insert a new node before a given node.
In a singly linked list, to delete a node, a pointer to the previous node is needed. To get this previous node, sometimes the list is traversed. In DLL, we can get the previous node using the previous pointer.

Disadvantages of doubly linked lists over singly linked list:
Every node of DLL Require extra space for a previous pointer.
All operations require an extra pointer previous to be maintained. For example, an insertion, we need to modify previous pointers together with next pointers.


Creating and Traversing a Doubly Linked List
Creating and Traversing a doubly linked list is almost similar to that of the singly linked lists. The only difference is that in doubly linked lists we need to maintain an extra previous pointer for every node while creating the list.

Below is the complete program to create and traverse a Doubly Linked List :
c++:
// A linked list node 
struct Node { 
    int data; 
    struct Node* next; 
    struct Node* prev; 
}; 

// This function prints contents of Doubly linked 
// list starting from the given node 
void printList(struct Node* node) 
{ 
    struct Node* last; 

    // Traverse the linked list in forward direction
    // using the next node's pointer present 
    // at each node
    cout<<"\nTraversal in forward direction \n"; 
    while (node != NULL) { 
        cout<<node->data<<" "; 
        last = node; 
        node = node->next; 
    } 

    // Traverse the linked list in reverse direction 
    // starting from the last node using the previous
    // node's pointer present at each node
    printf("\nTraversal in reverse direction \n"); 
    while (last != NULL) { 
        cout<<last->data<<" "; 
        last = last->prev; 
    } }                    
void append(struct Node** head_ref, int new_data) //function enters new node at the end
{ 
    /* 1. allocate node */
    Node* new_node = new Node; 

    struct Node* last = *head_ref; /* used in step 5*/

    /* 2. put in the data */
    new_node->data = new_data; 

    /* 3. This new node is going to be the last node, so 
        make next of it as NULL*/
    new_node->next = NULL; 

    /* 4. If the Linked List is empty, then make the new 
        node as head */
    if (*head_ref == NULL) { 
        new_node->prev = NULL; 
        *head_ref = new_node; 
        return; 
    } 

    /* 5. Else traverse till the last node */
    while (last->next != NULL) 
        last = last->next; 

    /* 6. Change the next of last node */
    last->next = new_node; 

    /* 7. Make last node as previous of new node */
    new_node->prev = last; 

    return; 
} 
Java:
// A complete working Java program to demonstrate  
// Doubly Linked List 

public class DLL { 
    Node head; // head of list 

    /* Doubly Linked list Node*/
    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; } 
    } 

 // Add a node at the end of the list 
    void append(int new_data) 
    { 
        /* 1. allocate node 
           2. put in the data */
        Node new_node = new Node(new_data); 

        Node last = head; /* used in step 5 */

        /* 3. This new node is going to be the last node, so 
              make next of it as NULL */
        new_node.next = null; 

        /* 4. If the Linked List is empty, then make the new 
              node as head */
        if (head == null) { 
            new_node.prev = null; 
            head = new_node; 
            return; 
        } 

        /* 5. Else traverse till the last node */
        while (last.next != null) 
            last = last.next; 

        /* 6. Change the next of last node */
        last.next = new_node; 

        /* 7. Make last node as previous of new node */
        new_node.prev = last; 
    } 

    // This function prints contents of linked list
    //  starting from the given node 
    public void printlist(Node node) 
    { 
        Node last = null; 

        // Traverse the linked list in forward direction
        // using the next node's pointer present 
        // at each node
        System.out.println("Traversal in forward Direction"); 
        while (node != null) { 
            System.out.print(node.data + " "); 
            last = node; 
            node = node.next; 
        } 
        System.out.println(); 
        
        // Traverse the linked list in reverse direction 
        // starting from the last node using the previous
        // node's pointer present at each node
        System.out.println("Traversal in reverse direction"); 
        while (last != null) { 
            System.out.print(last.data + " "); 
            last = last.prev; 
        } 
    } 




darkmode