Segmentation fault in Linked List code, deletion part

Question

I am trying to code for insertion and deletion in linked list. Here is my code for basic insertion and deletion of nodes in a singly linked list. There are no errors in the code, but the output on the terminal shows segmentation fault. Can someone explain why am I getting a segmentation fault? And what changes do i make to remove the fault. I believe the segmentation fault is in the deletion part. Please help.

// class is a type of user defined datatype
class Node {
    public:
    int data;
    Node* next;

    //constructor
    Node(int data) {
        this -> data = data;
        this -> next = NULL;
    }

    // destructor
    ~Node() {
        int value = this -> data;
        //memory free krr rhe hain
        if(this -> next != NULL){
            delete next;
            this -> next = NULL;
        }
        cout << "memory is free for node with data" << value << endl;
    }

};

void insertAtHead(Node* &head, int data) {

    // creating new node called temp of type Node 
    Node* temp = new Node(data);
    temp -> next = head;
    head = temp;
}

void insertAtTail(Node* &head, Node* &tail, int data) {
    // //New node create
    // Node* temp = new Node(data);
    // tail -> next = temp;
    // tail = temp;

    Node* temp = new Node(data);
    if (head == nullptr) { // If this is the first node of the list
        head = temp;
    } else { // Only when there is already a tail node
        tail -> next = temp;
    }
    tail = temp;
}

void insertAtPosition(Node* &tail, Node* &head, int position, int data) {

    // Insert at starting
    if(position == 1) {
        insertAtHead(head, data);
        return;
    }

    // Code for inserting in middle
    Node* temp = head;
    int cnt = 1;

    while(cnt < position-1) {
        temp = temp -> next;
        cnt++;
    }

    // Creating a node for data
    Node* nodeToInsert = new Node(data);
    nodeToInsert -> next = temp -> next;
    temp -> next = nodeToInsert;

    // Inserting at last position (tail) 
    if(temp -> next == NULL) {
        insertAtTail(head,tail, data);
        return;
    }
}

void deleteNode(int position, Node* &head) {
    
    //deleting first or starting node
    if(position == 1) {
        Node* temp = head;
        head = head -> next;
        //memory free start node
        temp -> next = NULL;
        delete temp;

    } else {
        // deleting any middle node
        Node* curr = head;
        Node* prev = NULL;

        int cnt = 1;
        while(cnt <= position) {
            prev = curr;
            curr = curr -> next;
            cnt++;
        }

        prev -> next = curr -> next;
        curr -> next = NULL;
        delete curr;
    }
}

void print(Node* &head) {

    Node* temp = head;
    while(temp != NULL) {
        cout << temp -> data << " ";
        temp = temp -> next;
    }
    cout << endl;
}

int main() {

    Node* head = nullptr; // A list has a head
    Node* tail = head; //  a tail.

    insertAtHead(head, 10); // pass the head
    insertAtTail(head, tail, 20);
    insertAtTail(head, tail, 30);
    insertAtHead(head, 5);
    print(head);  // Print the whole list

    cout << "head" << head -> data << endl;
    cout << "tail" << tail -> data << endl;

    deleteNode(1, head);
    print(head);
}

Do you know what a debugger is? It can help you to find your problem very easily — RoQuOTriX
– RoQuOTriX, Commented Aug 2, 2022 at 5:47

Zulfiqar Chaudhry · Accepted Answer · 2022-08-02 06:01:28Z

The problem is not with the delete function since even commenting it out leads to segmentation fault.

The problem is that you are initializing tail = head which is set to nullptr at the start. However, when you insertAtHead, you set the value of head but leave the tail to nullptr. You need to do tail = head when adding the first node (when head == nullptr).

Refer below for working code:

// Online C++ compiler to run C++ program online
#include <iostream>
using namespace std;

// class is a type of user defined datatype
class Node {
    public:
    int data;
    Node* next;

    //constructor
    Node(int data) {
        this -> data = data;
        this -> next = NULL;
    }

    // destructor
    ~Node() {
        int value = this -> data;
        //memory free krr rhe hain
        if(this -> next != NULL){
            delete next;
            this -> next = NULL;
        }
        cout << "memory is free for node with data" << value << endl;
    }

};

void insertAtHead(Node* &head,Node* &tail, int data) {

    // creating new node called temp of type Node 
    Node* temp = new Node(data);
    temp -> next = head;
    
    if (head == nullptr)
        tail = temp; //inializing tail
    
    head = temp;
}

void insertAtTail(Node* &head, Node* &tail, int data) {
    // //New node create
    // Node* temp = new Node(data);
    // tail -> next = temp;
    // tail = temp;

    Node* temp = new Node(data);
    if (head == nullptr) { // If this is the first node of the list
        head = temp;
    } else { // Only when there is already a tail node
        tail -> next = temp;
    }
    tail = temp;
}

void insertAtPosition(Node* &tail, Node* &head, int position, int data) {

    // Insert at starting
    if(position == 1) {
        insertAtHead(head,tail, data);
        return;
    }

    // Code for inserting in middle
    Node* temp = head;
    int cnt = 1;

    while(cnt < position-1) {
        temp = temp -> next;
        cnt++;
    }

    // Creating a node for data
    Node* nodeToInsert = new Node(data);
    nodeToInsert -> next = temp -> next;
    temp -> next = nodeToInsert;

    // Inserting at last position (tail) 
    if(temp -> next == NULL) {
        insertAtTail(head,tail, data);
        return;
    }
}

void deleteNode(int position, Node* &head) {
    
    //deleting first or starting node
    if(position == 1) {
        Node* temp = head;
        head = head -> next;
        //memory free start node
        temp -> next = NULL;
        delete temp;

    } else {
        // deleting any middle node
        Node* curr = head;
        Node* prev = NULL;

        int cnt = 1;
        while(cnt <= position) {
            prev = curr;
            curr = curr -> next;
            cnt++;
        }

        prev -> next = curr -> next;
        curr -> next = NULL;
        delete curr;
    }
}

void print(Node* &head) {

    Node* temp = head;
    while(temp != NULL) {
        cout << temp -> data << " ";
        temp = temp -> next;
    }
    cout << endl;
}

int main() {

    Node* head = nullptr; // A list has a head
    Node* tail = head; //  a tail.

    insertAtHead(head,tail, 10); // pass the head
    insertAtTail(head, tail, 20);
    insertAtTail(head, tail, 30);
    insertAtHead(head,tail, 5);
    print(head);  // Print the whole list

    cout << "head" << head -> data << endl;
    cout << "tail" << tail -> data << endl;

    deleteNode(1, head);
    print(head);
}

Thankyou for the explanation, and for resolving the issue as well.

Schol-R-LEA · Accepted Answer · 2022-08-02 06:04:21Z

2

The segfault is actually in the function insertAtTail(), and is because, while you handle the case where head is a null pointer, you do not handle the case where there is a head node but no tail node. The following code fixes this issue:

void insertAtTail(Node* &head, Node* &tail, int data) {
    // //New node create
    Node* temp = new Node(data);
    if (head == nullptr) { // If this is the first node of the list
        head = temp;
    } else if (tail == nullptr) { // if there's a head but no tail
        head -> next = temp;
    } else {               // Only when there is already a tail node
        tail -> next = temp;
    }
    tail = temp;
}

answered Aug 2, 2022 at 6:04

Schol-R-LEA

4114 silver badges10 bronze badges

1 Comment

Zulfiqar Chaudhry Over a year ago

Good observation. However, if tail is initialized with head, there will not be any case in which head is null and tail is not. So if we initialize the tail=head in insertAtHead, this issue should resolve itself. Notice that calling insertAtTail before insertAtHead will not cause an error since when head==nullptr, tail is also nullptr.

RoQuOTriX · Accepted Answer · 2022-08-02 06:01:45Z

If you have a look at this part of your code:

int main() 
{
    Node* head = nullptr; // A list has a head
    Node* tail = head; //  a tail.

    insertAtHead(head, 10); // pass the head
    insertAtTail(head, tail, 20);

    return 0;
}

tail is a nullptr as you pass it into insertAtTail(head, tail, 20);

Then in insertAtTail you are going to access this nullptr:

void insertAtTail(Node* &head, Node* &tail, int data) {
    // //New node create
    // Node* temp = new Node(data);
    // tail -> next = temp;
    // tail = temp;

    Node* temp = new Node(data);
    if (head == nullptr) { 
        head = temp;
    } else { 
        // here you have nullptr access resulting in your segmentation fault
        tail -> next = temp;
    }
    tail = temp;
}

Collectives™ on Stack Overflow

Segmentation fault in Linked List code, deletion part

3 Answers 3

1 Comment

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related