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

//Store the incoming integers in a doublely linked list,
//in order of increasing size.

int main()
{
	struct node {
		int i;
		node *prev;   //the previous node (if any)
		node *next;   //the next node (if any)
	};

	node *head {nullptr}; //the first node, or nullptr if no nodes yet

	for (;;) {
		cout << "Input an int (or control-d when done): ";
		int i {0};
		cin >> i;
		if (!cin) {      //if the user typed control-d,
			break;   //out of the for loop
		}

		node *const p {new node}; //not an array, no square brackets
		p->i = i;                 //means (*p).i = i;

		//Insert the new node into the list.  There are three cases:

		if (head == nullptr) {   //The list is empty;
			//Case 1: insert p at the head of the list.
			p->prev = nullptr;
			p->next = nullptr;
			head = p;
		} else {
			//Loop along the list, until we find the correct place
			//to insert the new node p.

			for (node *q {head};; q = q->next) {
				if (q->next == nullptr) {  //q is the last node.
					//Case 2: insert p immediately after q.
					p->prev = q;
					p->next = nullptr;
					q->next = p;
					break;   //out of the for loop
				}
				if (q->i >= p->i) {
					//q is holding a bigger int than p.
					//Case 3: insert p immediately before q.
					p->prev = q->prev;
					p->next = q;
					if (q->prev == nullptr) {
						head = p;
					} else {
						q->prev->next = p;
					}
					q->prev = p;
					break;
				}
			}
		}
	}

	//Arrive here when the user typed control-d.
	cout << "\n";
	cout << "Here are the ints you typed in:\n";

	//Print all the integers.
	for (const node *p {head}; p != nullptr; p = p->next) {
		cout << p->i << "\n";
	}

	//Deallocate all the nodes.
	for (node *p {head}; p != nullptr;) {
		node *const q {p->next};   //Save p->next before it's destroyed.
		delete p;               //No square brackets to delete a scalar.
		p = q;
	}

	return EXIT_SUCCESS;
}