C programming Pointers and Linked List Questions

[JC724]

I have a few questions that came up for me while I have been writing my program in my Operating Systems class. I got my program to work so I am not asking for help with my homework BUT I am really confused as to why some things I originally tried did not work. I good tons of examples online and nothing really answered my questions. Also I am very new to C programming. Most of my experience is in C++ and JAVA.

I was trying to delete the head of a linked list via a function that returns the deleted head.

EX: (I will make this a little generic but still to get my point across
struct nodeName *DeleteHead(Struct node *head) {
deleteHead = head;
head = head->next;

return deleteHead;
}//end of function DeleteHead

So I don't understand why this doesn't work. When I return to my main function. The head of the node has not be removed. Next thing I tried was to pass the actually address of the head function in the parameter with &head but this causes an error. To remove the head I would have to do head=head->next in the main function but deleteHead would return the head of the head->next not the originally head.

so I ended up doing something like this in the function above. It works in the function and in MAIN function but I don't understand why my other two ways didn't work above??? And I would expect this to work but I don't know why I need to do it.

struct nodeName *DeleteHead(Struct node *head) {
struct nodeName *deleteHead = malloc(sizeof(nodeName));
//placing head in deleted head address
*deleteHead = *head;

//used to move head to head->next
struct nodeName *temp = head->next;
head->data = temp->data;
head->next = temp->next;
free(temp);

return deleteHead;
}//end of function DeleteHead

1st. Question: Why does "Struct node *head" in the parameter of the function does not pass the pointer by reference? I thought all pointers where pass by reference by default?

2nd Question: Why does the original head = head->next in the function not work?

3rd Question: I don't understand why if I did deleteHead=head in the Function and I did head = head->next in the Main function(where it deleted the head), why did deleteHead move to the head->next. I wanted it to stay at the original head.

Like I said my program works, but I DO want to understand why it didn't work before as I like to learn and be more efficient.

Also I am looking for some other forums to join, that are similar to this one: where I can ask questions as well as read others post to learn from.

Thanks for your help.

 

[rsquared]

Pointers are not pass by reference, but in C all passing by reference is done with pointers. The parameter "struct node* head" is passing the pointer by value. The original "head = head->next" is modifying the function's value of head copied from the function call, not the function-caller's value of head. When DeleteNode returns the changes are lost. If you want to pass a pointer by reference, then you need to pass a pointer to the pointer.

struct nodeName* DeleteHead(struct node** head) {
struct nodeName* deleteHead = *head;
*head = (*head)->next;
return deleteHead;
}//end of function DeleteHead​

Note that head is dereferenced with * when used in the function, taking away that second level of pointer.

When you call DeleteHead, then, you give it a pointer to your list-head pointer with the address-of operator &:

struct node *head = ...;
DeleteHead( &head );​

Which you already tried, but DeleteHead was expecting a pointer, not a pointer to a pointer, which is why you got the error.

 

[Absalom]

Another way to look at it:

A pointer is a special type of variable. And since it's a variable, it follows the same convention as other primitive types (i.e. int, char, etc.). Pointers can use the same built-in math operators (+,-,*,/) that ints, doubles or char can use, so, in that respect, they are pretty much treated the same. The key difference being that pointers must be dereferenced to get to the very thing they point to. It's that extra level of indirection that can make things confusing to anyone new to the C/C++ language. Think of a pointer as a variable that stores a memory address. So, for example, if you provide a pointer as a function argument, copying a memory address is equally or generally faster than copying the data structure it points to, right?

Data type declarations in C often, but not always, come in pairs, the data type itself and its pointer equivalent.

int i;    // variable to store an integer type
int* j;   // variable to store a pointer (or address) of an integer type

In theory, you could write an entire program with nothing but pointer types. You probably won't be popular with your coworkers if you do, but just saying...

Whenever you see a star (*) in a type declaration, read it right to left. i.e. "This is a pointer to data of type..." Don't get too caught up into the semantics of pass-by-value or pass-by-reference, as those are object oriented language terms. If you're dealing with C (and to some degree C++), then you are in control of how data is read or written to. Your implementation will determine how your function behaves (i.e. the whole notion of pass-by-reference or pass-by-value). Most OO languages don't let you get under the hood like C/C++ does, so such terms are better left to higher levels of abstraction (not to dismiss them entirely as they are important design concepts).

If you're not dealing with pure C, but make allowance for C++, there is also a third type, and often underused, the C++ reference type.

int& k = i;

In the simplest term, a reference type in C++ is an alias to another variable. Much like a pointer, a reference type stores the address of the thing it "points to". With respect to pointers, the key differences with reference types are:

• Reference types themsleves can not be "rebound", as in whatever they reference is bound for the lifetime of the program.
• Reference types do not need to be explicitly dereferenced (i.e. * or -> do not apply).

Once a reference declaration "binds" itself to something, it acts and operates just like the very thing it is bound to (hence alias). In my example, you would use k just like you would i, with no strings attached. The dereferencing happens all behind the scenes. The nice thing about references if that they abstract the "this points to" away from the programmer, which often leads to less bugs.

At first glance, reference types don't seem too useful since you can do so much more with pointers. However, when dealing with safety of function arguments reference types are extremely useful. When you start caring about the const'ness of your function arguments (i.e. don't modify this argument), you'll be dealing with references a lot more. Using references (where appropriate) also makes code easier to read.

Again, don't worry about reference types if you're using pure C. You can simulate everything they do with pointers. I only mention them here because most people learning C eventually bleed into learning C++, where they do matter.

 

[ChristianVirtual]

struct nodeName *DeleteHead(Struct node *head) {
struct nodeName *deleteHead = malloc(sizeof(nodeName));
//placing head in deleted head address
*deleteHead = *head;

//used to move head to head->next
struct nodeName *temp = head->next;
head->data = temp->data;
head->next = temp->next;
free(temp);

return deleteHead;
}//end of function DeleteHead

With this one you call for trouble ! And a kind of trouble hard to debug as it even might work as intended. Really depends on the conditions at runtime.

1) your returned node is actually not the head; it's a new created clone at a new memory position. Also calls for memory leak as you would need to free it somewhere else.
2) what happen if you have only one element in the list ? The temp=head->next alone seems risk (but maybe because of the cut-down version of the code)
3) what happen if you have elsewhere references stored for be second item in the list you just free(temp) . You might find your ghost object there or something else. You prepare yourself here for nice memory corruptions (overwriting memory with unwanted content)

The answer from rsquared is a good one ...

 

[serious]

First, most programming languages have something called primitive types, and all variables are declared by a type (by it can be implicitly declared). The word "pointer", "reference" and "address" all meant the same thing, which is a primitive type that is used to store an address of the memory table space. I'll simply use the term "address" to refer to this primitive type to make things simpler to understand. Other than primitive types, you can define your own type using typedef.

In C, there are 3 concept that you need to understand:
First, * (aka "value of") a variable. If the variable, say `a` stores an address, then `*a` returns the value stored on that address.
Second, & (aka "address of") a variable. `&a` returns the address of the stored value.
Third, function parameters are copies of the caller's parameters, aka "pass by value".

Suppose `node` is your custom type for your object (linked list token), then you should stick with this type only and not create new types.

Suppose in your main you have

node* list = malloc(sizeof(node));​

`list` itself is an address and you want to create a function named "DeleteHead" that pops the first element out. You will want to pass the address of `list` and not `list` itself because you want to update `list`. That is after the function call the value stored in list changes from pointing to the first element to the second element.

node* deletedNode = DeleteHead(&list);​

In the function, you want to receive the parameter as `node**`, since list is `node*` and you are passing in the address of it. Note that you don't want to update oList directly as oList will be discarded. You instead want to update *oList as you want to update lList.

Consider the following example:

#include <stdio.h>
#include <stdlib.h>

typedef struct node {

int value;
struct node* next;​

} node;

// node* *oList is the same thing as node** oList, which is the same thing as node **oList.
// In fact, spaces are ignored when there is a *.

void AddElement(node* *oList, int n) {

node* newEle = malloc(sizeof(node));
newEle->value = n;
newEle->next = NULL;

if (*oList == NULL)

*oList = newEle;​

else {

node* lastEle = *oList;
while (lastEle->next != NULL)

lastEle = lastEle->next;​

lastEle->next = newEle;​

}​

}

node* DeleteHead(node* *oList) {

node* token = *oList; //token is an address which points to where list points to.
if (*oList != NULL) {

*oList = (*oList)->next; // *oList (which is list) now points to the second element of the list.
token->next = NULL;​

}
//At this point you have 2 distinct node, token and *oList, where token contains 1 element,
//which was the first element of list, and *oList(which is list), which stores the second
//element of list. If list only has 1 element, then the resulting list will be NULL. If list is
//NULL, then token = NULL too.
return token;​

}

// since I'm not trying to change oList, i don't need a *.
void printList (node* oList) {

printf("list: ");
while (oList != NULL) {

printf("%d ", oList->value);
oList = oList->next;​

}
printf("\n");​

}

char* toString(node* element) {

char* str;
if (element != NULL)

asprintf(&str,"%d", element->value);​

else

str="undefined";​

return str;​

}

int main() {

node* list = NULL;
node* deleted = NULL;

//AddElement requires node**, I need to put & before list.
AddElement(&list, 3);
AddElement(&list, 4);
AddElement(&list, 5);

//printList requires node*, I can simply pass in list.
printList(list);
//DeleteHead requires node** again ...
deleted = DeleteHead(&list);

//toString requires node*
printf("deleted: %s\n", toString(deleted));
free (deleted);

//printList requires node*
printList(list);

//DeleteHead requires node**
deleted = DeleteHead(&list);

//you should get the idea by now.
printf("deleted: %s\n", toString(deleted));
free (deleted);

//Deleting the last element.
deleted = DeleteHead(&list);
printf("deleted: %s\n", toString(deleted));
free (deleted);

//list is now NULL.
deleted = DeleteHead(&list);
printf("deleted: %s\n", toString(deleted));

//Freeing a variable that points to NULL is okay.
//Freeing a variable that had been freed is not okay.
free (deleted);
printList(list);
return 0;​

}​

 

[JC724]

First, most programming languages have something called primitive types, and all variables are declared by a type (by it can be implicitly declared). The word "pointer", "reference" and "address" all meant the same thing, which is a primitive type that is used to store an address of the memory table space. I'll simply use the term "address" to refer to this primitive type to make things simpler to understand. Other than primitive types, you can define your own type using typedef.

In C, there are 3 concept that you need to understand:
First, * (aka "value of") a variable. If the variable, say `a` stores an address, then `*a` returns the value stored on that address.
Second, & (aka "address of") a variable. `&a` returns the address of the stored value.
Third, function parameters are copies of the caller's parameters, aka "pass by value".

Suppose `node` is your custom type for your object (linked list token), then you should stick with this type only and not create new types.

Suppose in your main you have

node* list = malloc(sizeof(node));​

`list` itself is an address and you want to create a function named "DeleteHead" that pops the first element out. You will want to pass the address of `list` and not `list` itself because you want to update `list`. That is after the function call the value stored in list changes from pointing to the first element to the second element.

node* deletedNode = DeleteHead(&list);​

In the function, you want to receive the parameter as `node**`, since list is `node*` and you are passing in the address of it. Note that you don't want to update oList directly as oList will be discarded. You instead want to update *oList as you want to update lList.

Consider the following example:

#include <stdio.h>
#include <stdlib.h>

typedef struct node {

int value;
struct node* next;​

} node;

// node* *oList is the same thing as node** oList, which is the same thing as node **oList.
// In fact, spaces are ignored when there is a *.

void AddElement(node* *oList, int n) {

node* newEle = malloc(sizeof(node));
newEle->value = n;
newEle->next = NULL;

if (*oList == NULL)

*oList = newEle;​

else {

node* lastEle = *oList;
while (lastEle->next != NULL)

lastEle = lastEle->next;​

lastEle->next = newEle;​

}​

}

node* DeleteHead(node* *oList) {

node* token = *oList; //token is an address which points to where list points to.
if (*oList != NULL) {

*oList = (*oList)->next; // *oList (which is list) now points to the second element of the list.
token->next = NULL;​

}
//At this point you have 2 distinct node, token and *oList, where token contains 1 element,
//which was the first element of list, and *oList(which is list), which stores the second
//element of list. If list only has 1 element, then the resulting list will be NULL. If list is
//NULL, then token = NULL too.
return token;​

}

// since I'm not trying to change oList, i don't need a *.
void printList (node* oList) {

printf("list: ");
while (oList != NULL) {

printf("%d ", oList->value);
oList = oList->next;​

}
printf("\n");​

}

char* toString(node* element) {

char* str;
if (element != NULL)

asprintf(&str,"%d", element->value);​

else

str="undefined";​

return str;​

}

int main() {

node* list = NULL;
node* deleted = NULL;

//AddElement requires node**, I need to put & before list.
AddElement(&list, 3);
AddElement(&list, 4);
AddElement(&list, 5);

//printList requires node*, I can simply pass in list.
printList(list);
//DeleteHead requires node** again ...
deleted = DeleteHead(&list);

//toString requires node*
printf("deleted: %s\n", toString(deleted));
free (deleted);

//printList requires node*
printList(list);

//DeleteHead requires node**
deleted = DeleteHead(&list);

//you should get the idea by now.
printf("deleted: %s\n", toString(deleted));
free (deleted);

//Deleting the last element.
deleted = DeleteHead(&list);
printf("deleted: %s\n", toString(deleted));
free (deleted);

//list is now NULL.
deleted = DeleteHead(&list);
printf("deleted: %s\n", toString(deleted));

//Freeing a variable that points to NULL is okay.
//Freeing a variable that had been freed is not okay.
free (deleted);
printList(list);
return 0;​

}​

Thanks you this was helpful

 

[JC724]

I appreciate everyones help

 

[Writer]

If you want to really get a solid of grasp of pointers, I highly recommend learning some basic assembler. Even a little bit of assembler experience will give you a much deeper understanding of what's going on under the hood. It will benefit you in all future languages you choose to learn, and make concepts like pointers, pointers-to-pointers, pass by reference, etc. fundamentally understandood.

Warning: if you follow this advice there is a very high likelihood you will find yourself confounded by the utter confusion of other programmers over what will, to you, seem like straightforward and simple things.

 

[cyclone3d]

If you want to really get a solid of grasp of pointers, I highly recommend learning some basic assembler. Even a little bit of assembler experience will give you a much deeper understanding of what's going on under the hood. It will benefit you in all future languages you choose to learn, and make concepts like pointers, pointers-to-pointers, pass by reference, etc. fundamentally understandood.

Warning: if you follow this advice there is a very high likelihood you will find yourself confounded by the utter confusion of other programmers over what will, to you, seem like straightforward and simple things.

I second this.

And even now I sometimes get how pointers work mixed up and have to go back and refresh myself with the concepts when I end up using them.

 

[Writer]

I was lucky enough to land an asm programming job early in my career in the 90's -- which was a pretty rare thing even then! -- but to this day it continues to pay dividends.

The enormity of this advantage began to reveal itself two years later on a big C and C++ project, while listening to a group of senior programmers argue over the use of pointers-to-pointers in a method call. It was pretty obvious they didn't really "get" what pointers were at all. It sounded like it was all crazy voodoo to them. I couldn't believe it when I heard the most experienced programmer in the group admit that pointer arithmetic made him nervous because it was so "unpredictable" and "difficult to understand."

I couldn't help thinking, you turkeys are supposed to be better at this?

 

[cyclone3d]

I was lucky enough to land an asm programming job early in my career in the 90's -- which was a pretty rare thing even then! -- but to this day it continues to pay dividends.

The enormity of this advantage began to reveal itself two years later on a big C and C++ project, while listening to a group of senior programmers argue over the use of pointers-to-pointers in a method call. It was pretty obvious they didn't really "get" what pointers were at all. It sounded like it was all crazy voodoo to them. I couldn't believe it when I heard the most experienced programmer in the group admit that pointer arithmetic made him nervous because it was so "unpredictable" and "difficult to understand."

I couldn't help thinking, you turkeys are supposed to be better at this?

HAHAHA, nice.

Pointer arithmetic made him nervous because it was so "unpredictable" and "difficult to understand." ????

Somebody should have not had the position they had.

 

[Armenius]

If you want to really get a solid of grasp of pointers, I highly recommend learning some basic assembler. Even a little bit of assembler experience will give you a much deeper understanding of what's going on under the hood. It will benefit you in all future languages you choose to learn, and make concepts like pointers, pointers-to-pointers, pass by reference, etc. fundamentally understandood.

Warning: if you follow this advice there is a very high likelihood you will find yourself confounded by the utter confusion of other programmers over what will, to you, seem like straightforward and simple things.

Second this. I had a hard time grasping the subject of pointers when I first started learning C, as well, and when I revisited the subject after taking a class on asm it suddenly clicked for me.

 

[StoleMyOwnCar]

If you want to really get a solid of grasp of pointers, I highly recommend learning some basic assembler. Even a little bit of assembler experience will give you a much deeper understanding of what's going on under the hood. It will benefit you in all future languages you choose to learn, and make concepts like pointers, pointers-to-pointers, pass by reference, etc. fundamentally understandood.

Warning: if you follow this advice there is a very high likelihood you will find yourself confounded by the utter confusion of other programmers over what will, to you, seem like straightforward and simple things.

I have to kind of disagree with learning assembly as a step in understanding any language. For me it was an entirely different animal, and frankly the way each language gets translated to it seems to be different. Occasionally I just slack around and browse Stackoverflow at work and there are all kinds of posts that are confused about how Java or some such gets translated to machine code.

I had a class a while back where first we would write code in C that would do some conceptual problem. Usually it was contrived, with no real world analogue, but still somewhat complicated anyway. Anyhow, then we had to take what we did in C and basically translate (rewrite) it to assembly. Maybe it's just me, but what I ended up doing was simply treating assembly as a different animal that plays by a different set of rules entirely. Or rather, so low level that you could essentially get away with any optimizations you fancied to make. To me C/C++ was such a high level language by comparison that I didn't even try to translate every piece to assembly systematically. Instead what I did was look at what I did in C and figure out what would be the best way to do something similar to it in assembly. On one program, my translation ended up becoming almost entirely different. It wasn't really a translation but more of a re-imagining. For instance, I didn't treat my recursion generically and do the traditional way of "calling functions" in assembly, but simply treated the problem as "I need 5 frames, and I don't necessarily care how one would translate these to assembly generically". What ended up coming out was an extremely well optimized script that cut out many little excesses of dynamic code length that I simply couldn't do (or maybe didn't know how to) in C. It didn't really play by the rules, but as a result was much (much) more efficient than the professors' baseline. There were a lot of "yeah, this is how I would do it usually, but if I just employ this little trick here..." type of moments. >_>


Every language has its own weird little quirks. Are the variables passed by value or reference? Can you even pass references around? What's the namespace of this? How does the garbage collector behave? Will the optimizer screw up volatile variables if I don't declare them volatile for this embedded system?

If you sit there and try to boil it down to how you think something gets translated into lower level languages, you'll probably learn way more than you ever really wanted or needed, and have wasted a lot of time. There's a time and place for everything, and it really depends on what you want to do. Expertise is both overrated and underrated. I can tell you right now that with my current job of doing perl/web design/database work no one really gives a crap about how it translates to C and I sure as hell have never had to wonder. I just learned about the little quirks and that's more than plenty to do some clever things.

 

[Writer]

To be clear, I wasn't referring to translating from some other language to assembler...I was referring specifically to learning how to program in assembler, which gives you a fundamental understanding of what is going on at a low level. It's this low-level understanding that I've found makes some trickier concepts in high level languages much easier to grasp and (more importantly) to deeply comprehend.

> If you sit there and try to boil it down to how you think something gets translated into lower level languages

Knowing how things work at a fundamental level might not help you remember whether a particular language passes parameters by reference or by value...but it will help you more fully understand what those concepts mean. For example, a background in assembler would make the fact that Java passes all parameters by value intrinsically make sense. You aren't limited to understanding how things work just by how they appear to behave.

 

[Doward]

Gonna third (actually fourth, I think) the thought of doing some assembler. I started my development with Atari Basic, and quickly moved into 6502c assembly. To this day, computers still work based on On and Off, so the knowledge I gained from there is still useful today.

You will understand what's going on with your code at such a fundamental level, you'll be able to much more intuitively understand any edge cases that pop out.