DoublyLinkedList

#include <iostream>
using namespace std;
class Node {
public:
  int data;
  Node *next;
  Node *prev;
  Node(int d) {
    this->data = d;
    this->prev = NULL;
    this->next = NULL;
  }
  ~Node()
  {
    int value = this->data;
    while (this->next != NULL) {
      delete next;
      this->next = NULL;
    }
    cout << "Memort is free for value " << value << endl;
  }
};
// find length
int listSize(Node *&head) {
  Node *temp = head;
  int len = 0;
  while (temp != NULL) {
    len++;
    temp = temp->next;
  }
  return len;
}
// insert at head
void insertAtHead(Node *tail, Node *&head, int data) {
  if (head == NULL) {
    Node *temp = new Node(data);
    head = temp;
    tail = temp;
  } else {
    Node *temp = new Node(data);
    temp->next = head;
    head->prev = temp;
    head = temp;
  }
}
// at tail
void insertAtTail(Node *&tail, Node *&head, int data) {
  if (tail == NULL) {
    Node *temp = new Node(data);
    tail = temp;
    head = temp;
  } else {
    Node *temp = new Node(data);
    tail->next = temp;
    temp->prev = tail;
    tail = temp;
  }
}
// insesrt at any pos
void insertAtPos(Node *&tail, Node *&head, int data, int pos) {
  if (pos == 1) {
    insertAtHead(tail, head, data);
    return;
  }

  Node *temp = head;
  int cnt = 1;

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

  // inserting at Last Position
  if (temp->next == NULL) {
    insertAtTail(tail, head, data);
    return;
  }

  // creating a node for d
  Node *nodeToInsert = new Node(data);

  nodeToInsert->next = temp->next;
  temp->next->prev = nodeToInsert;
  temp->next = nodeToInsert;
  nodeToInsert->prev = temp;
}
//deletion
void deleteNode(Node *&tail, Node *&head, int pos)
{
  if(pos==1)
  {
    Node *temp = head;
    temp->next->prev = NULL;
    head=temp->next;
    temp->next=NULL;
    delete temp;
  }
  else
  {
    Node *curr = head;
    Node *prev = NULL;
    int cnt = 1;
    while (cnt < pos) {
      prev = curr;
      curr = curr->next;
      cnt++;
    }
    curr->prev=NULL;
    prev->next=curr->next;
    curr->next=NULL;
    delete curr;

    Node *temp = head;
    while (temp->next != NULL) {
      temp = temp->next;
    }
    tail = temp;
    temp->next = NULL;
    delete temp->next;
  }
}
// print
void print(Node *&head, Node *&tail) {
  Node *temp = head;
  while (temp != NULL) {
    cout << temp->data << " ";
    temp = temp->next;
  }
  cout << endl;
}

int main() {
  // Node *node1 = new Node(10);
  // cout << node1->data << endl;
  // cout << node1->prev << endl;
  // cout << node1->next << endl;

  Node *head = NULL;
  Node *tail = NULL;
  print(head,tail);
  // insertAtHead(tail,head,20);
  insertAtTail(tail, head, 20);
  print(head,tail);
  insertAtPos(tail, head, 15, 2);
  print(head,tail);
  insertAtPos(tail, head, 2, 1);
  print(head,tail);
  insertAtPos(tail, head, 200, 4);
 print(head,tail);
  insertAtPos(tail, head, 250, 5);
print(head,tail);
  cout << "Head " << head->data << endl;
  cout << "Tail " << tail->data << endl;
  deleteNode(tail,head,5);
  print(head,tail);
  cout << "Head " << head->data << endl;
  cout << "Tail " << tail->data << endl;
  return 0;
}