Doubly Linked List

main.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;
}

DoublyLinkedList.h

#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;
}

Insert at the Head & Tail

#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';
}

Insert at any Position

#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;
}

Delete at any Position

#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;
}