#include <iostream>
using namespace std;

struct Node
{
  int data;
  Node *next;
public:
  Node()
  {
    data = 0;
    next = nullptr;
  }
  Node(int val)
  {
    data = val;
    next = nullptr;
  }
};

/*********************************************************************************/

class Linkedlist 
{
    Node *head ;
    Node *tail ;
    size_t sz;
    Node* make_node(int val);
  public:
    
    Linkedlist();
    ~Linkedlist();
    
    void insert(int val);
    void insert_front(int val);
    void insert_back(int val);
    void insert_after(Node *p, int val);
    
    int remove(int val);
    int remove_front();
    int remove_back();
    
    bool is_empty();
    
    Node *get_head();
    Node *get_tail();
    
    void display();
    
};

/*********************************************************************************/

Linkedlist :: Linkedlist()
{
    head = tail = nullptr;               // initialize all the values of class to a good value
    sz = 0;                   // initially size of the Linkedlist is ZERO after the size increases accordingly
}

Linkedlist :: ~Linkedlist()
{
    while(head != nullptr)   // till head == nullptr the loop continues
    {
        remove_front();      // it will delete the front
    }
}

Node *Linkedlist :: make_node(int val)
{
   Node* new_node = new Node(val);
   if(new_node == nullptr)
   {
     exit(0);
   }
   return new_node;
}
void Linkedlist ::  insert(int val)
{
    if(head == nullptr)
    {
        head = tail = make_node(val);
        ++sz;
        display();
    }
    else
    {
        Node *prev, *curr;
        for(prev = nullptr, curr = head; curr!=nullptr && curr->data < val; prev = curr, curr = curr->next)
        ;
        insert_after(prev, val);
    }
}

void Linkedlist ::  insert_front(int val)
{
      Node *new_node = make_node(val);
      if(head == nullptr)
      {
        head = tail = new_node;
      }
      else
      {
        new_node->next = head;
        head = new_node;
      }
      ++sz;
      display();
}

void Linkedlist ::  insert_back(int val)
{
     Node *new_node = make_node(val);
     {
       if(tail == nullptr)
       {
         head = tail = new_node;
       }
       else
       {
         tail->next = new_node;
         tail = tail->next;
       }
     }
     ++sz;
     display();
}

void Linkedlist :: insert_after(Node *prev, int val)
{
  /*******************************************************************************
  1.
  
  
  
  
  ********************************************************************************/
  
  
  
   if(prev == nullptr)
   {
      insert_front(val);
   }
   else if(prev == tail)
   {
      insert_back(val);
   }
   else
   {
      Node *p = make_node(val);
      p->next = prev->next;
      prev->next = p;
      ++sz;
   }
}

int Linkedlist ::  remove(int val)
{
  /***********************************************************************
  Before removing any value check the initial conditions
  1. check wheather the list is empty..?
  2. what if the given value is absent..?
  3. what if the node with given value is at head position..?
  4. what if the node with given value is at tail position..?
  5. What if given value is somewhere at middle position..?
  
  **********************************************************************/
    if(is_empty())
  {
    cout<<"Attempting to remove from an empty list";
    return -1;
  }
  else
  {
    Node *prev, *curr;
    for(prev== nullptr, curr = head; curr!= nullptr && curr->data != val; prev = curr, curr = curr->next)
    ;
    {
      if(curr == nullptr)
      {
        cout<<"Val is not present is the list";
        return -1;
      }
      else
      {
        //Now remove the curr node
        if(curr == head)
        {
          return remove_front();
        }
        else if(curr == tail)
        {
          return remove_back();
        }
        else
        {
          int  ret_val = curr->data;
          prev->next = curr->next;
          delete curr;
          if(prev->next == nullptr)
          {
            tail = prev;
          }
          --sz;
          display();
          return ret_val;
        }
      }
    }
  }
}
int Linkedlist ::  remove_front()
{
  if(curr == nullptr)
  {
    cout<<"Attempting to remove from an empty list";
    return -1;
  }
  else
  {
    int ret_val = head->data;
    if(head == tail)
    {
      delete head;
      head = tail = nullptr;
    }
    else
    {
      Node *temp = head;
      head = head->next;
      delete temp;
    }
    return ret_val;
    --sz;
    display();
  }
}

int Linkedlist ::  remove_back()
{
  if(curr == nullptr)
  {
    cout<<"Attempting to remove from an empty list";
    return -1;
  }
  else
  {
    int ret_val = head->data;
    if(head == tail)
    {
      delete head;
      head = tail = nullptr;
    }
    else
    {
      Node *prev, *curr;
      for(prev = nullptr, curr = head; curr != tail && curr->data != val; prev = curr, curr = curr->next)
      ;
      {
        
      }
      while(head != nullptr)
    }
    return ret_val;
    --sz;
    display();
  }
}

bool Linkedlist ::  is_empty()
{
  if(head == nullptr)
  {
    return true;
  }
  else
    return false;
}

Node Linkedlist ::  *get_head()
{
  return nullptr;
}
Node Linkedlist ::  *get_tail()
{
  return nullptr;
}

void Linkedlist :: display()
{
  
}

/*********************************************************************************/

int main() 
{
    
    return 0;
}

/*********************************************************************************/