If we forget about the computer in front of us, then a linked list is like a long roll of paper. A long roll of paper on which we can keep jotting down points one after the other without knowing how many points will be there at the end. Like this: + "potato" + "onion" + "garlic" + "roses" + "jasmine" And every time I write down something with (eg., + "rose"), I unroll the paper a bit to accomodate the new entry. * mavu (n=mavu@59.178.188.219) has joined #dgplug I keep unrolling the paper till the roll runs out. * amrita has quit (Nick collision from services.) So if we open our eyes and look at the computer in front of us, we can find some similarities between our roll of paper and the computer. * amrita_ is now known as amrita The primary memory (or RAM) is the equivalent of the paper roll. And instead of jotting down things on a paper, we store data in the primary memory (we will use memory as a synonym). So the deal is to store data. * mavu__ (n=mavu@59.178.169.8) has joined #dgplug Doubts? please forgive my UPS quirks no * amrita has quit (Read error: 104 (Connection reset by peer)) mavu__: Happens. * chacha_chaudhry (n=rpmbuild@gnu-india/supporter/rakeshpandit) has joined #dgplug Ok. no Before moving further ahead, lets have a brief look at something else. * amrita (n=amrita@117.201.96.153) has joined #dgplug What if we were jotting down points on a torn sheet of paper instead of a paper roll? A torn sheet of paper is limited in length and unlike a paper roll can not be unrolled to get fresh paper. So if the sheet has space for 10 lines, you can only add 10 lines. Not 11, not 12, not 100. This torn sheet of paper is basically an array. * Debashree_ (n=Debashre@117.201.97.235) has joined #dgplug * karunakar has quit ("Leaving") Just like the size of an array is pre-determined before it is used, the length of the sheet is fixed. So the advantage of using the paper roll (or linked list) over a torn sheet (or array) is that you need not be bothered about how many points (or data elements) you need to store beforehand. Doubts? none till now no no. no Nice. no So the crucial part in using a paper roll is unrolling the roll to make space for new points. In terms of a computer, it is what we call allocating a new node. So as I wrote earlier, points in a paper roll will look like: + "roses" + "garlic" * mavu_ has quit (Read error: 110 (Connection timed out)) + "potato" So if "rose" is the data, the "+" represents the node containing the data. And every time we add a new point we add a new "+" or allocate memory for a new node. Doubts? none. * Soumya (n=Soumya@117.192.10.125) has joined #dgplug no * amrita_ (n=amrita@117.201.97.232) has joined #dgplug So let show you the C code for writing new '+'s or allocating memory for new nodes. struct node { char data; struct node * next; }; ... ... struct node * newnode; newnode = (struct node *) malloc (sizeof (struct node)); if (newnode == NULL) * rtnpro has quit ("http://www.mibbit.com ajax IRC Client") error (EXIT_FAILURE, 0, "malloc: out of memory"); newnode->data = 'r'; newnode->next = NULL; The malloc function does the magic of allocating some memory for us. It unrolls the paper. To make this memory usable as a linked list node, we type the address of the memory and store it in a pointer (variable storing addresses) to a 'struct node'. Just have a look at 'struct node'. It has space to store some data. For simplicity I have used a character as data. So instead of storing "potato", "rose" and "garlic" we will store 'p', 'r' and 'g'. Any doubts with this code snippet? not yet. * mavu has quit (Read error: 110 (Connection timed out)) nope So we have our first entry in the linked list. no We usually remember the first entry (or '+') for future use. rishi_, the error function's parameters please explain * Debashree_ has quit ("Leaving") arpita: $ man 3 error It basically prints out a error message and exits the program and returns the first argument as its exit code. * rtnpro (i=756308a0@gateway/web/ajax/mibbit.com/x-145b36576fbf4f1f) has joined #dgplug Ok. So let me elaborate the earlier code a bit more: struct node { char data; struct node *next; }; struct node *list = NULL; struct node * new_node (struct node *list, const char data) { struct node *newnode; newnode = (struct node *) malloc (sizeof (struct node)); if (newnode == NULL) error (EXIT_FAILURE, 0, "malloc: out of memory"); newnode->data = data; newnode->next = NULL; if (list == NULL) return newnode; /* some more code */ ... ... return list; } Now I have encapsulated the earlier code into a function. The function is still incomplete, so don't start compiling it yet. * chacha_chaudhry has quit (Read error: 110 (Connection timed out)) * munichlinux has quit (Read error: 110 (Connection timed out)) * amrita has quit (Read error: 110 (Connection timed out)) * amrita_ is now known as amrita kushal: Shall we use pastebin for code samples? If we use pastebin, they will not be a part of the logs. rishi_, on te, I will put them on log later rishi_, I will do the manual work, no problem rishi_, go ahead http://fpaste.org/paste/5767 ---------------- #include #include struct node { char data; struct node *next; }; struct node * new_node (struct node *list, const char data) { struct node *newnode; newnode = (struct node *) malloc (sizeof (struct node)); if (newnode == NULL) error (EXIT_FAILURE, 0, "malloc: out of memory"); newnode->data = data; newnode->next = list; return newnode; } int main (void) { struct node *list = NULL; list = newnode (list, 'r'); return 0; } -------------------------- Everybody please have a look. There is a slight difference between this code and our paper unrolling. Instead of adding new elements at the back of the list, we are adding them in front. Doubts? * rishi_ is waiting its giving some errors It might. I am writing them impromptu. It is more important for you to be able to read and understand the code. yupp...some errors... seems fine.. Since the idea is for you to be able to write it yourself. Copy pasting into a editor and compiling doesn't serve the purpose. :-) rishi_: ! rtnpro: Ask. what do you mean by rishi_: Is NULL the value of the pointer list? rtnpro: Which line are you referring to? rishi_: line 28 rtnpro: Initially the list is empty. ie., no paper has been rolled out from the paper roll. * Soumya has quit (Read error: 110 (Connection timed out)) So we represent that in the computer with a pointer pointing to NULL (ie., nowhere). * Soumya (n=Soumya@117.192.6.210) has joined #dgplug rtnpro: Am I clear? * rishi_ is waiting yes * amrita has quit (Remote closed the connection) What did you do by this program? It will create a list having a single node only, isn't it? rtnpro: Yes. * Debashree has quit ("Leaving") http://fpaste.org/paste/5768 is more interesting now. ----------------------- #include #include #include struct node { char data; struct node *next; }; struct node * new_node (struct node *list, const char data) { struct node *newnode; newnode = (struct node *) malloc (sizeof (struct node)); if (newnode == NULL) error (EXIT_FAILURE, 0, "malloc: out of memory"); newnode->data = data; newnode->next = list; return newnode; } void traverse_list (struct node *list) { struct node *cur; for (cur = list; cur != NULL; cur = cur->next) putchar (cur->data); putchar ('\n'); return; } int main (void) { struct node *list = NULL; list = new_node (list, 'r'); list = new_node (list, 'g'); list = new_node (list, 'j'); traverse_list (list); return 0; } ----------------------- rishi_: got it Bascially our list looks like this: list ----> ('j',

) ----> ('g',

) ----> ('r', NULL) ----> * Soumya_ (n=Soumya@117.192.6.210) has joined #dgplug * Soumya__ (n=Soumya@117.192.6.210) has joined #dgplug Please note that each node does not only contain the data part. The address of the next node is also noted. * mavu__ is now known as mavu This has some advantages. Since we are noting the address, there is no need for consecutive nodes to be in contiguous memory locations. * abc (n=Soumya@117.192.6.210) has joined #dgplug So unlike our paper roll which is one long strip, our list is more flexible. It is scattered all over the memory with each node knowing the location of its successor. This is an advantage over arrays as well. Since arrays are one single chunk of memory, it might become difficult to get one very big chunk to be allocated to an array. However it is far likely that you will have empty spaces scattered here and there. Questions? * Soumya has quit (Remote closed the connection) * abc has quit (Remote closed the connection) * Soumya_ has quit (Read error: 104 (Connection reset by peer)) * Soumya__ has quit (Read error: 104 (Connection reset by peer)) rishi: won't searching the next nodes take time in case of linked lists rishi_: since it is scattered rtnpro: Depends on what you mean by the term searching. rtnpro: But yes, linked lists are inherently associated with algorithms of complexity O(n). Arrays on the other hand can be accessed in O(1) given we know the index of the element. rtnpro: searching means to find a partcular data rishi_: ! rtnpro: Yes, that will take O(n). rtnpro: Assuming that you don't know the address of the node having the data. rtnpro: Ask. rtnpro: Ask. arrays are linear arrangement of data and a continuous allocation of bits but linked lists are not continuous aren't then operating on arrays faster? since in arrays you get all the data in one place rtnpro: "operating" is a vague term rtnpro: Inserting and deleting something in the middle of an array is costly. It is cheaper for a linked list. But yes, if you are looking for random access nothing beats an array. ok...and rams are expensive...got it rishi_: thanks Any more? * rishi_ thinks everyone understood no you can continue i thnk so... Essentially this enough to understand the basic concept of a linked list. Since every node has a link to its successor, we use the adjective 'linked'. Often the node in a linked list is termed as a self-referential structure. 'self-referential' since it has a pointer to an object of the same type (ie., another struct node). So can you write the code to insert a new element into a list. ? Say you are given the address of a node and a data, and you have to insert a new node containing the data after the given node. yes...we can try rtnpro: Ok. Let us know when you have made some progress. Others? yeah trying.. yes trying mavu: Not you. :-) mavu: I have something slightly more interesting for you. :) and that is.. * Soumya (n=Soumya@117.192.6.210) has joined #dgplug everyone quiet or is it my xchat again? hehe same question here ah :D good we gave each other the answer * ria (n=ria@59.161.115.199) has joined #dgplug rishi_, you there ? kushal: Yes. rtnpro: Done? trying mavu: Can you write a linked list in C which is not bound to a specific data type? me too a bit more kishan: Trying? hmm... can try :) yes mavu: Nice. kishan: How far? all basic types of the type can be user defined too? * arpita has quit (Read error: 110 (Connection timed out)) ria, oh. ok http://fpaste.org/paste/5769 s/ria/rishi_ mavu: Yes. kishan: That is not a linked list. kushal: ? kishan, that looks like a single wagon http://fpaste.org/paste/5770 kishan, we are looking for the train a part... ria, nothing kishan: Here is the prototype of the function: eh...still writing... struct node * insert_node (struct node *node, char data); It should return the address of the node it inserted. kushal: :-) eh rishi_, that was for you :p kamalx: You are close. kamalx: Lines 7-8 are a bit messed up. rishi_: guess i missed the return? kamalx, and next value for the last node No need for the return. Your function returns void anyway. yeah ok kamalx: newnode->next = last->next; kamalx: ^^^^ needs to be somewhere. oh right :) * rishi_ waits oh no.. i got confused.. `newNode` is the one just created. and `last` was the one passed to this function to append after so shouldn't i update the pointer of last->next to the address of this new node? kamalx: Yes. and the next in this new node should be NULL then? kamalx: It should be the successor of 'last'. yes. isn't this also the last node appended in the list. or can it be anywhere in between.. ah. now i got it.. :P kamalx: Nice. i guess i have an idea how to do mavu: How? What about the others? Has everyone fallen asleep? rishi_, ah sorry was not following the conversation here.. was talking about the program you asked me to do * sunny_slls (n=sunny@125.20.11.34) has joined #dgplug mavu: Me too. :-) i was doing it with type def declare whatever structure you want and typedef to 'datatype' then write a normal linked list program where the data is of the type datatype or type of void * ? mavu: I like kushal's approach. rishi_: http://fpaste.org/paste/5771 http://mibbit.com/pb/PTqE6p mavu: But thinking of it now, I think you have an interesting idea. rishi_: here's the link void * will take away all the type checking. rtnpro, btw , try some better pastebins liek rafb or fpaste can you please explain how should i allocate memory if i have type void? will there be 2 mallocs? one for the flexible data size and the other for node? s/liek/like ok rishi_: ! mavu: You can ask the user to pass you a void* pointer and length of the data. mavu: Something like write(2). rtnpro: Ask. * Subhodip has quit ("Pants on Fire .. Angry elephant chasing ...ar ki ki hote pare ??") did you check my code? rishi_: ! mavu: If you are trying the typedef approach it should work if we are writing a library providing a linked list. its not running kamalx: Your code looks fine. But there is one problem. kamalx: It might crash in some cases. rtnpro: Your implementation looks wrong. rishi_: where? struct node * insert_node (struct node *node, char data); rtnpro: See ^^^^^^^^^^^^ the prototype does not match. kamalx: Everytime you dereference pointers passed to you by some unknown party, do a NULL check. ok ! can't I keep return type void for the ins function? * kishan has quit ("http://www.mibbit.com ajax IRC Client") rtnpro: Better not to, but even then the rest is a mess. * Soumya has quit ("Leaving") rishi_: so the whole thing should be in a 'if(last!=NULL) { ... }' block? kamalx: You can do something more interesting. Assume that if last == NULL, then you are going to add the node at the beginning of the list. ah.. yes :) * mib_baxhw9 (i=75630007@gateway/web/ajax/mibbit.com/x-c045dc6f80be4384) has joined #dgplug sorry...got disconnected ! * mib_baxhw9 is now known as kishan mavu: Yes? ! um i am trying the void* approach as the typedef one had occurred to me and implementation is almost identical to the normal one.. but i do not get how to implement cases where the type itself is a user defined type.. like if i have a struct with a char and an int, how do i implement a linked list of that struct with void*? i do not get how to say take the first byte for char and the rest 2 of the data that i send as int Just allocate a block of memory and let node->data point to it. I guess node -> data = (void *) &mystruct_value node->data is also void*. ah so it will automatically divide? thanks :) rishi_: http://mibbit.com/pb/uvmhjo I think we will stop here today. rishi_: could you see why still I am getting segmentation fault rtnpro, use gdb and find rtnpro, pjp taught how to use it rishi_, I also think it is good time to stop for tonight I think we will stop here today. Most people seem to have gone to sleep.