Add a node to a linked list (segmentation fault)

Question

The head of the linked list is input, as well as the index where the node should be added and the value associated with the node. The program returns the head of the updated list. If the index is greater than the size of the list, the program should return NULL.

What is the reason for the error and how may the code be improved/optimized?

#include <iostream>

class Node {
    public:
        int value;
        Node* next = NULL;
};

int size = 0; 

Node* getNode(int data) 
{ 
    // allocating space 
    Node* newNode = new Node(); 

    // inserting the required data 
    newNode->value = data; 
    newNode->next = NULL; 
    return newNode; 
} 

void add(Node* head, int index, int valueInput)
{
      if (index < 1 || index > size + 1) 
        std::cout << "Invalid position!" << std::endl;
      else { 
        // Keep looping until the pos is zero 
        while (index--) { 

            if (index == 0) { 

                // adding Node at required position 
                Node* temp = getNode(valueInput); 

                // Making the new Node to point to  
                // the old Node at the same position 
                temp->next = head; 

                // Changing the pointer of the Node previous  
                // to the old Node to point to the new Node 
                head = temp; 
            } 
            else
              // Assign double pointer variable to point to the  
              // pointer pointing to the address of next Node  
              head = (head)->next; 
        } 
        size++; 
    }
} 

void printList(struct Node* head) 
{ 
    while (head != NULL) { 
        std::cout << " " << head->value; 
        head = head->next; 
    } 
    std::cout << std::endl; 
} 


int main() 
{ 
    // Creating the list 3->5->8->10 
    Node* head = NULL; 
    head = getNode(3); 
    head->next = getNode(5); 
    head->next->next = getNode(8); 
    head->next->next->next = getNode(10); 

    size = 4; 

    std::cout << "Linked list before insertion: "; 
    printList(head); 

    int data = 12, pos = 3; 
    add(head, pos, data); 
    std::cout << "Linked list after insertion of 12 at position 3: "; 
    printList(head); 

    // front of the linked list 
    data = 1, pos = 1; 
    add(head, pos, data); 
    std::cout << "Linked list after insertion of 1 at position 1: "; 
    printList(head); 

    // insetion at end of the linked list 
    data = 15, pos = 7; 
    add(head, pos, data); 
    std::cout << "Linked list after insertion of 15 at position 7: "; 
    printList(head); 

    return 0; 
}

Assigning to a (non-reference) parameter of a function has no effect outside that function. There is no exception for pointers. — molbdnilo
– molbdnilo, Commented Apr 2, 2020 at 14:44
If your function should return a pointer to the new head, or a null pointer, why don't you do that? — molbdnilo
– molbdnilo, Commented Apr 2, 2020 at 14:46
You forgot to add the new node as the next member of the previous node. — melk
– melk, Commented Apr 2, 2020 at 15:11

Landstalker · Accepted Answer · 2020-04-02 18:03:52Z

When you write:

 head = temp;

You just overwrite the value of the address passed as an argument. Therefore the content of head will not be changed when you exit function. You increment list size but you don't add elements, wich cause a segmentation fault when you call:

head = (head)->next;

head = NULL before finishing the number of iterations because your list does not contain sizeelements, So (head)->next cause segmentation fault.

If you want to modify the content of your head from the function, you need a Node ** parameter. I corrected your program and add a memory release function (freeList () to call at the end of program) to avoid memory leaks:

void add(Node** head, int index, int valueInput)
{
    if (index < 1 || index > size + 1) 
        std::cout << "Invalid position!" << std::endl;
    else if ( NULL == head ) // Check if pointer is invalid
        std::cout << "Invalid head pointer !" << std::endl;
    else { 
        Node *pCurrentNode = *head;
        Node *pPreviousNode = *head;

        // Keep looping until the pos is zero 
        while (index--) { 

            if (index == 0) { 

                // adding Node at required position 
                Node* temp = getNode(valueInput); 

                // Insert new node BEFORE current node
                temp->next = pCurrentNode; 

                // Current != previous if we are not in a head insertion case
                if ( pCurrentNode != pPreviousNode)
                    pPreviousNode->next = temp; // insert new node AFTER previous node
                else 
                    *head = temp; // Update de content of HEAD and not juste it ADRESS!

                size++; // Increment size when we ADD a new node
            } 
            else
            {
                pPreviousNode = pCurrentNode; // Save previous node pointer
                pCurrentNode = pCurrentNode->next; // Get pointer of next node
            }
        } 

    }
} 

void freeList(struct Node* head) 
{ 
    Node* pCurrentNode = head;
    while ((pCurrentNode = head) != NULL) 
    { 
        head = head->next;          
        delete pCurrentNode;               
    }
}   

int main() 
{ 
    // Creating the list 3->5->8->10 
    Node* head = NULL; 
    head = getNode(3); 
    head->next = getNode(5); 
    head->next->next = getNode(8); 
    head->next->next->next = getNode(10); 

    size = 4; 

    std::cout << "Linked list before insertion: "; 
    printList(head); 

    int data = 12, pos = 3; 
    add(&head, pos, data); 
    std::cout << "Linked list after insertion of 12 at position 3: "; 
    printList(head); 

    // front of the linked list 
    data = 1, pos = 1; 
    add(&head, pos, data); 
    std::cout << "Linked list after insertion of 1 at position 1: "; 
    printList(head); 

    // insetion at end of the linked list 
    data = 15, pos = 7; 
    add(&head, pos, data); 
    std::cout << "Linked list after insertion of 15 at position 7: "; 
    printList(head); 

    freeList (head);

    return 0; 
}

Result:

Collectives™ on Stack Overflow

Add a node to a linked list (segmentation fault)

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related