#include <iostream>
#include "assert.h"
using namespace std;
 
struct Item;
 
struct List
{
    Item* first;
    Item* last;
};
 
struct Item
{
    Item* prev;
    string name;
    Item* next;
};
 
void clear (List & a)
{
    a.first = NULL;
    a.last = NULL;
}
 
void link(List & a, Item* before, Item* fresh, Item* after)
// a - seznam do ktereho vkladame
// fresh - nove vkladany prvek (musi existovat, nesmi byt v zadnem seznamu)
// before - ukazatel na predchozi prvek ( before == nullptr => fresh bude prvni)
// after - ukazatel na nasledujici prvek ( after == nullptr => fresh bude posledni)
{
    fresh->prev = before;
    fresh->next = after;
 
    if (before != nullptr)
        before->next = fresh; // nekdo je pred
    else
        a.first = fresh; // jsme prvni
 
    if (after != nullptr)
        after->prev = fresh;
    else
        a.last = fresh;
}
 
void insertFirst(List& a, string name0)
{
    Item* t = new Item; // novy prvek
    t->name = name0;
    link (a, nullptr, t, a.first); 
    // vlozit do seznamu a
    // predchozi je null
    // novy prvek t
    // nasledujici za novym prvkem je dosud prvni prvek
}
 
void insertLast (List& a, string name0)
{
    Item* t = new Item; // novy prvek
    t->name = name0;
    link(a, a.last, t, nullptr);
}
 
void insertBefore (List& a, Item* target, string name0)
// vkladame pred target
// target musi existovat a musi byt v nasem seznamu a
{
    Item* t = new Item; // novy prvek
    t->name = name0;
    assert(target != nullptr);
    link(a, target->prev, t, target);
}
 
void insertAfter (List& a, Item* target, string name0)
{
    Item* t = new Item; // novy prvek
    t->name = name0;
    assert(target != nullptr);
    link(a, target, t, target->next);
}
 
void print (List& a)
{ 
    Item* p = a.first;
    if (p == nullptr)
    {
        cout << "seznam je prazdny" << endl;
    }
    while (p != nullptr)
    {
        cout << p->name << endl;
        p = p->next;
    }
    cout << endl;
}
 
Item* prvek(List& a, int inx) // inx == 0, prvni prvek
{
    Item* p = a.first;
    while (inx > 0 && p != nullptr) {
        inx--;
        p = p->next;
    }
    return p;
}
 
Item* find(List& a, string name0)
{
    Item* p = a.first;
    while (p != nullptr && p->name != name0) 
    {
        p = p->next;
    }
    return p;
}
 
void remove(List& a, Item* t)
// odstranit t ze seznamu a
{
    if (t != nullptr)
    {
        Item* before = t->prev;
        Item* after = t->next;
 
        if (before != nullptr)
            before->next = after;
        else
            a.first = after;
 
        if (after != nullptr)
            after->prev = before;
        else
            a.last = before;
 
        t->prev = nullptr;
        t->next = nullptr;
        delete t;
    }
}
 
List seznam;
 
int main()
{
    clear(seznam);
    insertFirst(seznam, "cervena");
    insertLast(seznam, "zelena");
    insertBefore(seznam, seznam.last, "oranzova");
 
    Item* t = prvek(seznam, 1); // index 1 ... druhy prvek
    insertAfter(seznam, t, "modra");
 
    Item* m = find(seznam, "modra");
    if (m != nullptr)
       insertBefore(seznam, m, "zluta");
 
    print(seznam);
 
    while (seznam.first != nullptr)
    {
        remove(seznam, seznam.last);
    }
    print(seznam);
}