#pragma once

#include <iostream>
#include <string>
using namespace std;

class node
{
public:
	string data; //data item
	node* next; //point to next node
};

class linkedList
{
public:
	//variables? (attributes)
	node* headptr;


	//functions (methods)
	linkedList()
	{
		headptr = nullptr;
	}

	//add an item to front of list
	//run time: O(1)
	void addFront(string x)
	{
		//declare a pointer variable
		node* p;
		
		//create a new node, and store it's address in p
		p = new node;

		//Put x into data field of the new node
		//Can also put p->data = x, same thing.
		(*p).data = x;

		//Set next pointer of node to previous front item
		(*p).next = headptr;

		//Update the head pointer
		headptr = p;
	}

	//Remove and return front item from list
	string popFront()
	{
		//Step 1: write down value to return
		string output;
		output = (*headptr).data;

		//Now, let's remove front item...
		
		//Write down node location for deletion
		node* doomedNode;
		doomedNode = headptr;

		//move headpoint to remove node
		headptr = (*headptr).next;

		//Prevent memory leak
		delete doomedNode;

		//Step last: return the value
		return output;
	}

	void printList()
	{
		//create pointer initialed to point at first node
		node* current;
		current = headptr;

		while (current != nullptr)
		{
			//print data of current node
			cout << (*current).data << endl;
			
			//Move current to point to next node
			current = (*current).next;
		}
	}

	//Return pointer to last node in list
	node * findLastNode()
	{
		node* current;
		current = headptr;

		while ( (*current).next != nullptr ) //current is not yet pointing to last node)
		{
			current = (*current).next;
		}

		return current;
	}

	//Add x to the back of the list
	void addBack(string x)
	{
		if (headptr == nullptr)
		{
			addFront(x);
		}
		else
		{
			//First task: loctate last node
			node* p;
			p = findLastNode();

			//Next step: create a new node
			node* babyNode;
			babyNode = new node;

			//Set values of baby node
			(*babyNode).next = nullptr;
			(*babyNode).data = x;

			//Have last node's next point point to baby
			(*p).next = babyNode;
		}
	}


	//Find smallest item in list from node i to the end,
	//Return pointer to that node.
	//Run time: O(n)
	node* findSmallest(node* i)
	{
		node* smallptr = i;
		for (node* current = i; current != nullptr; current = (*current).next)
		{
			if ((*current).data < (*smallptr).data)
			{
				smallptr = current;
			}
		}
		return smallptr;
	}

	//A basic selection sort
	//Run time: O(n^2)
	void sort()
	{
		for (node * iptr = headptr; iptr !=nullptr; iptr = (*iptr).next)
		{
			//find smallest from current item to end of list
			node* smallptr = findSmallest(iptr);

			//swap smallest item into node iptr
			swap((*iptr).data, (*smallptr).data);
		}
	}

	//Print list backwards from p to end.
	void printBackwardsRecursive(node* p)
	{
		if (p== nullptr) //base case
		{
			//Whoa!  empty list!  do nothing
		}
		else //recursive case
		{
			printBackwardsRecursive((*p).next);
			cout << (*p).data << endl;
		}
	}

	void printBackwards()
	{
		printBackwardsRecursive(headptr);
	}
};