#include <iostream>
#include<string>
using namespace std;
struct TListenKnoten
{
	int data;
	TListenKnoten *next;
	TListenKnoten *prev;
};
void hinten_anfuegen(TListenKnoten *&anker, const int wert)
{
	TListenKnoten *neuer_eintrag = new TListenKnoten;
	neuer_eintrag->data = wert;
	neuer_eintrag->next = nullptr;
	neuer_eintrag->prev = nullptr;
	if (anker == nullptr) {
		anker = neuer_eintrag;
	}
	else
	{
		TListenKnoten *ptr = anker;
		while (ptr->next != nullptr)
		{
			ptr = ptr->next;
		}
		ptr->next = neuer_eintrag;
		ptr->next->prev = ptr;
	}
}
string liste_als_string(TListenKnoten * anker)
{
	string resultat = "";
	if (anker == nullptr)
		return "Leere Liste.";
	else
	{
		resultat += "[ ";
		TListenKnoten *ptr = anker;
		do
		{
			resultat += std::to_string(ptr->data);
			if (ptr->next != nullptr) resultat += " , ";
			else resultat += " ";
			ptr = ptr->next;
		} while (ptr != nullptr);
		resultat += "]";
	}
	return resultat;
}
void liste_ausgeben(TListenKnoten * anker)
{
	cout << liste_als_string(anker) << endl;
}
string liste_als_string_rueckwaerts(TListenKnoten * anker)
{
	string resultat = "";
	if (anker == nullptr)
		return "Leere Liste.";
	else
	{
		resultat += "[ ";
		TListenKnoten *ptr = anker;
		while (ptr->next != nullptr)
		{
			ptr = ptr->next;
		}
		do
		{
			resultat += std::to_string(ptr->data);
			if (ptr->prev != nullptr)
			{
				resultat += " , ";
			}
			else
			{
				resultat += " ";
			}
			ptr = ptr->prev;
		} while (ptr != nullptr);
		resultat += "]";
	}
	return resultat;
}
void liste_ausgeben_rueckwaerts(TListenKnoten * anker)
{
	cout << liste_als_string_rueckwaerts(anker) << endl;
}
bool existiert_in_der_liste(TListenKnoten* &anker, int gesucht) {
	if (anker == nullptr) {
		return false;
	}
	TListenKnoten *ptr = anker;
	//while (ptr->next != nullptr)
	while (ptr != nullptr)
	{
		//if (ptr->next->data == gesucht)
		if (ptr->data == gesucht)
		{
			return true;
		}
		ptr = ptr->next;
	}
	return false;
}
void in_liste_einfuegen(TListenKnoten* &anker, int wert_neu, int vor_wert)
{
	TListenKnoten *neuer_eintrag = new TListenKnoten;
	neuer_eintrag->data = wert_neu;
	neuer_eintrag->next = nullptr;
	neuer_eintrag->prev = nullptr;

	if (existiert_in_der_liste(anker, vor_wert))
	{
		// cout << "if ??????" << endl;
		if (anker->data == vor_wert)
		{
			neuer_eintrag->next = anker;
			anker->prev = neuer_eintrag;
			anker = neuer_eintrag;
		}
		else
		{
			TListenKnoten *ptr = anker;
			TListenKnoten *parent = anker;
			while (ptr->data != vor_wert)
			{
				parent = ptr;
				ptr = ptr->next;
			}
			parent->next = neuer_eintrag;
			neuer_eintrag->next = ptr;
			neuer_eintrag->prev = parent;
			ptr->prev = neuer_eintrag;
		}
	}

	else
	{
		if (anker == nullptr) {
			anker = neuer_eintrag;
		}
		else
		{
			TListenKnoten *ptr = anker;
			while (ptr->next != nullptr)
			{
				ptr = ptr->next;
			}
			ptr->next = neuer_eintrag;
			ptr->next->prev = ptr;
		}
	}
}
void aus_liste_loeschen(TListenKnoten* &anker, int wert)
{
	// ersten Knoten mit Wert löschen
	// Falls einziges Element, also Liste danach leer, anker auf nullptr setzen
	// Bei Duplikaten immer nur den ersten Knoten löschen
	// auch bei einer leeren Liste aufrufbar, ergo wenn der Wert nicht vorkommt
	// bei letzterem soll dann nix passieren
	// Hinweis: Was wenn der erste Knoten gelöscht werden soll?

	if (anker == nullptr)
	{
		return;
	}
	else
	{
		TListenKnoten *ptr = anker;
		TListenKnoten *parent = ptr;
		while (ptr->data != wert)
		{
			parent = ptr;
			ptr = ptr->next;
		}

		parent->next = ptr->next;
		ptr->next->prev = parent;
		delete ptr;
	}
}
void liste_loeschen(TListenKnoten* &anker)
{
	if (anker == nullptr)
	{
		return;
	}
	else
	{
		TListenKnoten *ptr = anker;
		TListenKnoten *parent = ptr;
		while (ptr->next != nullptr)
		{
			parent = ptr;
			ptr = ptr->next;
		}

		while (ptr != anker)
		{
			parent = ptr;
			ptr = parent->prev;
			delete parent;
			parent = ptr;
		}
		anker = nullptr;
	}
}

int main()
{
	const int laenge = 10;
	TListenKnoten *anker = nullptr;
	liste_ausgeben(anker);
	liste_ausgeben_rueckwaerts(anker);
	liste_loeschen(anker);
	hinten_anfuegen(anker, 77);
	hinten_anfuegen(anker, 88);
	hinten_anfuegen(anker, 99);
	liste_ausgeben(anker);
	liste_ausgeben_rueckwaerts(anker);
	liste_loeschen(anker); // war: aus_liste_loeschen(anker, 99);
	liste_ausgeben(anker);
	liste_ausgeben_rueckwaerts(anker);
	for (int i = 0; i < laenge; i++)
		in_liste_einfuegen(anker, i*i, 9999);
	liste_ausgeben(anker);
	liste_ausgeben_rueckwaerts(anker);
	in_liste_einfuegen(anker, -1, 0);
	in_liste_einfuegen(anker, 24, 25);
	in_liste_einfuegen(anker, 80, 81);
	in_liste_einfuegen(anker, 99, 9999);
	liste_ausgeben(anker);
	liste_ausgeben_rueckwaerts(anker);
	aus_liste_loeschen(anker, 24);
	aus_liste_loeschen(anker, 80);
	liste_ausgeben(anker);
	liste_ausgeben_rueckwaerts(anker);
	liste_loeschen(anker);
	liste_ausgeben(anker);
	liste_ausgeben_rueckwaerts(anker);
	system("PAUSE");
	return 0;
}