Thread: Linked List of Linked lists Revisited.

Hi, I am still having problems with my linked list of linked lists problem I posted last month, here is the linking function I have devised:

Code:

void lnk_C_and_H(Holiday *pHoliday, Customer *pCustomer, int nHolidays, int nCustomers)
{
	pCustomer = pHead;
	for(int i = nCustomers; i>0; i--)
	{
		pHoliday = Head;
		for(int j = nHolidays; j>0; j--)
		{
			if(strcmp(pHoliday->Holiday_code,pCustomer->Holiday_code))
			{
				pHoliday->pCustomer_lst = new Customer;
				pHoliday->pCustomer_lst = pCustomer;
				add_Customer(pHoliday->pCustomer_lst);
				break;
			}
			pHoliday = pHoliday->next;
		}
		pCustomer = pCustomer->pNext;
	}
}

also here is the add_Customer() function:

Code:

void add_Customer(Customer *pCustomer)
{
	if(pHead == NULL) 
	{
		pHead = pCustomer;
		pCustomer->pPrev = pHead;
		pCustomer->pNext = pHead;
	}
	else 
	{
		pCustomer->pPrev = pHead->pPrev;
		pHead->pPrev->pNext = pCustomer;
		pCustomer->pNext = pHead;
		pHead->pPrev = pCustomer;
	}
}

and here are the 2 structures:

Code:

struct Customer 
{
	string fName;
	string lName;
	char Holiday_code[5];
	Customer *pNext;
	Customer *pPrev;
}*pHead, *pHead2, *pCustomer;

struct Holiday 
{
	char Holiday_code[5];
	string location;
	string destination;
	string place_of_stay;
	double price;
	Customer *pCustomer_lst;
	Holiday *next;
	Holiday *prev;
}*Head, *pHoliday;

What I did was first create a linked list of customers and holidays, and then i tried to link them and (create I beleive) a third linked list of customers ona specific holiday, well it didnt work at all, I am completely perplexed by this problem and am not even sure if my methods are correct as I dont think I am suppose to make a 3rd linked list (am I?).

Any help on this matter would be greatly apreciated.

I can't tell by looking at the code posted whether your lists are instances of a class(es) or free standing lists and whether add_Customer and lnk_C_and_H are methods of a class or free standing functions.

If your lists are free standing then the line:

Customer *pCustomer_lst;

in the Holiday struct should allow you to create a list of Customers for each node in the list of Holidays. But I think your add_Customer()function should be passed both the head node of the list you want to add to and the node you wish to add. pCustomer_lst should be treated as the head node for each customer list. In your lnk_C_and_H fucntion it looks like you are trying to use pCustomer_lst as the customer to add, not the head node of the customer list, which it appears to be in the declaration of the Holiday struct.

If your lists are classes, then the Holiday struct could contain a line something like this:

CustomerList Customers;

rather than this:

Customer * pCustomer_lst;

to have a list of Customers in each Holiday and your add_Customer() would then just need the Customer to add passed as a parameter (or no parameters if the Customer information is obtained by the add_Customer function itself). By convention, pHead usually refers to the head of a list that is an instance of a class, whereas freeStanding lists don't routinely have a node specifically noted as head as the name of the pointer is the name of the list and the head node of the list all in one.

I'll be happy to try to help out but I'll need the class/free standing issue clarified before giving more specific advice.

Hi, sorry for not clarifying that the lists and functions are all free standing and not classes. could you please elaborate more on what you mean by passing the 'head' into the add_customer() function.

Thanks

I guess I should find out if you want the lists to be global or local variables. If your list is a global variable, then add_Customer() could take just a single variable containing the information to add to the list and pull in the list itself from global space. If the list is local, then you need to pass information as to which list you want to add to to add_Customer. I just assumed you'd use a local, variable, but it's not mandatory. Using global variables makes the code easier to write, but is not as encouraged as using local variables. Sorry about that.

Either global or local, whichever is best as TBH I am quite lost with this, how would one normally go about making a linked list of linked lists, is there a set method I could follow as the linking function I beleive is totally wrong, it wont even work when I am not trying to create a linked list ie just setting pHoliday->pCustomer_lst= pCustomer, it doesnt work, is there another way I can go about this?

Thanks

Alright, to be sure of common ground I recommend we start from the beginning. I don't mean to insult you by doing this, but lists and lists of lists can get pretty complicated pretty fast if we don't speak the same language.

For simplisity, I've written some stripped down code similar to what I think yours is to develop a doubly linked list of Customers. The list is built by adding each new Customer to the beginning of the list. The list itself, list1, is global. Do you understand what is being done in each of the functions?

Code:

#include <iostream>
using namespace std;
struct Customer
{
  int id;
  Customer * next;
  Customer * prev;
};
 
Customer * list1;
 
void developCustomer(Customer *&);
void addCustomer(Customer *);
void displayList(Customer *);
 
const MAX = 5;

int main(int argc, char* argv[])
{
  list1 = NULL;
  Customer * pC = NULL;
  int i;
  for(i = 0; i < MAX; ++i)
  {
	developCustomer(pC);  
	addCustomer(pC);
  }
  
  displayList(list1);
 return 0;
}
 
void developCustomer(Customer * & pC)
{
  pC = new Customer;
  cout << "enter id" << endl;
  cin >> pC->id;
  pC->next = NULL;
  pC->prev = NULL;
}
 
void addCustomer(Customer * pC)
{
  if(list1 == NULL)
	list1 = pC;
  else
  { 
	//add to front of list
	pC->next = list1;
	list1->prev = pC;
	list1 = pC;
  }
}
 
void displayList()
{
  Customer * currentCustomer = list1;
  while(currentCustomer != NULL)
  {
	cout << currentCustomer->id << ' ' << endl;
	currentCustomer = currentCustomer->next;
  }
}

In particular I think it is important to understand that the address in pC changes in developCustomer(), therefore it is passed as a reference so the values placed at the address in pC in developCustomer() will be available back in main() to be passed to addCustomer. Change the declaration of developCustomer to:

void developCustomer(Customer *);

and the definition to:

void developCustomer(Customer * pC)
{....

and recompile if you don't understand why that is important.

Note, that because list1 is global, we don't need to pass list1 to addCustomer() or displayList() like we did pC, which is local to main() rather than global. Likewise, because list1 is global I can change the address in list1 and have it stick without having to passing it by reference, like I had to with pC. When making a list local to main, and probably when making a list of lists, that difference will be further emphasized.

Hi, yes i totally understand what each function does, also what I did was create a doubly circular linked list, as such 'next' nor 'prev' will ever be NULL, and there will be only 1 sentinal the 'Head', I am just not sure I am going along the right path to make my list of lists, the customer list and holidays list are working fine independently but I have yet to understand how I link the 2 by a common element such that each holiday displays only the customer on that holiday linked by the common element in this case, Holiday_code, I double that my Add_customer() function woudl work with parsing pHoliday->pCustomer_list into it as it the add_custoemr function is using the pHead sentinal unique only to the Customer list as such I dont beleive that a Head for each Holidays customer list is being made.

My experience with circular doubly linked lists is zilch. I have done a list of lists using additions to end of list, so maybe I'll try to work one of those up for experience and post it if you haven't gotten your bug worked out.

Good luck.

For what it's worth, here's a program that creates a list of customers each of which has a "list" of vacations/holidays. It then creates a list of holidays from the list of customers with each holiday each containing it's own list of customers. It adds to the end of each list rather than to the front. It's not circular. Maye I'll see if I can use a list of pointers to customers in each holiday rather than a list of customers. Maybe that way I wouldn't have to create a whole new customer to add to the list of customers in each holiday, just point back to the existing list that is independent of the list of holidays. I might try to work on adding to beginning of each list, rather than the end, to see if I can get it to work---couldn't get it to last night, though.

Code:

#include <iostream>

using namespace std;
const int MAX = 2;
const int MAXHOLIDAYS = 3;

struct Customer
{
  int id;
  char vacations[MAX][1];
  Customer * next;
  Customer * prev;
};

void addCustomer(Customer **);


struct Holiday
{
  char name;
  Customer * customers;
  Holiday * hNext;
  Holiday * hPrev;
};

void addHoliday(Holiday **, Customer *);
void displayHolidays(Holiday *);
int main()
{
  Customer * customerList = NULL;

  int i;
  for(i = 0; i < MAX; ++i) 
	addCustomer(&customerList);
  
  Holiday * holidays = NULL;


  for(i = 0; i < MAXHOLIDAYS; ++i) 
	addHoliday(&holidays, customerList);

  displayHolidays(holidays);

  return 0;
}


void addCustomer(Customer ** customerList)
{
  Customer * newCustomer;
  newCustomer = new Customer;
  cout << "enter id" << endl;
  cin >> newCustomer->id;
  
  int i;
  for(i = 0; i < MAX; ++i)
  {
	cout << "enter vacation name" << endl;
	cin >> newCustomer->vacations[i][0];
  }
  newCustomer->next = NULL;
  newCustomer->prev = NULL;
  
  Customer * currentCustomer = *customerList;

  if(currentCustomer == NULL)
	*customerList = newCustomer;
  else
  { 
	//add to back of list

	//find last Customer in list
	while(currentCustomer->next != NULL)
	  currentCustomer = currentCustomer->next;

	//add newCustomer to end of list;
	currentCustomer->next = newCustomer;
	newCustomer->prev = currentCustomer;
  }
}

void addHoliday(Holiday ** holidays, Customer * customerList)
{
  Holiday * newHoliday = new Holiday;
  newHoliday->customers = NULL; 
  newHoliday->hNext = NULL;
  newHoliday->hPrev = NULL;

  cout << "enter Holiday name" << endl;
  cin >> newHoliday->name;
  
  int i;
  Customer * currentCustomer = customerList;
  
  //search customerList for all customers who have this holiday as a vacation
  while(currentCustomer != NULL)
  {
	//look at each vacation for this customer
	for(i = 0; i < MAX; ++i)
	{
		//if this customer has this holiday listed
		if(currentCustomer->vacations[i][0] == newHoliday->name)
		{
		  //create a new customer to add to the list of customers in this holiday
		  Customer * newCustomer = new Customer;
		  newCustomer->id = currentCustomer->id;
		  int j;		  
		  for(j = 0; j < MAX; ++j)
			newCustomer->vacations[j][0] = currentCustomer->vacations[j][0];
			 
		  newCustomer->next = NULL;
		  newCustomer->prev = NULL;
 
		  //add the newCustomer to the list of customers in this holiday
		  if(newHoliday->customers == NULL)
			newHoliday->customers = newCustomer;
		  else
		  {
			//find the  end of the list of customers in this holiday
			Customer * tempCustomer = newHoliday->customers;
			while(tempCustomer->next != NULL)
			  tempCustomer = tempCustomer->next;
 
		   //add the new customer to the end of the list in this holiday
		   tempCustomer->next = newCustomer;
			newCustomer->prev = tempCustomer;
		  }
	   }
	}
	currentCustomer = currentCustomer->next;
  }
   
   //add this holiday to the list of holidays
  if(*holidays == NULL)
  {
	*holidays = newHoliday;
  }
  else
  { 
	//add to end of list
	Holiday * currentHoliday = *holidays;
	while(currentHoliday->hNext != NULL)
	  currentHoliday = currentHoliday->hNext;
	
	currentHoliday->hNext = newHoliday;
	newHoliday->hPrev = currentHoliday;
  }
}

void displayHolidays(Holiday * holidays)
{ 
  Holiday * currentHoliday = holidays;
  while(currentHoliday != NULL)
  {  
	cout << "this is holiday " << currentHoliday->name << endl; 
	cout << "customers are ";
	Customer * tempC = currentHoliday->customers;
	while(tempC != NULL)
	{
	  cout << tempC->id << ' ';
	  tempC = tempC->next;
	}
	cout << endl << endl;
	currentHoliday = currentHoliday->hNext;
  }
}

Hi elad, thanks for all your help, I figured it out in the end, although I didnt fully understaand your implementation (has lots of variables and confused me lol) it did help me to understand why mine was going wrong which points back to your first post, I was accidently pointing the pHoliday->pCustomer_lst to pCustomer and thus overighting it and all of its pointers when I did the add_Customer_lst() function, i have now manually specified what data is to be cloned into the pholiday_pcustomer_lst as such it works now fully.

Thanks again for all your help.

Congratulations!

Guess I won't need to post my version of a program that uses a list of pointers to the original list of Customers rather than a list of Customers per se in the Holiday struct.

Needless to say, I couldn't agree with you more when you say that following someone elses style/logic when it comes to linked lists gets confusing very fast, particularly when you only have part of the program to look at; which is why I wrote my own program and posted code to show the pertinent material from top to bottom. In my experience when I get into these problems it can be very helpful (sometimes very time consuming, too, but that's another matter) to strip down the program to bare essentials, comment the blazes out of the code using written sentences describing what exactly each step is supposed to do, and putting in lots of debugging code (like outputting the value of variables before and after a given step, since I've found that easier to do than using a debugger).

Your problem provided another instance of learning by trying to solve someone elses problem. Thanks for posting. I'm glad if my posts were useful to you in some way.