Creating a singly-linked list

Question

I have a function to join two structs to create a linked list.

Here, is the code:

struct point{
    int x;
    int y;
    struct point *next;
};
void printPoints(struct point *);
void printPoint(struct point *);
struct point * append(struct point *, struct point *);
void main(){
    struct point pt1={1,-1,NULL};
    struct point pt2={2,-2,NULL};
    struct point pt3={3,-3,NULL};
    struct point *start, *end;
    start=end=&pt1;
    end=append(end,&pt2);
    end=append(end,&pt3);
    printPoints(start);
}
void printPoint(struct point *ptr){
    printf("(%d, %d)\n", ptr->x, ptr->y);
}
struct point * append(struct point *end, struct point *newpt){
    end->next=newpt;
    return newpt;
}
void printPoints(struct point *start){
    while(start!=NULL){
        printPoint(start);
        start=start->next;
    }
}

Here, the append function's task involves changing the end pointer.

Both the arguments of append function are pointers; in 1st case, 1st argument is &pt1 and 2nd argument is &pt2.

The function makes a copy of the end pointer which has the type struct point. Since &pt1 is passed then this duplicate end pointer has x component as 1 and y component as -1 and next component as NULL. Now we change this copy's next component to newpt pointer and return the newpt pointer.

Back to the main function, the original end pointer now has the value of &pt2.

end->next = newpt; shouldn't produce any change in the original end pointer in main because only the local pointer was changed.

So then why do I get a linked list.

What I get:

(1, -1)
(2, -2)
(3, -3)

What I think I should get:

(1, -1)

Answer 1

end->next = newpt; shouldn't produce any change in the original end pointer in main. Because, only the local pointer was changed

Not quite correct. It is true that when you call append, a copy of end is made. However, the -> operator dereferences what that pointer points to. You would get the same behavior with (*end).. Since the end in main is the same as the end in append, they both point to the same thing. You could have 100 copies of a pointer, all pointing to the same thing. If you choose one, follow what it points to and change that, then you've changed the same thing that all other 99 pointers point to. Furthermore, you reassign end in main by returning newpt, so each call to append results in an updated end. The output you observe is correct. Consider the condensed stack frames:

In main, at first call to append:

____main____
|___pt1____| <----+  <-+
|x=1 y=-1  |      |    |
|_next=NULL|      |    |
|___pt2____|      |    |
|___pt3____|      |    |
|__start___|------+    |
|___end____|-----------+      // cell sizes NOT drawn to scale
// start and end both point to pt1

Now, on the first call to append, the main stack frame stays the same, and a new one is created for append, where end and the address to pt2 are passed in.

|___main____
|___pt1____| <----+  <-+
|_next=NULL|      |    |   // x and y omitted for brevity
|___pt2____|      |    |
|___pt3____|      |    |
|___end____|------+    |
                       |
___append__            |
|___&pt2___|           |
|___end____|-----------+  // also points to pt1 back in main

When you use the -> operator, you dereference what that pointer points to. In this case, pt1, so both end in main and end in append point to pt1. In append, you do

end->next = newpt;

which is the address of pt2. So now your stack frames look like this:

|___main____
|___pt1____| <-----------+  <-+
|_next=&pt2|------+      |    |  // x and y omitted for brevity
|          |      |      |    |  // (made pt1 cell bigger just to make the picture clearer, no other reason)
|__________|      |      |    |   
|___pt2____| <----+      |    |
|___pt3____|             |    |
|___end____|-------------+    |
                              |
___append__                   |
|___&pt2___|                  |
|___end____|------------------+  // also points to pt1 back in main

Finally, when you return from append, you return the address of pt2 and assign it to end, so your stack in main looks like this before the 2nd call to append (again, some cells made larger for picture clarity, this does not suggest anything grew in size):

____main____
|___pt1____| <-----------+
|_next=&pt2|---+         |
|          |   |         |
|__________|   |         |
|___pt2____| <-+ <-+     |
|___pt3____|       |     |
|___end____|-------+     |
|___start__|-------------+  // flipped start and end position to make diagram cleaner, they don't really change positions on the stack

And you do it all again with your next call to append, passing in end (now points to pt2) and the address of pt3. After all the calls to append, start points to pt1, pt1->next points to pt2, and pt2->next points to pt3, just as you see in the output.

One final note, you have an incorrect function signature for main

Answer 2

As in the illustration start still points to p1 and end points to pt3.

void main(){
    struct point pt1={1,-1,NULL};
    struct point pt2={2,-2,NULL};
    struct point pt3={3,-3,NULL};
    struct point *start, *end;
    start=end=&pt1;
    end=append(end,&pt2);
    end=append(end,&pt3);
    printPoints(start);
}

As in the main function, you make start and end to point at pt1. That's why any changes made to end is also seen from start.

struct point * append(struct point *end, struct point *newpt){
    end->next=newpt;
    return newpt;
}

In the append function, end->next=newpt which sets the next of end to newpt. In the first case, when end points pt1, the next is set to point at pt2. This change in the list is also seen from start.

Hence, the output you are getting is correct.

---

Changing Pointers

When you pass a pointer to a function, the value of the pointer (that is, the address) is copied into the function not the value it is pointing at.

So, when you dereference the pointer and change it, the change is also seen from any pointer which contain the same address. Remember that p->next is the same as (*p).next.

void change_the_pointer_reference(int* ip)
{
    int i = 1;
    *ip = i;
    printf("%d\n", *ip); // outputs 1
}

int main()
{
    int i = 0;
    change_the_pointer_reference(&i);
    printf("%d\n", i); // outputs 1
}

But as the value of the pointer is copied, if you assign to the pointer, this change is only seen locally.

void change_the_pointer(int* ip)
{
    int i = 1;
    ip = &i;
    printf("%d\n", *ip); // outputs 1
}

int main()
{
    int i = 0;
    change_the_pointer(&i);
    printf("%d\n", i); // outputs 0
}

Last final note, you have an incorrect signature of main