5 replies to this topic

[c0mputer-fr0d]

I would really like help with understanding linked lists more. I get the gist of them but I don't understand how you can have a variable number of nodes without using an array of structs. What I do understand is that you have a bunch of structs , the head struct has a ptr variable that links to the first one and then that one links to the 2nd one and so on.They all have a data value and a ptr but the tail's ptr points to null which indicates the end. This is what I've made so far

 typdef struct Node0{
		   int Addr_Val;
		   Node0* Next;
	    }Node;
    Node* Head = (Node*) malloc(sizeof(Node));
    Head->Next = NULL; // I suppose when I go to my add link function I just do Head->Addr_Val = numinput and Head->Next = nextnode?
    Node* Tail;
    Tail->Next=NULL;

I don't really know where to go from here as I don't understand how you can keep creating nodes without using realloc of a struct array, which wouldn't be a linked list from what I've been told. All the snippes I've seen have predefined nodes or I'm not undertstanding the code properly.
http://www.cprogramm...l/lesson15.html
http://cslibrary.sta...dListBasics.pdf
All look to me like they have predefined nodes.

[Reedbeta]

The "malloc" is the secret sauce there. Whenever you do "(Node*) malloc(sizeof(Node));" you're getting a brand-new node freshly allocated. You can do this inside a loop or a function or wherever, to create exactly as many nodes as you want. And you can create some nodes now and some later, so you don't need to know ahead of time exactly how many you'll need, like with an array.

Internally, the memory for these nodes comes from a place called the heap. The heap is just a large block of memory that the OS sets aside for you when your program starts up. It's distinct from the stack (where local variables live) and the data space where global variables live. Anytime you call malloc() you're reserving a piece of the heap and it gives you back a pointer to that piece, which you can use for whatever you need. That memory remains reserved until you call free() on it, or your program terminates.

[c0mputer-fr0d]

This is interesting I knew the heap was runtime memory but , don't you have to name a new struct and then use malloc() on it

struct node* head = NULL;
struct node* second = NULL;
struct node* third = NULL;
head = malloc(sizeof(struct node)); // allocate 3 nodes in the heap
second = malloc(sizeof(struct node));
third = malloc(sizeof(struct node));

this is code from http://cslibrary.sta...dListBasics.pdf , it looks to me like he has to explcitly declare those structs before he uses them and is not making new ones based on users adding new things . Am I not understanding whats really going on?

[TheNut]

fr0d, how much do you know about pointers? The idea here is that you create a new node object when you want to store a new item value. In your case, the Addr_Val is your node's item value. The "head" and "tail" are special members of a linked list that allow you to retrieve the first and last nodes in the list for traversal. They should be strictly assigned (pointing to) nodes that already exist. Once you get your starter node, you can use the "next" or "previous" fields (in a doubly linked list) to navigate the chain.

For sanity sake, don't pre-create your nodes all at once. Make sure your head and tail pointers are set to null. Create one node object, set its item value, and then add it to the list. By adding it to the list, if tail is null, point the head and tail to this new node. There's only one node at this point and it is both the first and last node in the list. The node you create will by default have its next and previous pointers set to null (ie: it's not attached to anything). When you create and add another node, if the tail is not null, then set tail->next to this new node you want to add and then point the tail to this new node, which will now become the last node in the list. Continue this process as needed.

[Reedbeta]

c0mputer-fr0d, on 15 October 2012 - 02:39 AM, said:

don't you have to name a new struct and then use malloc() on it

Those variables are pointers, not structs themselves. The * after 'node' in the declaration makes it a pointer. They don't contain the actual structs; they just contain the memory address of wherever the struct is on the heap. But you can have several pointers to the same struct, and the struct will continue to exist even without pointers.

To add a link to the list you would write a function that defines a pointer, calls malloc() to create a new node and make the pointer point to it, then stores the data and hooks it into the list. Then when that function returns, the pointer (a local variable) would go away, but the node still exists, and since it was hooked into the linked list you can find it again later by following pointers through the list. The only thing you need to keep around permanently is just one pointer to the head node, so you can find the beginning of the list. (You might maintain a tail pointer as well for convenience, but this is not strictly necessary.)

[c0mputer-fr0d]

Thanks guys. "Then when that function returns, the pointer (a local variable) would go away, but the node still exists" - this really helped me I thought the pointer would just stay there and you would keep over writing it or something , I was really mixed it.