#pragma once
#include <iostream>
using namespace std;

class linkedList
{
private:
	class node
	{
	public:
		double data;
		node* next;
	};

	//What variables does a linked list need?
	node* head;

	//Can keep other stuff if you want

	//helper methods
	//return pointer to node containing smallest
	//value from p to end of list.
	//Run time O(n)
	node* findSmallest(node* p)
	{
		node* current = p;
		node* smallestPtr = p;

		while (current != nullptr)
		{
			if (current->data < smallestPtr->data)
				smallestPtr = current;

			current = current->next;
		}
		return smallestPtr;
	}

public:
	linkedList()
	{
		head = nullptr;
	}

	//deconstructor: called when
	//object goes out of scope
	~linkedList()
	{
		while (!empty())
		{
			pop();
		}
	}

	//Add x to the front of the list
	//run time O(1)
	void addFront(double x)
	{
		node* baby = new node;
		baby->next = head;
		baby->data = x;
		head = baby;
	}

	//run time: O(1)
	double pop()
	{
		node* doomed = head;
		double output = head->data;

		head = head->next;

		delete doomed;
		return output;
	}

	bool empty()
	{
		if (head == nullptr)
			return true;
		else
			return false;
	}

	void printList()
	{
		node* current = head;

		while (current != nullptr)
		{
			//print current value
			cout << current->data << endl;

			//move current ptr to next node
			current = current->next;
		}
	}

	//Selection sort: run time O(n^2)
	void sort()
	{
		node* current = head;
		while (current != nullptr) //# loops: n
		{
			node* small = findSmallest(current); //O(n)
			swap(current->data, small->data); //O(1)

			current = current->next; //O(1)
		}
	}
};