Segmentation fault while implementing linkedlists in c++

Question

I am currently learning data structures, I was trying to create a function insert to insert a node at the nth position but I am always getting a segmentation error could you please help.

#include <iostream>
using namespace std;
struct node {
  int data;
  node* next;
};
struct node* head = NULL;
void insert(int dat, int pos) {
  node* temp = new node;
  temp->data = dat;
  temp->next = NULL;
  if (pos == 1) {
    temp->next = head;

    head = temp;
    return;
  }
  node* newtemp = head;
  for (int i = 0; i <= pos - 1; i++) {
    newtemp = newtemp->next;
  }
  temp->next = newtemp->next;
  newtemp->next = temp;
}
void print() {
  node* temp = head;
  while (temp != NULL) {
    cout << temp->data;
    temp = temp->next;
  }
  cout << endl;
}
int main() {
  head = NULL;
  insert(4, 1);
  insert(6, 2);
  print();
}

Answer 1

Look at this statement of insert() function:

  for (int i = 0; i <= pos - 1; i++) {

For inserting element 6, you are giving positing 2.

  First iteration:

  initialize i with 0
  0 <= 2 - 1 ==> true

  newtemp = newtemp->next
  [After this statement, newtemp is NULL because your linked list has only one element]

  i++  ==> i is now 1

  Second iteration

  1 <= 2 - 1  ===> true

  newtemp = newtemp->next

  [newtemp is NULL and this statment will attempt to access next of a NULL
   which is resulting in segmentation fault]

I hope you understood the cause of segmentation fault and a simple change can solve this problem - add NULL check for newtemp node, like this

  for (int i = 0; i < pos && newtemp->next != NULL; i++) {

Your code does not check the validity of a pos value passed and with your current implementation it will add the element at the end of list if the pos value is greater than size of linked list. May you want to throw error when the value of pos is not valid. Also, you are not releasing the memory allocated for linked list nodes. Follow the good programming practice - release allocated memory before program exit.

---

Additional:

Since you are implementating the linked list in c++, you should use the object oriented concepts in you implementation. For e.g. bundle the data and functions operate on that data in one unit:

class Node {
private: 
        int data; 
        Node* next;
public: 
        // Add constructor for initialization of memeber variables
        // Add destructor for cleanup and release memory
        void insert(int dat, int pos);
        void print();
};

A better implementation would be to separate the node and linkedlist in two different classes and bind their data with respective operations in them. For e.g.

class Node {
private:
        int data;
        Node* next;
public:
        Node();
        Node(const int& val);
        void setData(const int& val);
        int getData() const;
        void setNext(Node* const nodePtr);
        Node* getNext() const;
};

Singly linked list class LinkedList consisting of Node objects:

class LinkedList {
private:
        Node* headNode;
        Node* tailNode;
        Node* currNode;
        unsigned int count;
public:
        LinkedList(); // constructor
        // other overload of constructor, copy constructor, assignment operator, move semantics ....
        ~LinkedList(); // destructor 

        bool insertNode(const Node& newNode);
        // other overload of insert, like insert at given position, at head of list, at tail of list etc..

        unsigned int getCount() const;
        Node* getHeadNode() const;
        Node* getCurrNode() const;
        Node* getTailNode() const;

        bool deleteNode(const Node& node);
        // other overload of delete node like detete tail node, delete head node etc.

        bool deleteList();
};

Answer 2

It should be

i<pos-1
temp->next=newtemp->next;
newtemp->next=temp;

And you should check if the Linkedlist have the position you have given

ie, if you pass to add node in 6th position to a Linkedlist having 2 nodes, it will give you segmentation fault.

By NULL->next

So you should check whether the linked list have the length less than or equal to position.

    flag=false;
  while(temp!=NULL)
{
      if(i==Pos){
          flag=true;
          break;
      }
      temp=temp->next;
     i++;
}

if flag is false then length is insufficient else do your stuff in temp