#include <iostream>
using namespace std;

class Node
{
    public:
        string name;
        Node *next;
        
        Node (string inputName)
        {
            this->name = inputName;
            next = NULL;
        }    

        void addNext(Node *input)
        {
            next = input; 
        }
};

void showAll(Node *pointer)
{
    int index = 0;
    while (pointer != NULL)
    {
        cout << index << " " << pointer << endl;
        pointer = pointer->next;
        index++;
    }
    cout << "-------------" << endl;
}

//DELETE NODE
void deleteNode(Node *&head, Node *target)
{
    //delete the head
    if (head == target)
    {
        head = head->next;
        return;
    }

    //delete insdie chain
    Node *temp = head;
    while (temp->next != target && temp != NULL)
    {
        temp = temp->next;
    }

    if (target->next != NULL)temp->next = temp->next->next; 
}


//insert node between node i and i+1, i >= 0
void insertNode(Node *&head, Node *target, int index) 
{
    if (index == -1) //insert behind head
    {
        target->next = head;
        head = target;
        return;
    }
    
    //insert inside chain
    Node *temp = head;
    for (int i = 0; i < index; i++)
    {
        temp = temp->next;
        if (temp == NULL) return;
    }
    
    target->next = temp->next; 
    temp->next = target;
}

int main()
{
    Node ex1("a"), ex2("bb"), ex3("ccc"), ex4("dddd");
    Node *head = &ex1;

    ex1.addNext(&ex2);
    ex2.addNext(&ex3);
    ex3.addNext(&ex4);
    showAll(head);

    //delete
#if 0
    Node *target1 = &ex1;
    deleteNode(head, target1);
    showAll(head);
#endif

    //insert
#if 0
    Node exx("aloha");
    Node *target2 = &exx; 
    cout << "@@ " << target2 << endl;
    insertNode(head, target2, 3);
    showAll(head);
#endif 
}