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;
}