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;

}

Iterative Search in Linked List in C++

 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;

} 

Merge Sort using divide and conquer approach (With Mistakes noted! this time!)

When writing merge sort next time, ask yourself:

✅ Did I divide properly using si, mid, ei?

✅ Did I initialize i=si and j=mid+1 in merge()?

✅ Did I correctly loop with i <= mid and j <= ei?

✅ Did I merge into a temp vector and copy back?

#include <iostream>

#include <vector>

using namespace std;

void printArray(int arr[], int n) {

    for(int i =0; i<n; i++) {

        cout << arr[i] << " ";

    }

    

    cout << endl;

}

void merge(int arr[], int si, int mid, int ei) {

    int i = si; // Major part of mistake

    int j = mid+1; // Major part of mistake

    vector<int> temp;    // Did Mistake this line 

    

    

    // Merge the two sorted halves

    while (i <= mid && j <= ei) { // Did Mistake this line 

        

        if(arr[i] < arr[j]) {

            temp.push_back(arr[i++]);

        } else {

            temp.push_back(arr[j++]);

        }

    }

    

    

    // Copy remaining elements

    while(i <= mid) {  // Did Mistake this line 

        temp.push_back(arr[i++]);

    }

    

    

    while(j <= ei) {  // Did Mistake this line 

        temp.push_back(arr[j++]);

    }

    // Copy temp back to array

    

    for(int idx = si, x=0; idx<=ei; idx++) {

        arr[idx] = temp[x++];

    }

    

}

void mergeSort(int arr[], int si, int ei) {

    if(si >= ei) {

        return;

    }

    

    int mid = si + (ei-si)/2;

    mergeSort(arr, si, mid);

    mergeSort(arr, mid+1, ei);

    merge(arr, si, mid, ei);

}

int main() {

    int arr[] = {1,4, 7,2, 10};

    int n = sizeof(arr)/sizeof(int);

    

    cout << "Original array: ";

    printArray(arr, n);

    

    

    mergeSort(arr, 0, n-1);

    

    cout << "Sorted Array: ";

    printArray(arr, n);

    return 0;

}

Bubble Sort in C++

#include <iostream>

using namespace std;

void print(int arr[], int n) {

    for(int i=0; i<n; i++) {

        cout << arr[i] << " ";

    }

    

    cout << endl;

}

void bubbleSort(int arr[], int n) {

    

    // outer loop

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

        

        // inner loop

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

            if(arr[j] > arr[j+1]) { 

                swap(arr[j], arr[j+1]);

            }

        }

    }

    

    

    print(arr, n);

}

int main() {

    int arr[] = {5,3 ,2,4,1};

    int n = sizeof(arr)/sizeof(int);

    

    

    bubbleSort(arr, n);

    

    

    return 0;

}

Binary Search in C++

 #include <iostream>

using namespace std;

//  BInary Search

int binarySearch(int *arr, int key, int n) {

    int si=0;

    int ei=n-1;

    

    

    while(si <= ei) {

        int mid = si + (ei-si)/2;

        if(key == arr[mid]) {

            return mid;

        } else if(key >= arr[mid]) {

            si = mid+1; // right half

        } else {

            si = mid-1; // left half

        }

    }

    

    return -1;

}

int main() {

    int arr[] = {5, 4, 2, 1, 7};

    int n = sizeof(arr)/sizeof(int);

    

    cout << binarySearch(arr, 2, n);

 

    return 0;

}

Factorial of N in C++

 

#include <iostream>

using namespace std;

// Factorial of N

int factorial(int n) {

    if (n == 0) {

        return 1;

    }

    

    return n * factorial(n-1);

}

int main() {

   

    cout << factorial(5);

    return 0;

}

Sum of N numbers in C++

 

#include <iostream>

using namespace std;

// Sum of N numbers in C++

int sum(int n) {

    if(n == 0) {

        return n;

    }

    

    return n + sum(n-1);

}

int main() {

   

    cout << sum(5);

    return 0;

}