Understanding the logic behind building linked list using local reference

Question

Below is the code for creation of linked list using local reference logic. Not able to understand the code inside the for loop especially the 2nd line. (see // HERE)

Can somebody please elaborate how this logic is working.

void push(struct Node** head_ref, int new_data)
{
  struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
  newNode->data = new_data;

  newNode->next = *head_ref;
  *head_ref = newNode;

  return;
}


struct Node* buildWithLocalRef()
{
  int i=0;
  struct Node *head = NULL;
  struct Node **lastptrRef = &head;

  for(i=1;i<6;i++)
  {
    push(lastptrRef,i);
    lastptrRef = &((*lastptrRef)->next); // HERE
  }

  return head;
}

int main()
{
  struct Node* head;

  head = buildWithLocalRef();
  printList(head);
  return 0;
}

To point to next node, since lastptrRef is double pointer you need &. — kiran Biradar, Aug 12 '18 at 19:02
There are questions on SO about the 'pointer to pointer' technique for list traversal, including [What is the double pointer technique for simplifying the traversal of linked lists?](https://stackoverflow.com/questions/3182733/) and [A interesting C linked list idiom](https://stackoverflow.com/questions/332441/). These may help you. — Jonathan Leffler, Aug 12 '18 at 19:05

WhozCraig · Answer 1 · 2018-08-12T19:59:07.873

The technique you're seeing is building a linked list by forward-chaining. It is the most direct, and sensible way to build an ordered list from beginning to end, where the list does not have a tail pointer (and yours does not).

There are no "references" here. This isn't C++. This is using a pointer to pointer. The variable name is dreadfully named, btw. How it works is this:

Initially the list is empty, head is NULL
A pointer to pointer, lastptrRef will always hold the address of (not the address in; there is a difference) the next pointer to populate with a new dynamic node allocation. Initially that pointer-to-pointer holds the address of the head pointer, which is initially NULL (makes sense, that is where you would want the first node hung).
As you iterate the loop a new node is allocated in push . That node's next pointer is set to whatever value is in the pointer pointed to by lastptrRef (passed as head_ref in the function), then the pointer pointed to by lastptrRef is updated to the new node value.
Finally, lastptrRef is given the address of the next member in the node just added, and the process repeats.

In each case, lastptrRef hold the address of a pointer containing NULL on entry into push. This push function makes this harder to understand. (more on that later). Forward chaining is much easier to understand when done directly, and in this case, it would make it much, much easier to understand

struct Node* buildWithLocalRef()
{
    struct Node *head = NULL;
    struct Node **pp = &head;

    for (int i = 1; i < 6; i++)
    {
        *pp = malloc(sizeof **pp);
        (*pp)->data = i;
        pp = &(*pp)->next;
    }
    *pp = NULL;

    return head;
}

Here, pp always holds the address of the next pointer we'll populate with a new node allocation. Initially, it holds the address of head. As each node is inserted pp is set to the address of the next pointer within the latest node inserted, thereby giving you the ability to continue the chain on the next iteration. When the loop is done, pp holds the address of the next pointer in the last node in the list (or the address of head of nothing was inserted; consider what happens if we just pull the loop out entirely). We want that to be NULL to terminate the list, so the final *pp = NULL; is performed.

The code you posted does the same thing, but in a more convoluted manner because push was designed to push items into the front of a list (apparently). The function always sets the pointer pointed to by head_ref to the new node added, and the node's next is always set to the old value in *head_ref first. Therefor, one can build a stack by doing this:

struct Node* buildStack()
{
    struct Node *head = NULL;

    for (int i = 1; i < 6; i++)
        push(&head, i);

    return head;
}

Now if you print the resulting linked list, the number will be in reverse order of input. Indeed, push lives up to its name here. Dual-purposing it to build a forward-chained list is creative, I'll grant that, but in the end it makes it somewhat confusing.

@Deduplicator It's reflex. I *always* initialize declared pointers to determinate values. — WhozCraig, Aug 12 '18 at 19:39
I'm thinking that one line of code could be `*pp = malloc(sizeof(struct Node));` for readability, although it will work as is. — rcgldr, Aug 12 '18 at 19:50
@rcgldr it's correct either way (as I wrote it, or as you did). There is no actual rune-time dereference done. If you didn't know that, [read about the `sizeof` operator **here**](https://en.cppreference.com/w/c/language/sizeof), and more information [**here**](https://stackoverflow.com/questions/13574421/why-doesnt-my-program-seg-fault-when-i-dereference-a-null-pointer-inside-of-mal). I specifically use that method because changing the type of `pp` (imagine a function hundreds of lines long with a dozen pointers like this), doesn't require I change the allocation lines as well. — WhozCraig, Aug 12 '18 at 19:54
@WhozCraig - we may have cross posted, I updated my comment, noting it was a change for readability, not to correct the code. I'll delete this comment later. — rcgldr, Aug 12 '18 at 19:56

Understanding the logic behind building linked list using local reference

1 Answers1