-
doubly linked lists
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;
}
-
A doubly linked list is easy to follow once you understand how to use a pointer to access the previous node in the list. Here's a template, I'll explain as I go.
Code:
struct node {
int number;
node *next;
node *prev; //pointer to the previous node
}
int main() {
node root;
node iter;
root->next = NULL; //there's only one node so the root only
root->prev = NULL; //points to null both ways
root->number = 0;
iter = root;
for ( int i = 1; i < 10; i++ ) {
iter->next = new node; //new node, same as usual
iter->next->prev = iter; //new node points to current node with prev pointer
iter->next->next = NULL; //new node points to null with next pointer
iter = iter->next; //new node becomes current node
iter->number = i; //place the value of the counter in number
}
The only real difference is when you assign the iterator to the new node. You have to assign the prev pointer of the new node to the current node before making the new node the current node. Printing, inserting, and deleting are exactly the same except with an added step of dealing with the extra pointer to the previous node.
-
ok, that helped a little but i still don't understand how to implement that into the function. The way the program works is the function insertinorder is called to insert one city at a time, so if there are 10 cities, it runs through the function ten times.
-
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){}
};