# Doubly Linked List

<figure><img src="/files/moSOOwx3BALJnGaTpJy6" alt=""><figcaption></figcaption></figure>

{% code title="main.cpp" lineNumbers="true" %}

```cpp
#include "DoublyLinkedList.h"

int main() {  
    DoublyLL list;
    list.insert(1);
    list.insert(2);
    list.insertAtHead(3);
    list.insertAtHead(4);
    list.insertAtHead(5);
    
    cout << "Main List: " << list << endl;
    
    cout << "Given Node Data Present: " << boolalpha << list.search(1) << endl << endl;

    int temp;
    cout << "Head Removed: " << boolalpha << list.removeHead(temp) << endl;
    cout << "Deleted Head Node Element: " << temp << endl;
    cout << list << endl;

    cout << "Tail Node Removed: " << boolalpha << list.remove(2) << endl;
    cout << list << endl;

    cout << "Random Node Removed: " << boolalpha << list.remove(3) << endl;
    cout << list << endl;

    // --> There are some bugs in clear functions
    // list.clear();

    // cout << "List is Empty: " << boolalpha << list.isEmpty() << endl;
    
    // --> checking assignment & copy constructor
    
    // DoublyLL list1;
    // list1.insert(1);
    // list1.insert(2);
    // list1.insertAtHead(3);
    // list1.insertAtHead(4);
    // cout << list1 << endl;

    // DoublyLL list2;
    // list2.insert(5);
    // list2.insert(6);
    // list2.insertAtHead(7);
    // list2.insertAtHead(8);
    // list2.insertAtHead(9);

    // list1.Swap(list2);

    // cout << "List1: " << list1 << endl << "List2: " << list2 << endl;

    // DoublyLL list(list1);
    // list1.insertAtHead(10); 
    // cout << "Values of list1 copied into list using copy constructor! \n" << list << endl;

    // DoublyLL assignmentList1, assignmentList2;
    // assignmentList1 = assignmentList2 = list1;

    // list2.insertAtHead(20);

    // cout << "Values of list2 copied into assignmentList1 & assignmentList2 using Assignment operator! \n" << assignmentList1 << endl << assignmentList2;
}
```

{% endcode %}

{% code title="DoublyLinkedList.h" overflow="wrap" lineNumbers="true" %}

```cpp
#include <iostream>
#pragma once
using namespace std;

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

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

    // important 
    ~Node () {
        next = nullptr;
        prev = nullptr;

        delete next;
        delete prev;
    }
};

class DoublyLL {
    Node* head;
    Node* tail;
    int elements;
public:

    DoublyLL() : head(nullptr), tail(nullptr), elements(0) {};
    
    DoublyLL(const DoublyLL& list);

    DoublyLL& operator= (const DoublyLL& list);

    void insert(const int val);

    void insertAtHead(const int val);

    bool search(const int val);

    bool remove(const int val);

    bool removeHead(int& headData);

    void clear();

    bool isEmpty() {
        return elements == 0;
    }
    
    void Swap(DoublyLL& list2);

    friend ostream& operator<< (ostream& os, const DoublyLL& list);
};


DoublyLL :: DoublyLL(const DoublyLL& list) {
    Node* listHead = list.head;
    Node* listTail = list.tail;

    Node* newNode = new Node(listHead->data);
    listHead = listHead -> next;

    head = tail = newNode;

    while (listHead != nullptr) {
        Node* temp = new Node (listHead -> data);
        listHead = listHead -> next;

        tail -> next = temp;
        temp -> prev = tail;
        tail = temp;
    }
    elements = list.elements;
}

DoublyLL& DoublyLL :: operator= (const DoublyLL& list) {
    if(this == &list) return *this;
    
    delete head; 
    delete tail;

    Node* listHead = list.head;
    Node* lsitTail = list.tail;

    Node* newNode = new Node(listHead -> data);
    listHead = listHead -> next;

    head = tail = newNode;

    while(listHead != nullptr) {
        Node* temp = new Node(listHead -> data);
        tail -> next = temp;
        temp -> prev = tail;
        tail = temp;

        listHead = listHead -> next;
    }

    elements = list.elements; 
    return *this;
}

ostream& operator<< (ostream& os, const DoublyLL& list) {
    Node* cur = list.head;
    
    while (cur != nullptr) {
        os << cur -> data << " ";
        cur = cur -> next;
    } os << endl;

    os << "Head Data: " << list.head -> data << endl;
    cout << "Tail Data: " << list.tail -> data << endl;
    cout << "Size: " << list.elements << endl;
    
    return os;
}

void DoublyLL :: insert(const int val) {
    if(head == nullptr) {
        insertAtHead(val);
        return;
    }

    Node* newNode = new Node(val);
    
    tail -> next = newNode;
    newNode -> prev = tail;
    tail = newNode;
    elements++;
}

void DoublyLL :: insertAtHead(const int val) {
    if(head == nullptr) {
        Node* newNode = new Node(val);
        head = tail = newNode;
    }
    else {
        Node* newNode = new Node(val);
        newNode -> next = head;
        head -> prev = newNode;
        head = newNode;
    }
    elements++;
}

bool DoublyLL :: search(const int val) {
    Node* cur = head;
    while (cur != nullptr) {
        if(cur -> data == val) return true;
        
        cur = cur -> next;
    }
    return false;
}

bool DoublyLL :: remove(const int val) {
    Node* pre = nullptr;
    Node* cur = head;

    // if the given val is equal to the head node data then do removeHead.
    if(head -> data == val) {
        head = head -> next;

        head -> prev = nullptr;
        cur -> next = nullptr;

        delete cur;
        
        elements--;
        return true;
    }
    // condition for other Node's data
    else{
        // iterate till 2nd last node  
        while (cur -> next != nullptr) {
            if(cur -> data == val) {
                
                pre -> next = cur -> next;
                cur -> next -> prev = pre;
                
                elements--;
                delete cur;
                
                return true;
            }
            pre = cur;
            cur = cur -> next;
        }
        //Condition for deleting tail Node
        
        // imp --> cur is at tail node
        tail = pre;
        tail -> next = nullptr; // or tail -> next = cur -> next;
        
        elements--;
        delete cur;

        return true;
    }
    return false;
} 

bool DoublyLL :: removeHead(int& headData) {
    if(head == nullptr) {
        headData = -1;
        return false;
    } 

    Node* cur = head;
    headData = head -> data;
    
    head = head -> next;
    
    elements--;
    delete cur;

    return true;
}

void DoublyLL :: clear() {
    if(head == nullptr) {
        tail -> prev = nullptr;
        return;
    }

    Node* cur = head;
    head = head -> next;
    head -> prev = nullptr;

    clear();
    
    delete cur;

    // while (head != nullptr) {

    //     Node* cur = head;
    //     head = head -> next;
    //     head -> prev = nullptr;
        
    //     // condition for when head -> next equal to the next of tail Node which is nullptr;
    //     if(head -> next == tail -> next) {
    //         tail -> next = nullptr;
    //         tail -> prev = nullptr;
    //     }
        
    //     // Destructor of cur will automatically done this
    //     // cur -> next = nullptr;
    //     // cur -> prev = nullptr;

    //     elements--;
    //     delete cur;
    // }
}

void DoublyLL :: Swap(DoublyLL& list2) {
    // store the head and tail of list1 in tempHead & tempTail
    Node* tempHead = head;
    Node* tempTail = tail;
    
    // Pointing the head & tail of list 1 to list 2 head & tail
    head = list2.head;
    tail = list2.tail;
    

    list2.head = tempHead;
    list2.tail = tempTail;

    int temp = elements;
    elements = list2.elements;
    list2.elements = temp;
}
```

{% endcode %}

<details>

<summary>Insert at the Head &#x26; Tail</summary>

```cpp
#include<iostream>
using namespace std;

class Node{
    public:
        int data; Node* pre; Node* next;
        Node(int d) : data(d), pre (NULL), next (NULL) {}
};

void insertAtHead(Node* &head, int d) {
    Node* temp = new Node(d);
    temp-> next = head;
    head-> pre = temp;
    head = temp; 
}

void insertAtTail(Node* &tail, int d) {
    Node* temp = new Node(d);
    tail-> next = temp;
    temp-> pre = tail;
    tail = temp;
}

void print(Node* head) {
    while(head != NULL) {
        cout << head-> data << ' ';
        head = head-> next;
    } cout << '\n';
}

int getLength(Node* head) {
    int count = 0;
    while(head != NULL) {
        count++;
        head = head->next;
    }
    return count;
}

int main(){
    Node* node1 = new Node(10);
    Node* head = node1;
    Node* tail = node1;

    insertAtHead(head, 8); insertAtHead(head, 4); insertAtHead(head, 6); insertAtHead(head, 1);

    // inserting at the tail
    insertAtTail(tail, 19);
    print(head);
    cout << endl << "Head: " << head-> data << ", Tail: " << tail->data << '\n';

    int len = getLength(head);
    cout << "length: " << len << '\n';
}
```

</details>

<details>

<summary>Insert at any Position</summary>

```cpp
#include<iostream>
using namespace std;

class Node{
    public:
        int data; Node* pre; Node* next;
        Node(int d) : data(d), pre(NULL), next(NULL) {}
};

void insertAtHead(Node* &head, Node* &tail, int d) {
    if(head == NULL){
        Node* temp = new Node(d);
        head = temp;
        tail = temp;
    }
    else{
        Node* temp = new Node(d);
        temp ->next = head;
        head->pre = temp;
        head = temp;
    }
}

void insertAtTail(Node* &head, Node* &tail, int d) {
    if(tail == NULL){
        Node* temp = new Node(d);
        head = temp;
        tail = temp;
    }
    Node* temp = new Node(d);
    tail ->next = temp;
    temp ->pre = tail;
    tail = temp;
}

void insertAtAnyPos(Node* &head, Node* &tail, int d, int pos) {
    
    if(pos == 1){
        insertAtHead(head, tail, d);
        return;
    }
    
    Node* nodetoInsert = new Node(d);
    Node* temp = head;
    int count = 1;

    while(count++ < pos-1){
        temp = temp->next;
    }

    if(temp->next == NULL){
        insertAtTail(head, tail, d);
        return ;
    }

    nodetoInsert -> next = temp -> next;
    temp -> next -> pre = nodetoInsert;
    temp -> next = nodetoInsert;
    nodetoInsert->pre = temp;
}

void print(Node* head) {
    while(head != 0){
        cout << head -> data << ' ';
        head = head->next;
    } cout << '\n'; 
}

int main() {
    Node* head = NULL;
    Node* tail = NULL;
  
    insertAtHead(head, tail, 8); 
    insertAtHead(head, tail, 4);
    insertAtHead(head, tail, 6); 
    insertAtHead(head, tail, 1); 
    insertAtTail(head, tail, 10);
    print(head);
    
    // insert node at the head
    insertAtAnyPos(head, tail, 92, 1);
    print(head);
 
    // insert node at any random position
    insertAtAnyPos(head, tail, 124, 3);
    print(head);

    // insert node at the end
    insertAtAnyPos(head, tail, 32, 8);
    print(head);
    
    cout << "\nHead: " << head->data << "\nTail: " << tail->data << endl;
}
```

</details>

<details>

<summary>Delete at any Position</summary>

```cpp
#include<iostream>
using namespace std;

class Node{
    public:
        int data; 
        Node* pre; // previous Node 
        Node* next; // Next Node
        Node(int d) : data(d), pre(NULL), next(NULL) {}

        ~Node() {
            cout << "Memory is free for the Node with Data: " << this-> data << "\n"; 
        }
};

void insertAtHead(Node* &head, Node* &tail, int d) {
    if(head == NULL){
        Node* temp = new Node(d);
        head = temp;
        tail = temp;
    }
    else{
        Node* temp = new Node(d);
        temp ->next = head;
        head->pre = temp;
        head = temp;
    }
}

void insertAtTail(Node* &head, Node* &tail, int d) {
    if(tail == NULL){
        Node* temp = new Node(d);
        head = temp;
        tail = temp;
    }
    Node* temp = new Node(d);
    tail ->next = temp;
    temp ->pre = tail;
    tail = temp;
}

void deleteAtAnyPos(Node* &head, Node* &tail, int pos) {
    // Condition for deleting starting Node
    if(pos == 1){
        Node* temp = head;
        head = head->next;
        head->pre = NULL;
        temp ->next = NULL;
        delete temp;
    }
    // Condition for Deleting middle or ending Node
    else{
        Node* previous = NULL;
        Node* cur = head;
        int count = 1;
        while(count++ < pos){
            previous = cur;
            cur = cur-> next;
        }
        previous -> next = cur -> next;
        tail = previous;
        cur -> pre = NULL;
        delete cur;
    }
}

void print(Node* head) {
    while(head != 0){
        cout << head -> data << ' ';
        head = head->next;
    } cout << "\n\n"; 
}

int getLength(Node* head){
    int count = 0;
    while(head != NULL){
        head = head ->next;
        count++;
    }
    return count;
}

int main() {
    Node* head = NULL;
    Node* tail = NULL;
  
    insertAtHead(head, tail, 8); 
    insertAtHead(head, tail, 4);
    insertAtHead(head, tail, 6); 
    insertAtHead(head, tail, 1); 
    insertAtTail(head, tail, 10);
    insertAtTail(head, tail, 11);
    print(head);
    
    // delete starting Node
    deleteAtAnyPos(head, tail, 1);
    print(head);
    
    int len = getLength(head);
    // delete middle Node
    deleteAtAnyPos(head, tail, len/2);
    print(head);

    len = getLength(head);
    // delete ending Node
    deleteAtAnyPos(head, tail, len);
    print(head);
    
    cout << "Head: " << head->data << "\nTail: " << tail->data;

    return 0;
}
```

</details>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dsa-cpp.gitbook.io/nafees/linked-list/whats-linked-list-and-implementation/doubly-linked-list.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.