#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>

using namespace std;

template<typename T>
class Node
{
public:
    Node();
    Node(T value, Node<T>* nextNode);
    T data;
    Node<T>* next;
};

template<typename T>
class LinkedList
{
public:
    LinkedList();
    Node<T>* getHead() const { return head };  // return the head poiter
    Node<T>* getTail() const { return tail };  // returns the tail pointer
    void listAppend(T value);  // inserts an element at the end of the list
    void listPrepend(T value); //inserts a n element at the head of the list
    void insertAfter(Node<T>* curNode, T value); // Insert value after the curNode
    void removeAfter(Node<T>* curNode); // remove Node after CurNode
    void removeHead();  // Removes the first element
    void removeTail();  // removes the last element
    void printList() const;  // print the elements of the linked list
private:
    Node<T>* head;
    Node<T>* tail;
};

template<typename T>
void LinkedList<T>::printList() const
{
    Node<T>* temp = head;  // or temp = head
    while (temp != NULL)
    {
        std::cout << temp->data << " ";
        temp = temp->next;
    }
    std::cout << "\n";
}

template<typename T>
void LinkedList<T>::removeAfter(Node<T>* curNode)
{
    if (curNode->next == NULL)
        std::cout << "Cannot remove Node\n";
    else
    {
        Node<T>* temp = curNode->next;
        curNode->next = temp->next;
        delete temp;
    }
}

template<typename T>
void LinkedList<T>::removeTail()
{
    Node<T>* temp = head;
    while (temp->next != tail) // move until reaching the node
        temp = temp->next;        // before the tail node.
    temp->next = NULL;
    delete tail;
    tail = temp;
}

template<typename T>
void LinkedList<T>::removeHead()
{
    if (head != NULL)
    {
        Node<T>* temp = head;
        head = head->next;
        delete temp;
    }
}

template<typename T>
void LinkedList<T>::insertAfter(Node<T>* curNode, T value)
{
    if (head == NULL)  // empty list, insert at the head
    {
        Node<T>* newNode = new Node<T>(value, NULL);
        head = newNode;
        tail = newNode;
    }
    else if (curNode == tail)  //insert after the tail
    {
        Node<T>* newNode = new Node<T>(value, curNode->next);
        tail->next = newNode;
        tail = newNode;
    }
    else // insert in the middle
    {
        Node<T>* newNode = new Node<T>(value, curNode->next);
        curNode->next = newNode;
    }
}

template<typename T>
void LinkedList<T>::listPrepend(T value)
{
    Node<T>* temp = new Node<T>(value, NULL);
    if (head == NULL) // list empty
    {
        head = temp;
        tail = temp;
    }
    else
    {
        temp->next = head;
        head = temp;
    }
}

template<typename T>
void LinkedList<T>::listAppend(T value)
{
    Node<T>* newNode = new Node<T>(value, NULL);
    if (tail == NULL)
        head = tail = newNode;
    else
    {
        tail->next = newNode;
        tail = newNode;
    }
}