Home > OS >  Segmentation fault in Linked List code, deletion part
Segmentation fault in Linked List code, deletion part

Time:08-03

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

CodePudding user response:

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

CodePudding user response:

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

CodePudding user response:

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;
}
  • Related