Thread: Inserting a node at the tail of singly linked list

  1. #1
    Registered User
    Join Date
    Oct 2019
    Posts
    82

    Inserting a node at the tail of singly linked list

    Hello,

    Below is my half-witted attempt at inserting a node at the tail of a singly linked list. Assumptions are that the list is not sorted. This should probably be simple and easy to do but my lack of seriousness and focus is probably the problem. It probably makes me look a bit silly but you are better of looking silly while being smart than looking smart while being silly.

    Code:
    /*
    
     * list structure
    
     *
     * SinglyLinkedListNode {
     *     int data;
     *     SinglyLinkedListNode* next;
     * };
     *
     */
    
    SinglyLinkedListNode* insertNodeAtTail(SinglyLinkedListNode* head, int data) {
    
        SinglyLinkedListNode *new_node = (SinglyLinkedListNode*)malloc(sizeof(SinglyLinkedListNode));
    
        new_node->data = data;
    
        SinglyLinkedListNode *temp = head->next;
    
        while(temp->next != NULL)
        {
              temp = temp->next;
        }
    
        temp->next = new_node; 
    
       return head;
    }
    
    


    Is this heading in the right direction? Is the algorithm correct? Why is it segmentation faulting?
    This is preparation for some upcoding coding challenge which might lead me to an interview for a permanent or probably semi-permanent job. This particular challenge was picked off on hackerrank.



    Last edited by ghoul; 10-23-2020 at 01:52 AM.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    You need to make sure your new_node->next is NULL.

    > SinglyLinkedListNode *new_node = (SinglyLinkedListNode*)malloc(sizeof(SinglyLinkedL istNode));
    If this really is C++, then you should be using new, not malloc.
    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.

  3. #3
    Registered User
    Join Date
    Oct 2019
    Posts
    82
    Quote Originally Posted by Salem View Post

    You need to make sure your new_node->next is NULL.

    > SinglyLinkedListNode *new_node = (SinglyLinkedListNode*)malloc(sizeof(SinglyLinkedL istNode));
    If this really is C++, then you should be using new, not malloc.
    Thanks. fixed those but there still is the segfault. It looks like my lack of knowledge about the rest of the existing code might be what is getting in my way.

  4. #4
    Registered User
    Join Date
    Feb 2019
    Posts
    1,078
    Quote Originally Posted by ghoul View Post
    Thanks. fixed those but there still is the segfault. It looks like my lack of knowledge about the rest of the existing code might be what is getting in my way.
    Is this right?
    Code:
    SinglyLinkedListNode *temp = head->next;

  5. #5
    Registered User
    Join Date
    Sep 2020
    Posts
    150
    What's the purpose of this - homework?
    C++ comes with std::list and std::forward_list, why not using these?
    Are you aware that lists have a poor performance and should rarely be used?

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > Thanks. fixed those but there still is the segfault.
    At some point, you have to recognise that the current list is empty (head == NULL), and just return the freshly created node as being the sole entry in the list.
    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.

  7. #7
    Registered User
    Join Date
    Oct 2019
    Posts
    82
    Quote Originally Posted by thmm View Post

    What's the purpose of this - homework?
    No, but, yes, it is more or less like homework to prepare for an interview.

    Quote Originally Posted by thmm View Post

    C++ comes with std::list and std::forward_list, why not using these?

    Are you aware that lists have a poor performance and should rarely be used?
    So we have a new std::forward_list on top of the good old std::list. std::list was the best they had during my hey days. And, yes, a lot of research has gone into data structures and algorithms, there is little chance that you will be forced to come up with your own data structures and algorithms while dealing with a mainstream topic like sorting, searching etc

    Quote Originally Posted by flp1969 View Post

    Is this right?
    Code:
    SinglyLinkedListNode *temp = head->next;
    No idea, snuck it out as it was sort of introducing a bug in the algorithm.

    Quote Originally Posted by Salem View Post
    > Thanks. fixed those but there still is the segfault.
    At some point, you have to recognise that the current list is empty (head == NULL), and just return the freshly created node as being the sole entry in the list.
    Final code is below.

    Thanks a lot for the company and help!

    Code:
    SinglyLinkedListNode* insertNodeAtTail(SinglyLinkedListNode* head, int data) {
    
        SinglyLinkedListNode *new_node = new SinglyLinkedListNode(data);
    
        new_node->data = data;
    
    if (head == NULL)
        {
    return new_node;
        }
    
    
        SinglyLinkedListNode *temp = head;
    
    while(temp->next != NULL){
            temp = temp->next;
            }
    
        temp->next = new_node;
    
    return head;
    }
    
    

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 1
    Last Post: 08-02-2016, 06:44 AM
  2. Delettion of node in singly linked list
    By gamer_trex29 in forum C Programming
    Replies: 7
    Last Post: 06-12-2007, 02:00 PM
  3. Problems with deleting a node in a singly linked list
    By omishompi in forum C++ Programming
    Replies: 7
    Last Post: 02-23-2006, 06:27 PM
  4. Deleting node from singly linked list
    By Happy Man in forum C Programming
    Replies: 2
    Last Post: 04-16-2004, 06:56 AM
  5. Connecting node in singly linked list
    By hmaya74 in forum C Programming
    Replies: 1
    Last Post: 03-16-2002, 09:50 AM

Tags for this Thread