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