Linked List - Add to Tail

[Brandon Smith]

I am working on an assignment, and need to write a function to add a new node to the tail of a linked list. My code so far is as follows.

#include <stdio.h>
#include <stdlib.h>

typedef struct IntNode 
{
    int data;
    struct IntNode *next;
} IntNode;


typedef struct List
{
    IntNode *head;
} List;

void Add_to_Tail(List *list, List *newnode);
IntNode *New_Node(int n);

int main()
{
int i=0;
List myList = {NULL};

for(i=1; i<=10; i++) {
    IntNode* n=New_Node(i*2);
    Add_to_Tail(&myList, n);
}
Print_List(&myList); 
Free_List(&myList);
return 0;
}

IntNode *New_Node(int n){
    IntNode *temp;
    temp = malloc(sizeof(IntNode));
    temp->data = n;
}

void Add_to_Tail(List *list, List *newnode){
}

As you can see, it is supposed to basically create a linked list of even numbers from 2 to 20, and created a linked list by adding the nodes onto the end of the list. I know how to do this, I just don't know how to put it into code.

I know that my Add_to_Tail needs to do the following:

1. Detect if node = 1st node, i.e. if the list is empty
2. If not first node, use next ptr to find the end of the list
3. Update the old next ptr to point to the new node
4. ???

Any help converting this to code is greatly appreciated as always. Thanks.

[Salem]

Well given the head, you need to walk down the links until you get to the tail.

Having head and tail pointers makes this a snap.

[Brandon Smith]

Unfortunately, I can only use a head pointer. Which I guess means I would have to iterate through every time I "Add_to_Tail" until it comes back NULL, i.e the end?

[itCbitC]

Do you specifically need to add to the tail or can you add new nodes to the head, simplifying the task greatly.

[Brandon Smith]

Do you specifically need to add to the tail or can you add new nodes to the head, simplifying the task greatly.

I have to add to tail. Adding to the head is very simple, and I've got the function for that! Just having trouble figuring out the tail.

[itCbitC]

I have to add to tail. Adding to the head is very simple, and I've got the function for that! Just having trouble figuring out the tail.

Then you don't have any choice but to do exactly what Salem has suggested viz., traverse the list of linked nodes until you reach the end.

[Brandon Smith]

Then you don't have any choice but to do exactly what Salem has suggested viz., traverse the list of linked nodes until you reach the end.

I know I need to do this, but I have no idea how to, hence this post.

[Brandon Smith]

This is my updated Add_to_Tail function, getting closer, but still not sure where to go from here.

void Add_to_Tail(List *list, List *newnode)
{
    if(!list->head)
    {
     list->head = newnode;   
    }
    else
    {
    IntNode *hd;
    hd = list->head;  
    while(hd != NULL)
    {
        hd = hd->next;   
    }
    hd->next = newnode;
    }
}

[Salem]

> while(hd != NULL)
Try stopping on the tail node, not falling off the end.

while(hd->next != NULL)

And make sure your newnode->next is NULL

[claudiu]

Adding nodes to the tail of a single linked list is massively inefficient unless you also store a pointer to the tail which you update with every add. What are they teaching kids nowadays?

Now obviously you are probably just storing some small primitive types in the list, but what if you had to store large structures?

[Brandon Smith]

Adding nodes to the tail of a single linked list is massively inefficient unless you also store a pointer to the tail which you update with every add. What are they teaching kids nowadays?

Now obviously you are probably just storing some small primitive types in the list, but what if you had to store large structures?

I couldn't agree more, just teach us right the first time. The next assignment was doubly linked list, in a circular fashion. I guess it's just a good learning experience to figure it out the long way first. Thanks for your help everyone.