Thread: doubly linked lists

  1. #1
    Registered User
    Join Date
    Sep 2001
    Posts
    85

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

  2. #2
    Unregistered
    Guest
    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.

  3. #3
    Registered User
    Join Date
    Sep 2001
    Posts
    85
    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.

  4. #4
    of Zen Hall zen's Avatar
    Join Date
    Aug 2001
    Posts
    1,007
    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){}
    };
    zen

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Doubly linked lists
    By mohanlon in forum C Programming
    Replies: 8
    Last Post: 12-08-2010, 01:01 AM
  2. Doubly Linked Lists
    By Swerve in forum C++ Programming
    Replies: 6
    Last Post: 03-23-2009, 12:51 PM
  3. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  4. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM
  5. doubly linked lists
    By cworld in forum C++ Programming
    Replies: 2
    Last Post: 04-21-2002, 09:33 AM