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

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() — Omid CompSCI
– Omid CompSCI, Commented Jun 11, 2020 at 2:48
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 — Basile Starynkevitch
– Basile Starynkevitch, Commented Jun 11, 2020 at 5:50

Anandha Krishnan Aji · Accepted Answer · 2020-06-11 03:04:43Z

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

edited Jun 11, 2020 at 3:04

answered Jun 11, 2020 at 2:59

Anandha Krishnan Aji

1621 silver badge10 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

H.S. · Accepted Answer · 2020-06-11 05:46:23Z

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

Collectives™ on Stack Overflow

Segmentation fault while implementing linkedlists in c++

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related