#include<iostream>
#include<cstdlib>
#include <ctime>
#include <chrono>
using namespace std::chrono;
using namespace std;


// Create einfach und doppelt verkettete Listen
struct node {
   int data;
   struct node *next;
};

struct node* front = NULL;
struct node* rear = NULL;
struct node* temp;

struct dlist {
	dlist * prev;
	int data_1;
	dlist * next_1;
};

dlist *first, *current, *previos, *tamp;
int dlinklist_counter = 0;

// Insert Funktion für einfach verkettete Liste
void Insert(int val)
{
   if (rear == NULL) {
      rear = (struct node *)malloc(sizeof(struct node));
      rear->next = NULL;
      rear->data = val;
      front = rear;
   } else {
      temp=(struct node *)malloc(sizeof(struct node));
      rear->next = temp;
      temp->data = val;
      temp->next = NULL;
      rear = temp;
   }
}

// Delete Funktion für einfach verkettete Liste
void Delete() {
   temp = front;
   if (front == NULL) {
      cout<<"Underflow"<<endl;
      return;
   }
   else
   if (temp->next != NULL) {
      temp = temp->next;
      free(front);
      front = temp;
   } else {
      free(front);
      front = NULL;
      rear = NULL;
   }
}


// Insert doppelt verkettete Liste
void dlinklist_insert(int val)
{
	current = new dlist;
	if (dlinklist_counter == 0)
	{
		previos = current;
		first = current;
		current->prev = NULL;
		current->data_1 = val;
	}
	else
	{
        cout<< val <<endl;
		previos->next_1 = current;
		current->prev = previos;
		previos = current;
		current->data_1 = val;
	}
	current->next_1 = NULL;
	dlinklist_counter++;
}

// Delete Doppelt verkette Liste
void dlinklist_dequeu()
{
	if (dlinklist_counter == 0)
	{
		cout << " Queue is empty";
		system("pause");
	}
	else
	{
		first = first->next_1;

		dlinklist_counter--;
	}
}


int main()
{
    // Länge der Listen
    int n = 1000000;
    // Dynamische Speicherverwaltung für Array, das random Zahlen beinhaltet
    int* q = new int[n];

    // Array wird mit Random Zahlen gefüllt, man könnte auch direkt die Liste füllen, aber so wird sichergestellt, dass beide Listen mit den selben Zahlen gefüllt werden
    for(int i= 0; i<=n; i++)
    {
        int huan = rand();
        q[i] = huan;
    }

    // Starte Zeitmessung für einfach verkettete Liste
    std::chrono::time_point<std::chrono::system_clock> start, end;
    start = std::chrono::system_clock::now();

    // Insert Random Zahlen in Liste
    for(int i= 0; i<=n; i++)
    {
        Insert(q[i]);
    }

    // Lösche Random Zahlen aus Liste
    for(int i= 0; i<=n; i++)
    {
        Delete();
    }
    // Stoppe Zeitmessung
    end = std::chrono::system_clock::now();

    // Starte 2. Zeitmessung
    std::chrono::time_point<std::chrono::system_clock> start_1, end_1;
    start_1 = std::chrono::system_clock::now();

    // gleuch wie oben nur für doppelt verkettete Liste
    for(int i= 0; i<=n; i++)
    {
        dlinklist_insert(q[i]);
    }

    for(int i= 0; i<=n; i++)
    {
        dlinklist_dequeu();
    }

    end_1 = std::chrono::system_clock::now();

    // Berechne Differenz der Zeitmessungen
    int elapsed_seconds = std::chrono::duration_cast<std::chrono::seconds>
                             (end-start).count();

    int elapsed_seconds_1 = std::chrono::duration_cast<std::chrono::seconds>
                             (end_1-start_1).count();

    // gebe Zeit aus
    cout << "Dauer einfache Liste:";
    cout << elapsed_seconds << endl;
    cout << "Dauer doppelte Liste:";
    cout << elapsed_seconds_1 << endl;





}