/* Create a double linked list and insert nodes one by one
   according to the values of nodes to decide the links. 
   After all nodes are inserted, the list is sorted already.*/

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

template <typename T>
class Node
{
  public:
	T nodeValue;		//data held by the node
	Node<T> * prev;		//next node in the list
	Node<T> * next;		//next node in the list

	// default constructor with no initial value
	Node () 
    {
    next = NULL;
    prev = NULL;
    }

	// constructor.  Initialize nodeValue and next
	Node (const T& item, Node<T> * prevNode = NULL, Node<T> * nextNode = NULL)
	{
		nodeValue = item;
		prev = prevNode;
		next = nextNode;
	}
};
template <typename T>
void insert(Node<T> *& front, Node<T> * curr)
{
     Node<T> * p = front;  //p points to front in the beginning
	 Node<T> * q;

     if(front == NULL)     //if it was an empty list
        front = curr;
     else
        if(p->nodeValue > curr->nodeValue)   //curr is instered before p
        {
	   if(p->prev != NULL)     //connect the p's prev node to curr 
	   {
		  q = p->prev; 
		  q->next = curr;
		  curr->prev = q;
	   }
           p->prev = curr;         //connect curr and p
           curr->next = p;
           front = curr;
	}
        else
            if(p->next == NULL)    //p is at tail of the list, curr attaches to p
            {
                p->next = curr;
                curr->prev = p;
            }
            else
               {
                  p = p->next;    // move p to the next node
                  insert(p, curr);  //recursive to insert the curr node
               }
}     
        
int main()
{
	Node<string> * p, *head, *newNode;
	
	head = new Node<string>;   //create an empty object

	string name;
	ifstream read("data.txt");
	while(read>>name)       //read the data until the end of list
	{
	 newNode = new Node<string> (name);
	 insert(head, newNode);
        }
	//Print the list
	p=head;
	while(p != NULL)
	{
		cout<<p->nodeValue<<" ";
		p = p->next;
	}
	cout<<endl;
	
	//Deallocate all dynamic memories
	Node<string> * toBeDelete;
	p= head;
	while(p != NULL)
	{
		toBeDelete=p->next;
		delete p;
		p = toBeDelete;
	}

	system("pause");
	return 0;
 }

data.txt

Bridge
Falilou
Mandela
Kevin
Eliot
Antonio