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