i'm working on a program dealing with linked lists. the program loads a list of cities into a linked list, alphabetically, and lets the user display, add and remove from the list. Then we where supposed to modify the program to use doubly linked lists, and add a function to Display the list backwords. I did the first part easily, but i'm lost on the doubly linked lists.

here is the function that loads the data into the single linked list:

STATUS InsertInOrder (NODE *head, const apstring &city)

// Inserts "city" in alphabetical order into the linked list.

// Assumes that the list is arranged in alphabetical order.

// Duplicate names are allowed.

// Returns OK if successful, FAILED if could not

// allocate a new node.

{

NODE *newnode;

// 1. Allocate a new node:

newnode = new NODE;

if (!newnode)

return FAILED;

// 2. Copy the information into newnode:

newnode->city = city;

// 3. Link newnode to the list:

// 3.1. Find the right place to insert newnode --

// between "prev" and "node":

NODE *node = head, *prev = 0;

while (node && node->city <= city) {

prev = node; // ... advance node and prev

node = node->next;

}

// 3.2. Link newnode between "prev" and "node":

newnode->next = node; // Append "node" to newnode.

if (prev)

prev->next = newnode; // Insert after "prev".

else

head = newnode; // No prev -- make newnode the

// new head.

return OK;

}

here is what i've done so far to change the function to load a doubly linked list. please help me fix this, or show me what to do next:

STATUS InsertInOrder (LIST &list, const apstring &city)

// Inserts "city" in alphabetical order into the linked list.

// Assumes that the list is arranged in alphabetical order.

// Duplicate names are allowed.

// Returns OK if successful, FAILED if could not

// allocate a new node.

{

NODE *newnode;

// 1. Allocate a new node:

newnode = new NODE;

if (!newnode)

return FAILED;

// 2. Copy the information into newnode:

newnode->city = city;

// 3. Link newnode to the list:

// 3.1. Find the right place to insert newnode --

// between "prev" and "node":

NODE *node = list.head; //*prev = 0;

NODE *node2 =list.tail; //*prev2=0;

while (node && node->city <= city) {

node->prev = node; // ... advance node and prev

node = node->next;

}

// 3.2. Link newnode between "prev" and "node":

newnode->next = node; // Append "node" to newnode.

if (node->prev)

node->prev->next = newnode; // Insert after "prev".

else{

list.head = newnode; // No prev -- make newnode the

list.tail = newnode; // new head and tail.

}

return OK;

}