Sign in to follow this  
The_Marlboro_Man

Linked lists in C.

Recommended Posts

Hello!. While this is not an specifically game-oriented question I think I could understand and apply linked lists to different game concepts (like... Creating enemies, bullets or items on a screen, I think) in C programming. Anyway, I came up with some code to do a linked list (or at least its beginning...) but I have a few questions about them. -Is it necessary the use of pointers and "pointers to pointers" to create linked lists? (I assume a big "yes" for answer and think I understand it but I wouldn't mind a bit of help for a better understanding). -Is it absolutely necessary to use the malloc function to create linked lists?. This is a bit of code that you may have seen thousands of times. On it you can see I commented a working method of creating the first element of the list (calling a function that returns a pointer of allocated memory) and another method, uncommented, that doesn't work...
#include <stdio.h>
#include <stdlib.h>

struct nodo
{
	int dato;
	struct nodo * siguientenodo;
};

void crearnuevo(struct nodo **cabecera, int dato); //This function creates a node.
struct nodo *NuevoElemento(); //This other returns a pointer to a node for helping the first.

int main()
{
	struct nodo * cabecera=NULL;  //Pointer to the header of the list, now empty.
	int dato=0; int cosa=0;  //Miscellaneous data.

	printf("\nIntroducir dato: "); //Requesting data.
	fflush(stdin);
	scanf("%d", &dato);

	if(dato) 
	{
		crearnuevo(&cabecera, dato);
		printf("\nEl valor es %d", cabecera->dato);
		printf("\nEl valor es %d", cabecera->dato);
		printf("\nEl valor es %d", cabecera->dato);
	}
	return 1;
}

void crearnuevo(struct nodo **cabecera, int dato)
{
	/*struct nodo *nodocreando=*cabecera;  //THIS PART WORKS.
	if(nodocreando==NULL)
	{
		printf("\nCreando PRIMER elemento");
		nodocreando=NuevoElemento();
		nodocreando->dato=dato;
		nodocreando->siguientenodo=NULL;
		*cabecera=nodocreando;
	}*/                                    //This other doesn't work.
	struct nodo nodocreando;               //A "real" node.
	struct nodo *punteroanodo=*cabecera;   //A pointer to a node, first to the header.
	if(punteroanodo==NULL)                 //Check for an empty list.
	{
		printf("\nCreando PRIMER elemento");
		nodocreando.dato=dato;         //Filling the "real" node.
		nodocreando.siguientenodo=NULL;
		punteroanodo=&nodocreando;     //Point the pointer to the "real" node.
		*cabecera=punteroanodo;        //Point the header to the pointer.
	}                                      //Shouldn't the header point to the "real" node memory location?.
}

struct nodo *NuevoElemento()
{
  struct nodo *puntero = (struct nodo *)malloc(sizeof(struct nodo));
  if (!puntero) printf("ERROR");
  return(puntero);
}

I'm not sure about why the second method doesn't work but I think it could have something to do with the "real" node being destroyed when the function ends, so the header (pointed to a pointer to the "real node" :S) ends up pointing to nowhere. What's strange is that on the three printf's I put there you have a "real" result on the first print and strange ones (trash, I guess) on the others. So, why isn't the second method working?. Is the "real" node rendered obsolete and deleted?. Do I need to use malloc to get an "undeletable" space in memory for my node?. As always, thanks a lot in advance for your replies.

Share this post


Link to post
Share on other sites
Your second method doesn't work because you're creating your head node on the stack (you're not using malloc -- which gives you a pointer to memory on the heap) which is scoped local to that function. When the function terminates, the space on the stack is reclaimed meaning that you're left with a dangling pointer. By using malloc, you ensure that whilst any local pointers to the heap memory may disappear after the function terminates, the memory itself is still valid to use afterwards (so you can keep a pointer to it).

I think you need to read up a little on scoping of variables.


EDIT: In short, the answer to your two questions (do you need to use pointers; do you need to use malloc) is yes.

Share this post


Link to post
Share on other sites
Thanks TheUnbeliever, that was very helpful.

As I thought in the previous post, it has to do with the memory (or the "node") being destroyed when the function ends (as it should be)... I do know little about the malloc function but expected it to "get an "undeletable" space in memory for my node" (now, valid memory sounds much better)... Anyway, expecting and thinking things seems not enough to me and since "heap" and "stack" are obscure terms for me I'll make sure to read a bit more (more than "Any local value is destroyed" :P) on scoping. Any suggestions :)?.

Still I'm clueless on how the code manages to give me a correct first output... I'm clueless on the internal working of the compiler too so maybe it's just that the space of memory for the node is still "alive"... or something.

As for the rest (specially for the pointers) I think I get a decent idea (decent for now) of the "how" and "why", specially the "why" (different positions in memory, pointers to new nodes, the impracticability of having like 300 instances of "real" nodes (with different names) for a list...).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this