Linked List - Add to Tail

[beatbox32]

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.

#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);
}

[tabstop]

"node 1"->next = "address of node 1"

I don't think that's true, is it? ->next gets changed before headRef does, so it gets headRef's original value, which should be NULL.

(EDIT: And by the same token, node2->next points to node1, not node2.)

[beatbox32]

Ah, good catch, thanks tabstop. But this still confuses me. If node2->next points to node1, wouldn't this place node2 in front of node1, therefore really inserting the node at the beginning of the list?

[tabstop]

Ah, good catch, thanks tabstop. But this still confuses me. If node2->next points to node1, wouldn't this place node2 in front of node1, therefore really inserting the node at the beginning of the list?

That's what "push" means, to put at the front of the list. (That's why headRef is changing, as opposed to tailRef.)

[beatbox32]

I see what you're saying. The Push() function was originally built for adding a node at the beginning of the list. It does that for the first node as a special case. But if it's always pushing to the front of the list, how is it that the output from the program is "1 2 3 4 5" and not "5 4 3 2 1" (assuming user inputs '5')?

After the first node (with data = 1), Push() takes the value of tail->next for the rest of the nodes (2 to user-inputted max). With your original reply in mind, here's what I'm seeing for node 2:

"node 2"->data = 2
"node 2"->next = tail->next (which is currently "address of node 1")
tail = "address of node 1"
head = "address of node 1"

Maybe I'm just using a tutorial for linked lists that doesn't work for me.. Any suggestions?

Thanks again for all of your help.

[tabstop]

If you pass tail->next as headRef, then you are telling the push function that the list begins at tail->next, so that's where things get added. (Since push changes headRef in the calling function, that is what hooks node2 to the end of node1, the line *headRef = newNode.)

Also notice that tail->next is extremely different from "address of node 1", and is in fact "NULL".

[beatbox32]

Okay, I think I'm getting it now. I wrote this little step-by-step text to work through the first 3 nodes:

set head to point to NULL

Create Node1:
=============
Push(&head,1)
create Node1 0x0001 // Creates Node1 in memory
set Node1->data = 1
set Node1->next to point to NULL (value of head) // Node1 has nothing following it
set head to point to 0x0001 (where Node1 lives) // Node1 is beginning of list

set tail to point to 0x0001 (where Node1 lives) // Node1 is shown as end of list
this in turn makes tail->next point to NULL

Create Node2:
=============
Push(&(tail->next), i)
create Node2 @ 0x0002 // Creates Node2 in memory
set Node2->data = 2
set Node2->next to point to NULL (value of tail->next) // Node2 now points to null, nothing following it
set tail->next (which is currently NULL) to point to Node2 address // Node2 is shown as end of the list

set tail to point to the value of tail->next which is Node2 address
Node2->next points to NULL, so therefore tail->next points to NULL

Create Node3:
=============
Push(&(tail->next), i)
create Node3 @ 0x0003 // Creates Node3 in memory
set Node3->data = 3
set Node3->next to point to NULL (value of tail->next) // Node3 now points to null, nothing following it
set tail->next (which is currently NULL) to point to Node3 address // Node3 is shown as the end of the list

set tail to point to the value of tail->next which is Node3 address
Node3->next points to NULL, so therefore tail->next points to NULL

So how long does it take for this stuff to become second nature?

[CommonTater]

So how long does it take for this stuff to become second nature?

60, maybe 70 years...

[laserlight]

So how long does it take for this stuff to become second nature?

The time needed to become a born-again programmer

[beatbox32]

Well, I thought I was getting it.. but after further examination, I realized I wasn't. After another day of wrestling with the problem, the light bulb went off. This little exercise has really sharpened my understanding of pointers and how making changes to the value of a dereferenced pointer variable also affects the dereferenced value of any other pointer variable pointing to the same memory segment.

Thanks for all of the assistance. It has been a real effort to understand this, but I guess the most interesting things never comes easy.

If you pass tail->next as headRef, then you are telling the push function that the list begins at tail->next, so that's where things get added. (Since push changes headRef in the calling function, that is what hooks node2 to the end of node1, the line *headRef = newNode.)

Also notice that tail->next is extremely different from "address of node 1", and is in fact "NULL".