Добавить узел в связанный список (ошибка сегментации)

Question

В заголовке связанного списка вводятся данные, а также индекс, в котором должен быть добавлен узел, и значение, связанное с этим узлом. Программа возвращает заголовок обновленного списка. Если индекс больше размера списка, программа должна вернуть NULL.

В чем причина ошибки и как можно улучшить / оптимизировать код?

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

Answer 1

Когда вы пишете:

 head = temp;  

Вы просто перезаписываете value адреса, переданного как argument. Поэтому содержимое заголовка не будет изменено при выходе из функции. Вы увеличиваете размер списка, но не добавляете элементы, которые вызывают ошибку сегментации при вызове:

head = (head)->next;   

head = NULL до , заканчивая количество итераций, потому что ваш список не содержат size элементов, поэтому (head)->next вызывает ошибку сегментации.

Если вы хотите изменить содержимое вашей головы из функции, вам нужен параметр Node **. Я исправил вашу программу и добавил функцию освобождения памяти (freeList () для вызова в конце программы), чтобы избежать утечек памяти:

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

Результат: