Thread: Global linked list

I googled but could not find what i wanted.


basically passing pointers between each function is a bit of a nightmare for one of my linked lists which is being used continually throughout my program. Is it possible to make a global linked list? Or would i just have to declare a global structure, and give it a fixed size, rather than being able to to use dynamic memory?

No need to double post.

And yeah, of course you can simply make the variable global. If that's the best case for you. Usually it's not, but maybe it is in this case...

Just put it in global scope (and possibly declare it in the header file).

sorry i dont know how i managed to double post? browser maybe got confused.


I am concerned about making it a global variable since this structure has many different elements, and each time the program runs it will likely need a different number of this structure.

If i say tell it i want a global array of say 100 of these structures, then if i only use 10 then thats quite a lot of wasted memory.

You could technically make it a global variable and have it be dynamically allocated, but I would strongly recommend against it. Globals are fine for errno and singleton type stuff, but a bad idea if you're just feeling lazy. Pass it around, it's an extra few characters in function declarations and function calls. You'll get over the typing long before you get over the pain of tracking down some wonky behavior due to a global, or wondering just where in the hell some global variable really came from.

so how do i make a global linked list then? because any linked list i create inside a function will be freed as soon as the function ends right? and i cant declare it before the main program because i wont know how big it will be at that point

Linked lists, by their nature, dynamically allocate memory, using malloc or the like. They grow and shrink in size as needed, which is what they're designed for (unlike arrays, which are fixed size). That's their whole purpose. That memory that gets allocated for each node sits on the heap, and lives until your program frees it back up. If your linked list is declared in the main function, it will be fine. The local variable that points to the memory you just allocated will disappear when the function returns, but the actual allocated memory (i.e. list node on the heap) wont. Note that if you don't somehow pass back or store the contents of that local pointer variable though, you will lose the handle to that list node, causing a memory leak. You can store it in a global if you want, but...

GLOBAL VARIABLES ARE EVIL! Using global variable simply because you're lazy and don't want to type a bit more is a HORRIBLE practice to get into. It will come back and bite you at some point, so be warned. And since I've given you this warning, I will not help you solve any problems related to your use of "I'm lazy" global variables.

That being said, and going against my better judgement, declaring global variables is just like declaring function/local variables, but you do it outside all of your functions, in global scope.

Try declaring it in main first, and passing it around. If you get stuck with that, I'd be happy to help.

Maybe you should post some code, because by the sound of it you have a fatal flawed assumption or something similar. Try to build it and when you fail, paste the code and describe the error you're getting. Otherwise this post might end up as a full C tutorial :P.

i think maybe i havent clearly explained myself.

I am saying that i DONT want to have a global variable for this structure, as i dont want wasted memory. So my question is do i have to have a linked list that is created in the main, and then the pointer to it is just passed around the functions. Or can i have a linked list that is defined globally, but is still dynamic?

Does that make more sense?

No, it doesn't.

Linked lists are, by their very nature, dynamic. Post some code, showing implementation of your (1) list node, and (2) functions for performing simple operations on the list.

Ok so my program is to help solve an issue with a game you can play called the murder game. Usually you need someone to organise it for everyone else, but that obviously means they cannot play, so the aim of my program is for the computer to set it up, so that everybody can play.

So currently I am trying to get the user to type in the list of names of people playing, the computer will then randomly order those names into a list. Then it takes a list of weapons, and randomly assigns one to each player, ignoring any excess. Finaly the same for each location.

I have made two linked lists, one just stores a list of words so that as the user types them in it can temporarily store them, and then put them into the main linked list after, as described above.

The problem I have is as soon as the get names function closes i lose my main linked list.

Code:

typedef struct list{
	char name[MAXLENGTH];
	int ID;
	struct list *next;
} List;

typedef struct gamedata{
	char name[MAXLENGTH];
	char weapon[MAXLENGTH];
	char place[MAXLENGTH];
	char password[MAXLENGTH];
	int kills;
	int evasions;
	int alive;
	int ID;
	struct gamedata *next;
} GameData;

void myfgets(char array[MAXLENGTH]); /**this just removes new line character from input**/
void getpeople();
void getweapons();
void waitfunc(double period);

int main(){
	srand(time(NULL));
	printf("Welcome!\n");

	getpeople();
	

	
	system("pause");
}


void getpeople(){	
	int nplay, i, j, check, randn;
	char line[MAXLENGTH];
	struct list *root = NULL;
	struct list *p;
	struct gamedata *start = NULL;
	struct gamedata *pointer;

	printf("How many players are there?\n");
	fgets(line, MAXLENGTH, stdin);
    sscanf(line, "%d", &nplay);

	root = malloc(sizeof *root);
	if(root==NULL){
		fprintf(stderr, "Out of Memory!\n");
		exit(1);
	}
	root->next=NULL;
	p = root;

	printf("Thank you,");
	printf("Please enter the name for player 1\n");
	fgets(p->name, MAXLENGTH, stdin);
	myfgets(p->name);

	for(i=1;i<nplay;i++){
		p->next = malloc(sizeof *p);
		if(p==NULL){
			fprintf(stderr, "Out of Memory!\n");
			exit(1);
		}
		p=p->next;
		p->next=NULL;
			
		printf("Please enter the name for player %d\n", i+1);
		fgets(p->name, MAXLENGTH, stdin);
		myfgets(p->name);
	}

	p=root;
	
	while(p->next != NULL){
		printf("%s\n", p->name);
		p = p->next;
	}
	printf("%s\n", p->name);

	
	
	start = malloc(sizeof *start);
	if(start==NULL){
		fprintf(stderr, "Out of Memory!\n");
		exit(1);
	}
	start->next=NULL;
	pointer = start;
	pointer->next=NULL;
	pointer->alive = 0;
	pointer->evasions = 0;
	pointer->kills = 0;

	
	for(i=1;i<nplay;i++){
		pointer->next = malloc(sizeof *pointer);
		if(pointer==NULL){
			fprintf(stderr, "Out of Memory!\n");
			exit(1);
		}
		pointer=pointer->next;
		pointer->next=NULL;
		pointer->alive = 0;
		pointer->evasions = 0;
		pointer->kills = 0;
	}
	p=root;
	srand(time(NULL));
	for(i=0;i<nplay;i++){
		
		while(1==1){
			randn = rand() % nplay;
			pointer=start;
			for(j=0;j<randn;j++){
				pointer=pointer->next;
			}
			if(pointer->alive==0){
				break;
			}
		}
		strcpy(pointer->name, p->name);
		pointer->alive=1;
		p=p->next;
		
	}
	
	pointer=start;
	
	while(pointer->next != NULL){
		printf("%s\n", pointer->name);
		pointer = pointer->next;
	}
	printf("%s\n", pointer->name);

	p = root;

	while(root != NULL){
		root=p->next;
		free(p);
		p=root;
	}

}

Return a pointer to root node from getpeople() to main() and you should be good to go.

but once that function closes wont all that memory be freed?

Originally Posted by PickleBranston

but once that function closes wont all that memory be freed?

I don't think you fully read my last post, or maybe you just didn't understand it.

If you allocate memory for a list node using malloc, the memory lives on until either
1. you explicitly free it using the free() function
2. your program terminates and the OS cleans everything up

All the (non-static) variables you declare in a function will disappear when the function is over, but the memory you allocate during that function stays. Thus, in your getpeople function, the following variables would disappear once the function exits: nplay, i, j, check, randn, line, root, p, start, pointer; your linked list would live on.

When a pointer variable like root goes away at the end of your function, it doesn't mean that the allocated memory goes away. A pointer is like an entry in an address book. If you erase the entry, it doesn't mean that that person and their house magically disappear. They're still there, you just don't know how to contact them anymore, or where to find them.

ok i got it now, so as long as the getpeople() function returns a pointer to the linked list i want then i have what i need.


Thanks for all the help guys