#include <iostream>
using namespace std;
 
struct Item 
{
    string name;
    Item* next;
};
 
void insertFirst(Item*& first, string name0)
{
    Item* p=new Item;
    p->name = name0;
    p->next = nullptr;
 
    p->next = first;
    first = p;
}
 
void insertLast(Item*& first, string name0)
{
    Item* p = new Item;
    p->name = name0;
    p->next = nullptr;
 
    if (first == nullptr)
    {
        first = p;
    }
    else {
        Item* t = first;
        while (t->next != nullptr) t = t->next;
        t->next = p;
    }
}
 
void insertNext (Item* target, string name0)
{
    Item* p = new Item;
    p->name = name0;
    p->next = target->next;
 
    target->next = p;
}
 
void insertPrev(Item * & first, Item* target, string name0)
{
    Item* p = new Item;
    p->name = name0;
    p->next = target->next;
 
    if (target == first)
    {
        first = p; // novy prvek je prvni
        p->next = target; // za novym prvkem je target
    }
    else
    {
        Item* t = first;
        while (t->next != target) t = t->next; // hledam predchudce prvku target
        if (target != nullptr)
        {
            t->next = p; // za t bude novy prvek
            p->next = target; // za novym prvkem je target
        }
    }
}
 
void remove (Item*&first, string name0)
{
    Item* p = first;
    Item* t = nullptr;
    while (p != nullptr && p->name != name0) 
    {
        t = p;  
        p = p->next;
    }
    if (p != nullptr)
    {
        if (t == nullptr)
            first = p->next;
        else
            t->next = p->next;
        cout << "mazu " << p->name << endl;
        delete p;
    }
}
 
Item* find(Item* first, string name0)
{
    Item* p = first;
    while (p != nullptr && p->name != name0)p = p->next;
    return p;
}
 
void print(Item* p)
{
    if (p == nullptr)
        cout << "seznam je prazdny" << endl;
    while (p != nullptr)
    {
        cout << p->name << endl;
        p = p->next;
    }
    cout << endl;
}
 
Item* list = nullptr;
Item* list2 = nullptr;
 
int main()
{
    insertFirst(list2, "mikes");
    insertFirst(list2, "bobes");
 
    insertFirst(list, "bob");
    insertFirst(list, "karlik");
    insertLast(list, "pepa");
    print(list);
 
    cout << "druhy seznam" << endl;
    print(list2);
    Item* b = find(list, "bob");
    if (b != nullptr)
    { 
        cout << "nasel " << b->name << endl;
        insertPrev(list, b, "Kouzelnik");
        insertNext(b, "Bobek");
        b->name = "Bob";
    }
 
    else
        cout << "nenasel " << endl;
 
    print(list);
    remove(list, "Bob");
    print(list);
    remove(list, "karlik");
    print(list);
    remove(list, "pepa");
    print(list);
 
    while (list != nullptr)
        remove (list, list->name);
 
    print(list);
 
    cout << "O.K."<< endl;
}