Unable to add a node in a linked list

Question

I tried to modify the code a few times but was unable to find the mistake in the code. My program is running but I have a hard time adding the node to the correct position.

#include<iostream>

using namespace std;

struct Node
{
    int data;
   struct Node *next;
}*HEAD=NULL;

void create(int a[],int n)
{
    struct Node *p;
    cout<<"Enter the number of elements of LL you want to display "<<endl;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        if(i==0)
        {
            HEAD=new Node;
            p=HEAD;
            p->data=a[0];
        }
        else
        {
            p->next=new Node;
            p=p->next;
            p->data=a[i];
        }
        
        
          p->next=NULL;
    }
 
}   
 void insertion(struct Node *p,int pos,int x)
{
    struct Node *t;
    int i,n;
    if(pos<0||pos>n)
    cout<<"Invalid position "<<endl;
    t=new Node;
     t->data=x;
    // t->next==NULL;
     if(pos==0)
     {
         t->next=HEAD;
         HEAD=t;
     }
     
    else
    for(i=0;i<pos-1;i++)
    {
        p=p->next;
        t->next=p->next;
        p->next=t;
    }
    
}
void display(struct Node *HEAD)
{   
    struct Node *p;
    p=HEAD;
    while(p!=NULL)
    {
        cout<<p->data;
        p=p->next;
        
    }
}
int main()
{
    struct Node *temp;
    int n;
    cout<<"enter the value of n "<<endl;
    cin>>n;
    int a[n];
    cout<<"Array elements are "<<endl;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    create(a,n);
   insertion(HEAD,1,15);
    display(HEAD);
}

Answer 1

There are several issues:

• In insertion you should move the following statements out of the loop, since they should only happen once, but also once when the loop does not iterate at all. This is the reason why you don't see a node added when you pass a position of 1:

  t->next = p->next;
  p->next = t;
  

• if(pos<0||pos>n) is not reliable as n is not initialised. You should not need n at all. You can make the second test while walking through the list and bumping into the end of the list before reaching the desired position.

• Don't ask for input of n in create as you already got this input in the main program.

• Your display function sticks all output together so that you cannot really see which is which. You should separate values with a separator like a space.

• Don't use a global variable for your list. It is bad practice and will not allow you to use these functions for when you have more than one list.

• Don't name that variable with all capitals. That is commonly reserved for constants.

• In C++ use nullptr and not NULL when assigning/comparing node pointers.

• When you find the position is out of range, you should exit the function.

• As head will not be a global variable, let create return it, and pass it by reference to insertion.

• Take note of Why is "using namespace std;" considered bad practice?

Here is a corrected version:

#include<iostream>

struct Node {
    int data;
    Node *next;
};

// Let function return the new linked list
Node *create(int a[], int n) {
    Node *head = nullptr; // local variable & not CAPS
    Node *p;
    if (n == 0)
        return nullptr;
    // No input should be asked here
    head = new Node;
    p = head;
    p->data = a[0];
    for (int i = 1; i < n; i++) {
        p->next = new Node;
        p = p->next;
        p->data = a[i];
    }
    p->next = nullptr;
    return head;
}

void insertion(Node **head, int pos, int x) {
    if (pos < 0) {
        std::cout << "Invalid position " << std::endl;
        return; // Should quit!
    }
    Node *t = new Node;
    t->data = x;
    if (pos == 0) {
        t->next = *head;
        *head = t;
    } else {
        Node *p = *head;
        for (int i = 0; i < pos - 1; i++) {
            p = p->next;
            // Without n you can test out of range here:
            if (p == nullptr) {
                std::cout << "Invalid position" << std::endl;
                delete t;
                return;
            }
        }
        // The following should happen outside the loop
        t->next = p->next;
        p->next = t;
    }
}

void display(Node *head) {   
    Node *p = head;
    while (p != nullptr) {
        std::cout << p->data << " "; // separate with space
        p = p->next;
    }
    std::cout << std::endl; // Newline
}

int main() {
    int n;
    std::cout << "Enter the value of n " << std::endl;
    std::cin >> n;

    int a[n];
    std::cout << "Array elements are " << std::endl;
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    // Define head as local variable - no CAPS
    Node *head = create(a,n);
    display(head);
    insertion(&head, 1, 15);
    display(head);
}