The insert function is pretty straightforward unless the value to be inserted is to be the head or the tail (the while loop will have stopped the iterator so you have to double check whether the tail is greater/less than the value to be inserted). It could be done like this (assuming that the head and tail pointers are global variables) -
Code:
void InsertInOrder (const string &city)
{
NODE* newnode = new NODE;
newnode->city = city;
if(head==NULL)
{
head=newnode;
tail=newnode;
return;
}
NODE* temp = head;
while(temp->next!=NULL && temp->city<city)
temp=temp->next;
if(temp==tail)
{
if(temp->city>city)
{
if (temp==head)
head=newnode;
newnode->next = temp;
newnode->prev=temp->prev;
temp->prev=newnode;
return;
}
else
{
temp->next=newnode;
newnode->prev=temp;
tail = newnode;
return;
}
}
if (temp==head)
head=newnode;
NODE* temp2 = temp->prev;
newnode->next = temp;
temp->prev=newnode;
newnode->prev=temp2;
}
To print the list out in reverse you would then create an iterator which is initialised to the tail pointer and for each iteration it is assigned to iterator->prev.
Depending on how your list is set up it may be easier to provide a constructor for your NODE so that you don't have to worry about the initialisation -
Code:
struct NODE
{
string city;
NODE* prev;
NODE* next;
NODE(): prev(NULL), next(NULL){}
};