OK,
I'm trying to write a program that uses a circular linked list. I have been playing around with a linked list program all day, and kinda understand it. Here it is, and yes it does compile.

#include <iostream>

using namespace std;

struct node
  {  char name[20];    // Name of up to 20 letters
     int age;          // D.O.B. would be better
     float height;     // In metres
     node *nxt;// Pointer to next node
  };

node *start_ptr = NULL;
node *current;		 // Used to move along the list
int option = 0;

void add_node_at_end()
  {  node *temp, *temp2;   // Temporary pointers

     // Reserve space for new node and fill it with data
     temp = new node;
     cout << "Please enter the name of the person: ";
     cin >> temp->name;
     cout << "Please enter the age of the person : ";
     cin >> temp->age;
     cout << "Please enter the height of the person : ";
     cin >> temp->height;
     temp->nxt = NULL;

     // Set up link to this node
     if (start_ptr == NULL)
       { start_ptr = temp;
	 current = start_ptr;
       }
     else
       { temp2 = start_ptr;
         // We know this is not NULL - list not empty!
         while (temp2->nxt != NULL)
           {  temp2 = temp2->nxt;
              // Move to next link in chain
           }
         temp2->nxt = temp;
       }
  }

void display_list()
  {  node *temp;
     temp = start_ptr;
     cout << endl;
     if (temp == NULL)
       cout << "The list is empty!" << endl;
     else
       { while (temp != NULL)
	   {  // Display details for what temp points to
              cout << "Name : " << temp->name << " ";
              cout << "Age : " << temp->age << " ";
	      cout << "Height : " << temp->height;
	      if (temp == current){
		cout << " <-- Current node";}
	//	else if (temp == NULL){
   	//      cout << " <-- Last Node" << endl;}
              cout << endl;
	      temp = temp->nxt;
	      

	   }
	 cout << "End of list!" << endl;
       }
  }

void delete_start_node()
   { node *temp;
     temp = start_ptr;
     start_ptr = start_ptr->nxt;
     delete temp;
   }

void delete_end_node()
   { node *temp1, *temp2;
     if (start_ptr == NULL)
          cout << "The list is empty!" << endl;
     else
        { temp1 = start_ptr;
          if (temp1->nxt == NULL)
             { delete temp1;
               start_ptr = NULL;
             }
          else
             { while (temp1->nxt != NULL)
                { temp2 = temp1;
                  temp1 = temp1->nxt;
                }
               delete temp1;
               temp2->nxt = NULL;
             }
        }
   }

void move_current_on ()
   { if (current->nxt == NULL)
      cout << "You are at the end of the list." << endl;
     else
      current = current->nxt;
   }

void move_current_back ()
   { if (current == start_ptr)
      cout << "You are at the start of the list" << endl;
     else
      { node *previous;     // Declare the pointer
        previous = start_ptr;

        while (previous->nxt != current)
          { previous = previous->nxt;
          }
        current = previous;
      }
   }

 main(){
       start_ptr = NULL;
     do
	{
	  display_list();
	  cout << endl;
	  cout << "Please select an option : " << endl;
	  cout << "0. Exit the program." << endl;
	  cout << "1. Add a node to the end of the list." << endl;
	  cout << "2. Delete the start node from the list." << endl;
	  cout << "3. Delete the end node from the list." << endl;
	  cout << "4. Move the current pointer on one node." << endl;
          cout << "5. Move the current pointer back one node." << endl;
          cout << endl << " >> ";
	  cin >> option;

	  switch (option)
	    {
	      case 1 : add_node_at_end(); break;
	      case 2 : delete_start_node(); break;
	      case 3 : delete_end_node(); break;
	      case 4 : move_current_on(); break;
              case 5 : move_current_back();
	    }
	}
     while (option != 0);
     
     return 0;

  }

My problem is that, I can't find any good resources on circular linked lists. I know that the last node in a circular linked list points
to the first node, but I can't figure out how to do this. Should I create another pointer in the struct??

My program is supposed to build a linked list of cards, and perform operations such as insert, delete, traverse.

Also, what is the true definition of traverse???

My directions say that a "card" can be inserted anywhere into the stack, and be traversed back to the "home card".

If anybody can get me pointed in the right direction, it would be greatly appreciated.

Again, the code above is just a normal linked list. If I am traversing any thing in the program, let me know so I can understand what that means more clearly.

John

As far as I know, 'traverse' simply means to move through the list/tree.. so to traverse a 'card' back to the 'home card' would just mean to move the appropriate node to the start of the list. Your move_current_back() function should be able to deal with that.

I've also noticed a lack of good resources on circular linked lists so I'm also officially interested in any links/examples anyone can conjure up although I'm not sure why you'd need a circular linked list for a simple deck of cards.. Unless it's been specified that you need to implement a circular linked list then I can't see any reason why a normal linked list wouldn't do the trick (?).

P.S. The code you posted (taken straight from a tutorial) could do with a couple of improvements.. getting rid of those global variables by having your functions accept a start_ptr would be a little cleaner :)

Thanks for the response!

Yes, the code is taken from a tutorial. It has helped me get a better understanding. I'm am doing this for an assignment that requires a circular list.

The program is a lot different than a simple deck of cards.
It needs to be circular because I have a home card and a tail.
Instead of the tail pointing to NULL, it has to point to the home card.

I understand how the current is set, and im working on the tail.

void add_node_at_end()
  {  node *temp, *temp2;   // Temporary pointers

     // Reserve space for new node and fill it with data
     temp = new node;   // creates a new node that temp points to.
     cout << "Please enter the message ";
     cin >> temp->msg;      // stores the input as the nodes msg
     
     temp->nxt = NULL;      // sets the nxt pointer to NULL because the node at the end has NULL pointer

     // Set up link to this node
     if (start_ptr == NULL)      // it is null when there is no other nodes
       { start_ptr = temp;       // the start_ptr points to the temp node 
	 current = start_ptr;        // the current pointer is set to the same address as the start_ptr
       }
       
     // else is the start_ptr is not != NULL, this means that there are other nodes
     else
       { temp2 = start_ptr;      // temp2 points to the start_ptr
       // We know this is not NULL - list not empty!
         while (temp2->nxt != NULL) 
           {  temp2 = temp2->nxt;   
              // Move to next link in chain
           }
         temp2->nxt = temp;
         tail_ptr = temp;   //sets the tail pointer to the last node created.
       }
  }

Thats as far as I have got to assigning a tail.

You must make a pointer that points to the first node (I think a card means a node). And traverse, means to simply go through the linked list, by going through each node one by one.

Hope this helps

I don't think you want to assign temp to your tail_ptr because temp->nxt = NULL so all you'd be doing is assigning space for a new node into tail_ptr and then making it the end of the list.. Maybe if you made temp->nxt point to the start_ptr.. (?) See if that works.
I'm pretty sure that none of your nodes should have a NULL pointer in them because the links should all join up..

Ok. Thanks for the help. But I got it to work finally after drawing UML diagrams all night. I am having a small problem though.

I have a method that move the current pointer to the next item in the list.

#include <iostream>
#include <cstdlib>
#include <fstream>
#include <string>
using namespace std;

struct node{  
     int key;
     string msg;    // Name of up to 20 letters
     node *nxt;// Pointer to next node
   };
   

node *home_ptr = NULL;
node *tail_ptr;
node *current;		 // Used to move along the list
int option = 0;



///////////////////////////////////////////////////
// Function to Add a node to the end of the list.//

void add_node_at_end(string name, int key)
  {  node *temp, *temp2;   // Temporary pointers

     // Reserve space for new node and fill it with data
     temp = new node;
     temp->msg = name;
     temp->key = key;
     temp->nxt = NULL;  // set the nodes *nxt pointer to NULL

     // Set up link to this node
     if (home_ptr == NULL)        // it is null when there is no other nodes
       { home_ptr = temp;         // the home_ptr points to the temp node
	 current = home_ptr; 
      temp->nxt = temp;         // the current pointer is set to the same address as the start_pt
       }
       
       
     // else if the home_ptr is not != NULL, this means that there are other nodes  
     else                         
       {  temp2 = current;
         // We know this is not NULL - list not empty!
         while (temp2->nxt != home_ptr)
           {  
              temp->nxt = home_ptr;
              
             
              // Move to next link in chain
           } 
           temp2->nxt = temp;
           temp->nxt = home_ptr;
           tail_ptr = temp;
           current = temp;
         
       }
     //  system("pause");
  }

/////////////////////////////////
// Function to print the list.//
void display_list()              
  {  node *temp;         // temp pointer
     temp = home_ptr;    // the temp pointer points to the home_ptr.
     cout << endl;
     if (temp == NULL)   // if temp points to NULL, the list is empty.
       cout << "The list is empty!" << endl;
     else
       { while (temp->nxt != home_ptr ) // if temp doesn't point to NULL, output the mode temp points to.
	   {  // Display details for what temp points to
	          cout << "Key : " << temp->key << " ";
              cout << "Message : " << temp->msg << " ";
              
        if (temp == home_ptr){      // if temp's address is the same as the home_ptr address.
   	    cout << " <-- Home Node";}  // display "<-- Home Node" next the the node. 
   	    
  	    else if (temp == tail_ptr){             // if temp's address is the same as the home_ptr address.
		cout << " <-- Current node" << endl;}  // display "<-- Current Node" next the the node. 
        
              cout << endl;
	      temp = temp->nxt;           // Move to next link in chain
	    // system("pause"); 

	   } // End while
	          cout << "Key : " << temp->key << " ";
              cout << "Message : " << temp->msg << " ";
              if (temp == tail_ptr){             // if temp's address is the same as the home_ptr address.
		      cout << " <-- Current node" << endl;}
	 cout << "\nEnd of list!" << endl;  // always prints this when there is nodes in the list.
       } // End Else
       
  } // End display_list
///////////////////////////////////////////////
// Move the current pointer to the next node.//
void move_current_on()
   {    
      current = current->nxt;
     
         
   }
///////////////////
// Main Function//

 main(){
       home_ptr = NULL;
       char cmd;                       // declare variables.
       string name;
       int key;



    ifstream inFile;               // create ifstream object
    inFile.open("prog2.dat");      // assign to .dat file
    if (inFile.fail()) {           // if it fails to open, display error message, and exit.
      cerr << "unable to open file input.dat for reading" << endl;
      exit(1);                     
 } 
 
 
  while(true){                    // while loop until eof is true. 


inFile >> cmd;                 // read cmd from the inFile
if(inFile.peek() != '\n')      // if the next item is  not \n then store as key
inFile >> key;
if(inFile.peek() != '\n')      // if the next item is  not \n then get the remainder of the line as string.
getline(inFile, name);

if(inFile.eof()) break;        // If the inFile is @ eof, break the while loop.


 // Switch statement for checking the cmd char to determine the operation.
 switch(cmd){
                case 'i':          
                      cout << "insert" << endl;
                      add_node_at_end(name,key);
                      break;
                case 'd':
                      cout << "delete" << endl;
                      delete_node(key);
                      break;
                case 't':
                      cout << "traverse" << endl;
                      break;
                case 'h':
                      cout << "home" << endl;
                      break;
                case 'f':
                      cout << "forward" << endl;
                       move_current_on();
                      break;
                case 'p':
                      cout << "print" << endl;
                      display_list();
                      break;
                default:
                      break;
                } // end switch


name.clear(); // clear the name string.
key = 0;      // clear the key.
   
	    }     // End while loop.
	
    
     system("pause");  
     return 0;

  } // End of main

The program compiles fine. But the current never moves forward.
I put a cout in the function just to make sure my current was set correctly, and it seems to indicate that the current position is correct, but the cout in my print doesnt move.
The switch statement in my main, should call the move current function when a f is encountered in the input, and it does, but the current never changes.
any thoughts??

Edited 7 Years Ago by luskbo: n/a

This article has been dead for over six months. Start a new discussion instead.