Like Tree1Likes
  • 1 Post By claudiu

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 am working on an assignment, and need to write a function to add a new node to the tail ...

  1. #1
    Registered User
    Join Date
    Feb 2012
    Posts
    32

    Linked List - Add to Tail

    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.

    Code:
    #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.
    Last edited by Brandon Smith; 04-03-2012 at 01:23 PM.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,854
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Feb 2012
    Posts
    32
    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?
    Last edited by Brandon Smith; 04-03-2012 at 01:26 PM.

  4. #4
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,058
    Do you specifically need to add to the tail or can you add new nodes to the head, simplifying the task greatly.

  5. #5
    Registered User
    Join Date
    Feb 2012
    Posts
    32
    Quote Originally Posted by itCbitC View Post
    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.

  6. #6
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,058
    Quote Originally Posted by Brandon Smith View Post
    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.

  7. #7
    Registered User
    Join Date
    Feb 2012
    Posts
    32
    Quote Originally Posted by itCbitC View Post
    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.

  8. #8
    Registered User
    Join Date
    Feb 2012
    Posts
    32
    This is my updated Add_to_Tail function, getting closer, but still not sure where to go from here.
    Code:
    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;
        }
    }

  9. #9
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,854
    > 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
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  10. #10
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    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?
    iMalc likes this.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  11. #11
    Registered User
    Join Date
    Feb 2012
    Posts
    32
    Quote Originally Posted by claudiu View Post
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked list tail
    By cable in forum C Programming
    Replies: 3
    Last Post: 10-08-2011, 01:48 PM
  2. Linked List - Add to Tail
    By beatbox32 in forum C Programming
    Replies: 9
    Last Post: 08-08-2011, 04:43 PM
  3. doubly linked list tail pointer in struct
    By bazzano in forum C Programming
    Replies: 15
    Last Post: 06-11-2007, 01:31 PM
  4. loosing tail in doubly linked list
    By bazzano in forum C Programming
    Replies: 5
    Last Post: 05-07-2007, 12:46 AM
  5. tail pointer - linked list
    By Space_Cowboy in forum C++ Programming
    Replies: 1
    Last Post: 12-02-2002, 03:05 AM

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