Doubly Linked List Implementation In C++, Java, Python and C

This article will Implement the Doubly linked list in C, C++, Python, and Java.

A doubly linked list is a linked list that consists of three fields. One field will store the data and the remaining two fields will store the address of the previous and next fields. Using doubly-linked lists we can traverse a linked list from both front and last.

Operations Performed On Doubly Linked List:

• Insertion at the head.
• Insertion at end of the LinkedList.
• Insertion at nth Node.
• Deletion at the head.
• Deletion at the end of the Linked List.
• Deletion at nth Node.
• Searching in Doubly Linked List
• Traversing

Declaring A Node In Doubly Linked List:

In the following way, a node in a doubly-linked list is declared. A field to store data and two fields to store the address of the next and previous node.

// Declaring a node in doubly linked-list
struct Node {
int data;
Node* next;
Node* prev;
};

Function to Get New Node In Doubly Linked List:

This function will return a node of the type defined earlier for a doubly-linked list.

 

 

 

Node* getNewNode(int data){    // function takes data as argument
    Node* newNode = new Node();    // Dynamic memory allocation for newNode
    newNode->data = data;   
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

Function To Traverse or Print Doubly Linked List ( Visit each node in the Doubly linked list) In forwarding Direction:

// Print in forward direction by visiting each node
void printForward(Node* head){
    Node* temp = head;
    while(temp!=NULL){          // prints the data until all the nodes visited i.e., last node = NULL
        cout<<temp->data<<" ";
        temp=temp->next;
    }
    cout<<"\n";
}

Traversing and Printing In Reverse Direction Of A Doubly Linked List:

// function to print in reverse direction by visiting each node
void printBackward(Node* head){
    Node* temp = head;
    while(temp->next!=NULL){
        temp=temp->next;          // visitng last node
    }
    
    while(temp!=NULL){
        cout<<temp->data<<" ";
        temp=temp->prev;        // traversing each element using prev address from last
    }
    
    cout<<endl;
}

Insertion At The Head In Doubly Linked List:

This function will create a new node with the data and insert it at the head of the doubly linked list.

// Function to insert at head of the doubly linked list
void InsertAtHead(int data){
    Node* newNode = getNewNode(data);
    if(head==NULL){
        head = newNode;
        cout<<head->data<<" Inserted at head"<<endl;
        return;
    }
    
    head->prev = newNode;
    newNode->next = head;
    head = newNode;
    cout<<head->data<<" Inserted at head"<<endl;
    printForward(head);
}

Insertion At End In Doubly Linked List:

This function will insert the given data at the end of the doubly linked list.

 

 

// Function to insert at the end of the doubly linked list
void InsertAtEnd(int data){
    Node* newNode = getNewNode(data);
    if(head==NULL){           // if head is null we will insert at head
        head = newNode;
        cout<<head->data<<" Inserted"<<endl;
        printForward(head);
        return;
    }
    Node* temp = head;  
    while(temp->next != NULL){
        temp = temp->next;          //first we will go to the last node in the doubly linked list
    }                               // and then we will insert from the last
    newNode->prev = temp;          // set newNode's previous node address as last node
    temp->next = newNode;          // Now set last node's next address as new Node
    cout<<temp->next->data<<" Inserted at end"<<endl;
    printForward(head);
    
}