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

• Omid CompSCI: Step through it with a debugger. If you don't know how add std::cout statements in between the lines and work your way through where the last print statement is and you'll know where the issue is. Add null checks when possible. My guess is anytime people implement a position or index and use that to traverse through a linked list that is most likely the issue. You should be traversing through using temp->next != nullptr in the insert()
• Basile Starynkevitch: Read a good C++ programming book and the documentation of your C++ compiler. For GCC see this and also read the documentation of your debugger (e.g. GDB). See this reference and read How to debug small programs

Answer 1

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

Answer 2

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