I've spent the past couple of days trying to understand how this algorithm works, even attempting memory drawings, but I'm just not grasping it. Below is the code. It builds the first node as a special case and then adds the rest of the nodes to the tail end. It also works as expected, so I'm really just trying to uncover the flaw in my logic and truly understand pointers.
This all comes from the tutorial found here: Linked List Basics
What I don't seem to understand specifically is how a new node is added to the tail end of the list.
After the first node is created, the variables have the following values:
"node 1"->data = 1
"node 1"->next = "address of node 1"
tail = "address of node 1"
head = "address of node 1"
As seen above, after creating the first node, it's next variable points to itself (via assignment from headRef). headRef then is changed from pointing to NULL to pointing to the "address of node 1".
Now comes time to add a new node at the tail. Push(&(tail->next), i) passes the value (by reference) of the tail->next pointer (which is really "node 1"->next since tail currently points to "node 1"). The Push() function creates a newNode ("node 2") and does the following:
"node 2"->data = 2
"node 2"->next = "address of node 2"
tail = "address of node 1"
head = "address of node 1"
To me, that seems to be leaving node 2 unconnected to node 1 and leaving the tail and head variables unchanged. This is obviously not what's happening.
I appreciate all the help to unclutter my thought process.
Code:#include <stdio.h> /* Push a new node onto list */ void Push(struct node** headRef, int data); /* Test the Push function */ void PushTest(int usernum); struct node { int data; /* Data */ struct node* next; /* Pointer to next node */ }; int main(int argc, char* argv[]) { int g; char line[50]; printf("Please enter the desired length of your list: "); fgets(line, sizeof(line), stdin); sscanf(line, "%d", &g); PushTest(g); return 0; } /* Takes a list and a data value. Creates a new link with the given data and pushes it onto the end of the list (except the 1st node exeception). */ void Push(struct node** headRef, int data) { struct node* newNode = malloc(sizeof(struct node)); newNode->data = data; newNode->next = *headRef; *headRef = newNode; } /* Test the Push function */ void PushTest(int usernum) { int len; struct node* head = BuildWithSpecialCase(usernum); len = Length(head); printf("List Length = %d\n", len); PrintLL(head); } /* Print Linked List from beginning */ void PrintLL(struct node* head) { struct node* current; printf("List (from beginning node): "); for(current = head; current != NULL; current = current->next) { printf("%d ", current->data); } } /* Build linked list with special case for first node */ struct node* BuildWithSpecialCase(int g) { struct node* head = NULL; struct node* tail; int i; //Deal with the head node here, and set the tail pointer Push(&head, 1); tail = head; //Do all the other nodes using 'tail' for (i = 2; i <= g ; ++i) { Push(&(tail->next), i); // add node at tail->next tail = tail->next; // advance tail to point to last node } return(head); }