Linked List - Part 1 (Includes all operations)

#include <iostream>

#include <vector>

using namespace std;

class Node {

public:

    int data;

    Node* next;

    Node(int val) {

        data = val;

        next = NULL;

    }

    ~Node(){

       

        cout << "~Node " << data << endl;

        if(next != NULL) {

            delete next;

            next = NULL;

        }

    }

};

class List {

    Node* head;

    Node* tail;

public:

    // constructor

    List() {

        head = NULL;

        tail = NULL;

    }

    // Destructor

    ~List()

    {   cout << "~List\n";

        if(head != NULL) {

            delete head;

            head = NULL;

        }

    }

    void push_front(int val) {

        Node* newNode = new Node(val); // dynamic allocation of Node

        // OR Node* newNode(val); // static allocation of Node creation method

        if(head == NULL) {

            head = tail = newNode;

        } else {

            newNode->next = head; // points towards new Node head

            head = newNode; // now head points towards newNode

        }

    }

    void push_back(int val) {

        Node* newNode = new Node(val);

        if(head == NULL) {

            head = tail = newNode;

        } else {

            tail->next=newNode;

            tail = newNode;

        }

    }

    void printList() {

        Node* temp = head;

        while (temp != NULL) {

            cout << temp-> data << " -> ";

            temp = temp->next;

        }

        cout << "NULL\n";

    }

    // 1->2->3 pos = 25

    void insert(int val, int pos) {

        Node* newNode = new Node(val);

        Node* temp = head;

        for(int i=0; i<pos-1; i++) {

            if(temp == NULL) {

                cout << "position is INVALID\n";

                return;

            }

            temp = temp->next;

        }

        // temp is now at pos-1 i.e. prev/left

        newNode->next = temp->next;

        temp->next = newNode;

    }

    void pop_front() {

        if(head == NULL) {

            cout << "LL is empty\n";

            return;

        }

        Node* temp = head;

        head = head->next;

        temp->next = NULL;

        delete temp;

    }

    void pop_back() {

        Node* temp = head;

        while(temp->next->next != NULL) {

            temp = temp->next;

        }

        temp->next = NULL; // temp = tail's prev

        delete tail;

        tail = temp;

    }

    int searchItr(int key) {

        Node* temp = head;

        int idx = 0;

        while(temp != NULL) {

            if(temp->data == key) {

                return idx;

            }

            temp = temp->next;

            idx++;

        }

        return -1;

    }

    int helper(Node* temp, int key) {  // Node* head in some articles if you read...

        if(temp == NULL) { // base case

            return -1;

        }

        if(temp->data == key) {

            return 0;

        }

        int idx = helper(temp->next, key);

        if(idx == -1) {

            return -1;

        }

        return idx+1;

    }

    int searchRec(int key) {

        return helper(head, key);

    }

    void reverse() {

        Node* curr = head;

        Node* prev = NULL;

        tail = head;

        while(curr != NULL) {

            Node* next = curr->next;

            curr->next = prev;

            //updations for next itr

            prev = curr;

            curr = next;

        }

        head = prev;

    }

    int getSize() {

        int sz = 0;

        Node* temp = head;

        while(temp != NULL) {

            temp = temp->next;

            sz++;

        }

        return sz;

    }

    void removeNth(int n) { // O(N); SC: O(1)

        int size = getSize();

        Node* prev = head;

       

        for(int i=1; i<(size-n); i++) { // i=size-n => prev => deletion node prev

            prev = prev->next; // phele temp bolte the, ab prev boldiya

        }

        Node* toDel = prev->next;

        cout << "going to delete : " << toDel->data << endl;

        prev->next = prev->next->next;

    }

};

int main() {

    List ll;

   

    ll.push_front(5);

    ll.push_front(4);

    ll.push_front(3);

    ll.push_front(2);

    ll.push_front(1);

    ll.printList();  // 1->2->3->4->5->null

       

   

    ll.removeNth(2);

    ll.printList(); // 1->2->3->5->null

    // // // // // //ll.reverse();

    // // // // // //ll.printList();

   

   

   

   

    // // // // //  cout << "Found at Idx: " << ll.searchRec(4) << endl;

   

   

   

    // // // // cout << "Found at Idx: " <<  ll.searchItr(4) << endl;

   

   

    // // // ll.pop_back();

    // // // ll.printList();

   

   

    // // ll.pop_front();

    // // ll.printList();

    // ll.push_back(4);

    // ll.push_back(5);

    // ll.printList(); // 1->2->3->4->5->null

    // ll.insert(100, 2);

    // ll.printList(); // 1->2->100->3->4->5->null

    return 0;

}