Thread: Linked Lists

I am a little confused about the push() function, which puts an element at the beginning of a linked list.

Code:

void WrongPush(struct node* head, int data) {
   struct node* newNode = malloc(sizeof(struct node));
   newNode->data = data;
   newNode->next = head;
   head = newNode;       // NO this line does not work!
}
void WrongPushTest() {
   List head = BuildTwoThree();
   WrongPush(head, 1);   // try to push a 1 on front -- doesn't work
}

The proposed solution for the above is to have struct node** head instead of struct node* head in the WrongPush parameters.

Now, I am a little confused here, could someone outline a process to help me understand it better? Also, in WrongPushTest(), could i pass WrongPush(&head, 1) instead of WrongPush(head, 1)? Would this allow me to keep the struct node* head in the parameter list? Are (*-**) and (&-*) synonymous?

Thanks

Well the problem is that head nodes outside the push function won't be able to reflect the change if you do it that way. The idea would stay the same, except that from a working implementation, you want the head pointer to point to the new head.

You could return the new head pointer

lst = push( lst, data)

or use a pointer to pointer.

push( &lst, data );

Sorry I didn't know 'List head' meant the same as 'struct node* head'. That clears things up a little. I am still a little confused about passing the & and using the 'struct node ** head' for that. I will read up a bit more and come back if i need further help. Thanks

Originally Posted by Tommo

Sorry I didn't know 'List head' meant the same as 'struct node* head'. That clears things up a little. I am still a little confused about passing the & and using the 'struct node ** head' for that. I will read up a bit more and come back if i need further help. Thanks

You could have the function return a pointer to the new head of the list:

Code:

struct node *push(struct node *head, int data)
{
    struct node *newnode = malloc(sizeof(*newnode));

    newnode->data = data;
    newnode->next = head;
    return newnode;
}

Then, when you use it:

Code:

head = push(head, 12345);

Of course, there is the issue of malloc() returning NULL, which my example doesn't consider.

OK, thanks. Turns out the new code is:

Code:

void Push(struct node** headRef, int data) {
   struct node* newNode = malloc(sizeof(struct node));
   newNode->data = data;
   newNode->next = *headRef;   // The '*' to dereferences back to the real head
   *headRef = newNode;         // ditto
}
void PushTest() {
   struct node* head = BuildTwoThree();// suppose this returns the list {2, 3}
   Push(&head, 1);       // note the &
   Push(&head, 13);
   // head is now the list {13, 1, 2, 3}
}

I think the thing that tripped me up was the **. I guess you need to know that the same rules apply as with the single *. Thanks for the help