Linked List - Add to Tail

This is a discussion on Linked List - Add to Tail within the C Programming forums, part of the General Programming Boards category; I've spent the past couple of days trying to understand how this algorithm works, even attempting memory drawings, but I'm ...

  1. #1
    Registered User
    Join Date
    Jul 2011
    Location
    Irvine, CA
    Posts
    13

    Linked List - Add to Tail

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

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    "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.)

  3. #3
    Registered User
    Join Date
    Jul 2011
    Location
    Irvine, CA
    Posts
    13
    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?

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by beatbox32 View Post
    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.)

  5. #5
    Registered User
    Join Date
    Jul 2011
    Location
    Irvine, CA
    Posts
    13
    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.

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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".

  7. #7
    Registered User
    Join Date
    Jul 2011
    Location
    Irvine, CA
    Posts
    13
    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?

  8. #8
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by beatbox32 View Post
    So how long does it take for this stuff to become second nature?
    60, maybe 70 years...

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,310
    Quote Originally Posted by beatbox32
    So how long does it take for this stuff to become second nature?
    The time needed to become a born-again programmer
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Registered User
    Join Date
    Jul 2011
    Location
    Irvine, CA
    Posts
    13
    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.

    Quote Originally Posted by tabstop View Post
    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".

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. doubly linked list tail pointer in struct
    By bazzano in forum C Programming
    Replies: 15
    Last Post: 06-11-2007, 12:31 PM
  2. loosing tail in doubly linked list
    By bazzano in forum C Programming
    Replies: 5
    Last Post: 05-06-2007, 11:46 PM
  3. Another List Q - Seg fault on head-tail list
    By JimpsEd in forum C Programming
    Replies: 11
    Last Post: 05-10-2006, 12:53 AM
  4. Replies: 6
    Last Post: 03-02-2005, 01:45 AM
  5. tail pointer - linked list
    By Space_Cowboy in forum C++ Programming
    Replies: 1
    Last Post: 12-02-2002, 02:05 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21