Linked Lists

[Saggy]

All right, so the other night I had a crash course in multithreaded programming. It was fun, but when I tried making a linked list to hold the threads, I quickly came to the realization that I didn't understand how to implement them fully. Up until now I've simply dealt with lists of other libraries that have their own functions to work with them like socket programming.

 

So anyway, I've got the concept of the node in the struct that is the "next" node, but what's been getting me is allocating memory for that node. Take the following code for example...

 

 

#include <stdio.h>#include <malloc.h>struct linkedList {       int anInteger;       struct linkedList *nextList;};int main(int argc, char *argv[]){       if(argc != 2)       {               printf("Usage %s number-to-count-to\n", argv[0]);               return 1;       }       struct linkedList *list, *p;       list = (struct linkedList *) malloc(sizeof (struct linkedList));       p  = list;       int i , num = atoi(argv[1]);       for(i = 0; i <= num; i++)       {               p->anInteger = i;               p->nextList = (struct linkedList *) malloc(sizeof (struct linkedList));               p = (struct linkedList *)p->nextList;       }       for(p = list; p->nextList != NULL; p = (struct linkedList *)p->nextList)               printf("%i @ 0x%x\n", p->anInteger, &p->anInteger);       return 0;}

 

 

It took me a good hour or two before I realized that I needed to use malloc to allocate the memory for the pointer because I had been thinking it would allocate memory itself, and then it took me a night or so ( I was very tired ) to realize that I needed to allocate it to p->nextList and not just to p.

 

So is there any basic linked list principle I'm missing between the concept of the links themselves and the memory allocation? Most material I have that covers them has a very large "practical example" that doesn't really work, and tries to cover them too fast. It spends one page on singly linked lists, half a page on double linked lists, and basically uses that as a springboard into trees.

 

I also did it a little different than most linked lists they show, that allocate a structure with the normal structure declaration. I wanted to make the original structure ( the one you keep pointed to the beginning that is ) reside in the same range of memory malloc() was allocating to all the other nodes too, because then the memory addresses are offset at 16 bytes, and that seems like it would be very useful. The other way, the first structure is in a memory address all of its own. My question about this: Should I even bother, will malloc() keep allocating to memory with such a consistent offset, or is just sort of a luck-of-the-draw type of thing?

[K^2]

You're on the right track. However, a few things you should keep in mind.

 

1) Allocate right before using.

2) If you aren't using the pointer, make it null. It can be handy. Note how I'm using initial null state of list.

3) You don't need to use the keyword struct in declarations of variables. Only when you are declaring the structure itself.

4) You do not need to typecast p = p->nextList, because linkedList::nextList is already of the type linkedList.

5) Don't forget to cap off your list with a null pointer. If you are adding elements one by one, rather than with a loop, like here, which is what you'll be doing most often, you should cap off your list after adding each new node. Here, I only do this after the cycle.

 

This is what it should look like.

 

#include <stdio.h>#include <malloc.h>struct linkedList{       int anInteger;       linkedList *nextList;};int main(int argc, char *argv[]){       linkedList *list, *p;       int i , num;       if(argc != 2)       {               printf("Usage %s number-to-count-to\n", argv[0]);               return 1;       }       list = 0;       num = atoi(argv[1]);       for(i = 0; i <= num; i++)       {               if(list) p = p->nextList = (linkedList *) malloc(sizeof (linkedList));               else p = list = (linkedList *) malloc(sizeof (linkedList));               p->anInteger = i;       }       p->nextList = 0;       for(p = list; p->nextList; p = p->nextList)               printf("%d @ 0x%x\n", p->anInteger, &p->anInteger);       return 0;}

 

 

Also, using names like nextList is unnecessary. It is already in the linkedList namespace, so simply going with next would suffice. It is how the pointer to next node is most commonly called, and will make your code easier to understand if somebody else is reading it. Purpose of *next pointer is almost always understood to be a pointer to the next element in the list.

 

Another thing about style, it's always a good idea to declare all your variables before starting to perform any tests. Your code is more elegant that way, and also, certain types of memory leaks would be far easier to track. And memory leaks is something you'll have a lot of when using linked lists.

[Saggy]

You're on the right track. However, a few things you should keep in mind.

 

1) Allocate right before using.

2) If you aren't using the pointer, make it null. It can be handy. Note how I'm using initial null state of list.

3) You don't need to use the keyword struct in declarations of variables. Only when you are declaring the structure itself.

4) You do not need to typecast p = p->nextList, because linkedList::nextList is already of the type linkedList.

5) Don't forget to cap off your list with a null pointer. If you are adding elements one by one, rather than with a loop, like here, which is what you'll be doing most often, you should cap off your list after adding each new node. Here, I only do this after the cycle.

 

This is what it should look like.

 

#include <stdio.h>#include <malloc.h>struct linkedList{       int anInteger;       linkedList *nextList;};int main(int argc, char *argv[]){       linkedList *list, *p;       int i , num;       if(argc != 2)       {               printf("Usage %s number-to-count-to\n", argv[0]);               return 1;       }       list = 0;       num = atoi(argv[1]);       for(i = 0; i <= num; i++)       {               if(list) p = p->nextList = (linkedList *) malloc(sizeof (linkedList));               else p = list = (linkedList *) malloc(sizeof (linkedList));               p->anInteger = i;       }       p->nextList = 0;       for(p = list; p->nextList; p = p->nextList)               printf("%d @ 0x%x\n", p->anInteger, &p->anInteger);       return 0;}

 

 

Also, using names like nextList is unnecessary. It is already in the linkedList namespace, so simply going with next would suffice. It is how the pointer to next node is most commonly called, and will make your code easier to understand if somebody else is reading it. Purpose of *next pointer is almost always understood to be a pointer to the next element in the list.

 

Another thing about style, it's always a good idea to declare all your variables before starting to perform any tests. Your code is more elegant that way, and also, certain types of memory leaks would be far easier to track. And memory leaks is something you'll have a lot of when using linked lists.

Does everything you've said ( aside from namespace ) also apply to C as well? I thought that in C it was still necessary to declare with "struct structurename" unless you used a typedef.

 

 

Anyway, yeah, I would normally have had some better style but it was a bit rushed to try to get the hold of things, with things added hastily after trial and error, and the compiler giving me warnings as if I needed to typecast when I was just using the wrong pointer operators.

 

Good to know that I'm on the right track as far as the linked lists go though.

 

[K^2]

I was under the impression that "type variable" was sufficient to declare a variable. You can try it and see if it works. As far as casting, yes, it works exactly the same way under C. The only difference is that in C++ you can overload casting operators.

[xtal256]

 

I was under the impression that "type variable" was sufficient to declare a variable. You can try it and see if it works. As far as casting, yes, it works exactly the same way under C. The only difference is that in C++ you can overload casting operators.

C'mon K^2, you should know this one. You're a C expert aren't you . structs have to be declared like this:

 

struct Object {   ...};struct Object obj;

 

or:

 

typedef struct /*optional struct name*/ {   ...} Object;Object obj;

 

See here. I don't know why C has this obscure way of declaring structs, i guess i'm just used to the OO way.

 

On a related matter, SagaciousKJB, why do you use structs rather than C++ classes? There is no real difference between the two other than making the programmer's life easier. If you're not ready for more advanced OO topics like inheritance and polymorphism you can still use classes for that same thing as you are using structs for.

Edited May 23, 2009 by Haro

[Saggy]

On a related matter, SagaciousKJB, why do you use structs rather than C++ classes? There is no real difference between the two other than making the programmer's life easier. If you're not ready for more advanced OO topics like inheritance and polymorphism you can still use classes for that same thing as you are using structs for.

Well, I only took an into to C++ course, so to me it's not really "easier". Just a matter of comfort I suppose. Though I thought it was better suited to a struct than a class anyway, but I'm not really an OO thinker, so you may disagree with me there.

 

I have been wondering about polymorphism and how it can help me here. With this programming, there's a lot of stuff like this...

 

 

main(){pthreads(do functionC)pthreads(do functionD)}functionC(){...functionD(){...

 

 

Where functionC and functionD are extremely similar, but can not be handled in a convenient loop. I was going to see what polymorphism could do for me in that situation, or just figure out how to hold the function pointers in an array of some sort. `

[xtal256]

 

Just a matter of comfort I suppose.  Though I thought it was better suited to a struct than a class anyway, but I'm not really an OO thinker, so you may disagree with me there.

Well that's why i said that structs and classes are really not that different. It's not even a matter of using OO, you can just substitute the word "struct" with "class" (more or less) and make no other changes. I understand it's sometimes hard to change your style once you feel comfortable using it but i just can't see what advantages structs have over classes. Even if you use them in exactly the same way, there is nothing (as far as i know) that you can do with structs than you can do with classes.

Take this example:

 

// The C way://------------------------------------------------------------------typedef struct Object {   int var;};void doSomething(Object& obj, int i) {   obj.var += i;}main(...) {   Object obj;   obj.var = 0;   // Have to initialise var   doSomething(obj, 4); // Have to explicitly pass the object you want to work with}// The C++ way://------------------------------------------------------------------class Object {   int var;   Object() { var = 0; }   void doSomething(int i) {       this->var += i;   }};main(...) {   Object obj;    // Var is initialised in constructor   obj.doSomething(4);  // Don't have to pass object, done implicitly by <this> pointer}

 

 

Do you not agree that the C++ way is easier? To use an object*, all you have to do is create it and call one of it's functions. With C you have to also explicitly pass the object into any function that works on the object, it just seems redundant to have to tell the function that. The C++ this pointer does that for you.

 

* I use the term "object" loosely. A struct is also an object in that it represents something with some properties, even though C isn't strictly "Object-Oriented".

[K^2]

The only times I use a C compiler is when writing DLLs. So I don't get to play with it too often.

 

Sagacious, if the only differences are in how types are handled, you can try templates.

[Saggy]

 

Just a matter of comfort I suppose.  Though I thought it was better suited to a struct than a class anyway, but I'm not really an OO thinker, so you may disagree with me there.

Well that's why i said that structs and classes are really not that different. It's not even a matter of using OO, you can just substitute the word "struct" with "class" (more or less) and make no other changes. I understand it's sometimes hard to change your style once you feel comfortable using it but i just can't see what advantages structs have over classes. Even if you use them in exactly the same way, there is nothing (as far as i know) that you can do with structs than you can do with classes.

Take this example:

 

// The C way://------------------------------------------------------------------typedef struct Object {   int var;};void doSomething(Object& obj, int i) {   obj.var += i;}main(...) {   Object obj;   obj.var = 0;   // Have to initialise var   doSomething(obj, 4); // Have to explicitly pass the object you want to work with}// The C++ way://------------------------------------------------------------------class Object {   int var;   Object() { var = 0; }   void doSomething(int i) {       this->var += i;   }};main(...) {   Object obj;    // Var is initialised in constructor   obj.doSomething(4);  // Don't have to pass object, done implicitly by <this> pointer}

 

 

Do you not agree that the C++ way is easier? To use an object*, all you have to do is create it and call one of it's functions. With C you have to also explicitly pass the object into any function that works on the object, it just seems redundant to have to tell the function that. The C++ this pointer does that for you.

 

* I use the term "object" loosely. A struct is also an object in that it represents something with some properties, even though C isn't strictly "Object-Oriented".

Well, I just meant that I usually think about a way to do something in C much more naturally, and so I just get started in that very quickly. Thinking about doing something in C++ still involves too much thinking about the syntax and stuff.

 

For an example, instead of remembering what you have done in C++, I generally can just think up something like the following quicker.

 

 

struct Object {   int *var;};void doSomething(int i) {   obj->var += i;}main(...) {   struct Object obj;   obj.var = malloc((sizeof(int));   doSomething(4); // Have to explicitly pass the object you want to work with}

 

 

I mean, what's the point of using the "this" pointer ( which frankly I've never understood ) over just a pointer.

[xtal256]

I mean, what's the point of using the "this" pointer ( which frankly I've never understood ) over just a pointer.

Well it's just easier and more logical when you think in terms of objects. By calling a member function on an object, you are telling the object to perform that task on itself (e.g. linkedList.print() tells the file to print itself to the console) rather than telling a function to perform a task on an object (e.g printList(linkedList) tells the function to print a LinkedList object). This way each object knows how to perform tasks specific to itself and you don't need to expose how it works to other parts of your code. The "this" pointer is just a way to let an object know who it is.

This may not seems necessary to you right now but it makes sense when you are writing large, complex programs.

 

Also, the code you posted, that you can "generally can just think up quicker" is wrong.

 

main(...) {  struct Object obj;  obj.var = malloc((sizeof(int));    <-- var is not a pointer, you don't need to malloc  doSomething(4);     <-- You need to pass the object in too}

 

Maybe you were just tired when you posted that

[Saggy]

I mean, what's the point of using the "this" pointer ( which frankly I've never understood ) over just a pointer.

Well it's just easier and more logical when you think in terms of objects. By calling a member function on an object, you are telling the object to perform that task on itself (e.g. linkedList.print() tells the file to print itself to the console) rather than telling a function to perform a task on an object (e.g printList(linkedList) tells the function to print a LinkedList object). This way each object knows how to perform tasks specific to itself and you don't need to expose how it works to other parts of your code. The "this" pointer is just a way to let an object know who it is.

This may not seems necessary to you right now but it makes sense when you are writing large, complex programs.

 

Also, the code you posted, that you can "generally can just think up quicker" is wrong.

 

main(...) {  struct Object obj;  obj.var = malloc((sizeof(int));    <-- var is not a pointer, you don't need to malloc  doSomething(4);     <-- You need to pass the object in too}

 

Maybe you were just tired when you posted that

Well, actually I redeclared the struct as

 

 

struct Object{int *var};

 

 

Though I was considering later whether obj->var was correct later on, which it is not, should be

 

 

#include <stdio.h>#include <malloc.h>struct Object {       int *var;};void doSomething(int i);{       *obj.var += i;int main(){       struct Object obj;       obj.var = malloc(sizeof(int));       doSomething(4);       return 0;}

 

[xtal256]

Well, actually I redeclared the struct as

 

 

struct Object{int *var};

 

Oh, ok... Why? ints don't need to be pointers, you can just use an int. If you had an object (i.e. struct or class) then you could use a pointer but since an int is atomic (isn't made up of more variables) then it doesn't need a separate location in memory. Even if you did have an object as a member variable you don't have to use a pointer.

Still, your call to doSomething(4) is wrong.

[K^2]

 

I mean, what's the point of using the "this" pointer ( which frankly I've never understood ) over just a pointer.

Lets start with the fact that old C++ compliers produced C code as their output, so there is absolutely nothing you can do in C++ that you cannot replicate in C. But same thing can be said about assembly and machine code, as these are the next two steps in compilation of the source code. It's all about convenience and forcing you to use good coding practices.

 

It's often convenient to have self-managed objects. In that case, use of this simply prevents you from messing something up. The methods working with the object will always manipulate data belonging to that particular object. One less pointer for you to worry about.

 

For example, look at this code.

 

class list{public: list(void); list *add(void); int data; list *next;};list::list(void){next=0};list *list::add(void){list *ret;ret=this;while(ret->next)ret=ret->next;ret=ret->next=new list;ret->next=0;return ret;}int main(void){list root,*p;int i;root->data=0;for(i=1;i<10;i++)root.add()->data=i;for(p=&root;p;p=p->next)printf("%d\n",p->data);return 0;}

 

 

Now compare the main here to the main you originally posted. Yeah, you could write up something like that with structs. You can even use function pointers to create methods. A C struct like this:

 

struct list{struct list*(*add)(struct list*);int data;struct list *next;};

 

 

Does exactly the same thing as list class above. You'd call root.add(&root), instead of just root.add(), but other than that they are identical. In fact, under C++ you can typecast one into the other. However, the use of a class as your list base practically forces you to write the code in the above style, simplifying the flow and your ability to follow it. Once you created a good clean class under C++, you know that the class will be working, and if something in your program doesn't work right, you don't have to look there.

 

You can take this a step further. Something I don't do above is make use of public/private members. There is a good reason for them. For example, if instead of starting with root being on the stack, I created it dynamically, there is a chance that something went wrong, and root would be a NULL pointer. In that case, so will this. The way you work around it is by declaring data and next as private, and use methods for accessing them. Consider this code:

 

 

#include <stdio.h>struct list{public: int &data(void);private: int ddata; static int sdata;};int list::sdata=0;int &list::data(){if(this)return ddata;return sdata;}int main(void){list *a,*b,*c;a=new list;b=c=0;a->data()=5;b->data()=6;c->data()=7;printf("a->data()=%d\nb->data()=%d\nc->data()=%d\n",a->data(),b->data(),c->data());return 0;}

 

 

The output is, of course, 5,7,7. Why? Because b and c being null, their data() is the static sdata field shared between all members of the list class. Why is that convenient? Because if you ran the same main code using the declaration of the list class from the first example, the statement b->data=6 would result in a crash. Here, the data goes somewhere you perhaps didn't intend it to, but the program keeps running, which will make debugging a lot easier.

 

Again, you can do this with C, but you probably won't, and whatever you come up with will most certainly not be as easy to follow.

[xtal256]

The output is, of course, 5,7,7. Why? Because b and c being null, their data() is the static sdata field shared between all members of the list class. Why is that convenient? Because if you ran the same main code using the declaration of the list class from the first example, the statement b->data=6 would result in a crash. Here, the data goes somewhere you perhaps didn't intend it to, but the program keeps running, which will make debugging a lot easier.

 

Again, you can do this with C, but you probably won't, and whatever you come up with will most certainly not be as easy to follow.

What!?! That's horrible code, K^2, you should know better! The only thing worse that a program that crashes on an error is a program that doesn't crash on an error and keeps going without telling you. If something went wrong and the pointer was NULL, it should throw an error (being C++) and let the client handle it. Besides, i'm not sure if i follow correctly but if "this" was NULL wouldn't calling a member function also crash? Hence, b->data() wouldn't work. And why are you trying to assign a value to the result of calling data()? I will forgive you if you were writing that at 2am but otherwise i am ashamed of you

[K^2]

A program that crashes or stops working on an error is a terrible one. Granted, error should be logged (which is something I omitted above), but if you try to assign a value to a property of a structure or class pointed to by NULL, you get a GPF. Instant crash, with no logging, unless you had an external runtime managing it.

 

All member functions are static pointers by default. So you can call a member function of the NULL pointed class. Checking if this is NULL is a standard practice in writing secure, stable code for that very reason.

 

Note that list::data() returns result by reference. That makes the result a legal L-value. You can assign to any L-value you want. And since addresses of these L-values are either a static member of list or a property of an actually existing list object, you'll never get a GPF.

 

By the way, I compiled and ran that code. It's fine.

[xtal256]

Ok, ok, you're right . But using a member function to return a reference is not usual practice (as far as i have seen), usually you create getters and setters. So you can forgive me for thinking you had gone completely crazy .

And i didn't say that a program crashing was a good thing (well i didn't mean to say that), but it's even worse to just let the program keep running without telling you. At least if a program crashes you know something has gone wrong and you can debug it.

[K^2]

Oh, I'm all for program reporting anomalies. I'm only pointing out that debugging is not that different from medicine. Biopsy is preferable to autopsy. And I really didn't feel like putting in all the error reporting code into that little example.

 

Also, if you are coding under time constraints, there can be situations where finding a bug takes too much time, but if you detected it, you know how to recover without crashing. It's far from the ideal solution, but if the code needs to be up and running by tomorrow or it's your head, that is a viable option. If you build your classes from start to be capable of withstanding heavy abuse from parent code, which might not even be your work, it can save you a lot of trouble.

 

 

usually you create getters and setters

Depends on what you are doing. There are many situations where getters/setters result in ugly code. You really have to know how to use both ways of working with data.

 

I have a program that I've been working on for a while. It has to perform some rather bizarre manipulations with certain data sets, which requires rather rapid destruction and creation of certain objects. On the top level it has an entirely static memory management class with templated method library, because malloc() is way to slow for this. It handles garbage collection for a variable number of list classes and keeps track of memory usage. Each of the list classes can be extended into a templated self-managing list class, which expands search capabilities at a certain hit to the memory allocation. Finally, the lists themselves contain data classes which have various algebraic and type casting operators defined for them. Simplest of these classes is a vector class, which interacts with other classes involved in linear algebra.

 

If I used getters and setters for this one, I'd still be writing definitions for all the things I might want to get or set.