error in remove method for singly linked list

Question

#include <iostream>
using namespace std;

template <typename Object>
struct Node
{
    Object data;
    Node* next;
    Node(const Object &d = Object(), Node *n = (Object)NULL) : data(d), next(n) {}
};

template <typename Object>
class singleList
{
public:
    singleList() { init(); }
    ~singleList() { eraseList(head); }
    singleList(const singleList &rhs)
    {
        eraseList(head);
        init();
        *this = rhs;
        print();
        contains(head);
    }

    void init()
    {
        theSize = 0;
        head = new Node<Object>;
        head->next = (Object)NULL;
    }

    void eraseList(Node<Object> *h)
    {
        Node<Object> *ptr = h;
        Node<Object> *nextPtr;
        while (ptr != (Object)NULL)
        {
            nextPtr = ptr->next;
            delete ptr;
            ptr = nextPtr;
        }
    }

    int size()
    {
        return theSize;
    }

    void print()
    {
        int i;
        Node<Object> *current = head;
        for(i=0; i < theSize; ++i){
            cout << current->data << " ";
            current = current->next;
        }

    }

    bool contains(int x)
    {
        Node<Object> *current = head;
        for (int i = 0; i < theSize; ++i){
            if (current->data == x){
                return true;
            }
            current = current -> next;
        }
        return false;

    }

    bool add(Object x){
        if(!contains(x)){
            Node<Object> *new_node = new Node<Object>(x);
            new_node->data = x;
            new_node->next = head;
            head = new_node;
            //head->next = new_node;
            theSize++;
            return true;
        }
        return false;
    }

    bool remove(int x)
    {
        if(contains(x)){
            Node<Object> *temp = head;
            Node<Object> *prev = NULL;

            if(temp != NULL && temp ->data == x){
                head = temp->next;
                delete temp;
                return 0;
            }else{
                while(temp != NULL && temp->data != x){
                    prev = temp;
                    temp = temp->next;
                }
                if(temp ==NULL){
                    return 0;

                }
                prev->next = temp->next;
                delete temp;
            }
            return true;
            //theSize--;
        }
        return false;
    }

private:
    Node<Object> *head;
    int theSize;
};

 int main()
 {
     singleList<int> *lst = new singleList<int>();
     lst->add(10);
     lst->add(12);
     lst->add(15);
     lst->add(6);
     lst->add(3);
     lst->add(8);
     lst->add(3);
     lst->add(18);
     lst->add(5);
     lst->add(15);

     cout << "The original linked list: ";
     lst->print();
     cout << endl;
     lst->remove(6);
     lst->remove(15);
     cout << "The updated linked list: ";
     lst->print();
     cout << endl;
     cout << "The number of node in the list: " << lst->size() << endl;

     return 0;
 }

so the output is supposed to be the following:

The original linked list: 5 18 8 3 6 15 12 10
The update linked list: 5 18 8 3 12 10
The number of node in the list: 6

my output gives the original linked list part but then gives a segmentation fault (core dumped) error. I am not sure where my code is wrong but i think it is in my remove().

Some help will definitely be appreciated.

[What is a debugger?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — PaulMcKenzie, Sep 18 '21 at 01:48
@PaulMcKenzie i ran the debugger on vscode and it is point to the print(). ont he line where it says cout.. — donkeykongcodes, Sep 18 '21 at 01:59
@donkeykongcodes Another piece of advice -- don't use so much test data. Just use 3 or 4 data, not 10 items. If your linked list does not work with 3 items, it isn't going to work with 10 items. I bet you didn't test your code with a smaller amount of items, and instead trusted what you wrote and went ahead with 10 items. If you use a smaller amount of test data, it would make it easier for you to follow your code to see where the logic goes wrong. — PaulMcKenzie, Sep 18 '21 at 02:13
hey @Eljay you were correct. I needed to do theSize--; in the remove() on line 109. That fixed the error. — donkeykongcodes, Sep 18 '21 at 02:20
Unrelated: [See the Community addition in this answer](https://stackoverflow.com/a/22122095/4581301) for a simpler way to remove items from a singly linked list. You can use the same pointer-to-pointer trick to simplify an insert routine. — user4581301, Sep 18 '21 at 03:01
@user4581301 hey thank you for this it really helped. Even though i answered my own question earlier David C. Rankin found a possible future error and this source that you shared really helped. — donkeykongcodes, Sep 18 '21 at 03:40

score 0 · Answer 1 · answered Sep 18 '21 at 02:22

0

on line 109 i needed to decrement size.

bool remove(int x)
    {
        if(contains(x)){
            Node<Object> *temp = head;
            Node<Object> *prev = NULL;

            if(temp != NULL && temp ->data == x){
                head = temp->next;
                delete temp;
                return 0;
            }else{
                while(temp != NULL && temp->data != x){
                    prev = temp;
                    temp = temp->next;
                }
                if(temp ==NULL){
                    return 0;

                }
                prev->next = temp->next;
                delete temp;
                theSize--;
            }
            return true;
            //theSize--;
        }
        return false;
    }

answered Sep 18 '21 at 02:22

donkeykongcodes

13
5

Good job finding that issue. However, you are not quite done. Add `lst->remove(5);` as your first removal and see what happens... A bit more debugging to do. You may want to look at the `delnode()` function in [C++ List Template Example](https://pastebin.com/Sq1MPU15) for ideas on how to simplify your remove function. See [Linus on Understanding Pointers](https://grisha.org/blog/2013/04/02/linus-on-understanding-pointers/) for details of iterating with both the address-of-node and pointer-to-node. – David C. Rankin Sep 18 '21 at 02:37
*"on line 109"* -- a line number this high often means that the question failed to narrow down the problem to a [mre]. (The more code people have to look through to help, the more likely they are to move on without helping.) – JaMiT Sep 18 '21 at 02:53
@DavidC.Rankin Thank you for letting me know. Someone posted a different source that was easier to follow and it worked. Now when i remove 5 is works but earlier with my answer it was not. Thank you again. I will post my final answer below. – donkeykongcodes Sep 18 '21 at 03:42

score 0 · Answer 2 · answered Sep 18 '21 at 03:42

Answer after second update:

had to fix the remove()

#include <iostream>
using namespace std;

template <typename Object>
struct Node
{
    Object data;
    Node* next;
    Node(const Object &d = Object(), Node *n = (Object)NULL) : data(d), next(n) {}
};

template <typename Object>
class singleList
{
public:
    singleList() { init(); }
    ~singleList() { eraseList(head); }
    singleList(const singleList &rhs)
    {
        eraseList(head);
        init();
        *this = rhs;
        print();
        contains(head);
    }

    void init()
    {
        theSize = 0;
        head = new Node<Object>;
        head->next = (Object)NULL;
    }

    void eraseList(Node<Object> *h)
    {
        Node<Object> *ptr = h;
        Node<Object> *nextPtr;
        while (ptr != (Object)NULL)
        {
            nextPtr = ptr->next;
            delete ptr;
            ptr = nextPtr;
        }
    }

    int size()
    {
        return theSize;
    }

    void print()
    {
        int i;
        Node<Object> *current = head;
        for(i=0; i < theSize; ++i){
            cout << current->data << " ";
            current = current->next;
        }
        
    }   

    bool contains(int x)
    {
        Node<Object> *current = head;
        for (int i = 0; i < theSize; ++i){
            if (current->data == x){
                return true;
            }
            current = current -> next;
        }
        return false;

    }

    bool add(Object x){
        if(!contains(x)){
            Node<Object> *new_node = new Node<Object>(x);
            new_node->data = x;
            new_node->next = head;
            head = new_node;
            //head->next = new_node;
            theSize++;
            return true;
        }
        return false;
    }

    bool remove(int x){
        Node<Object> *pCur  = head;
        Node<Object> *pPrev = pCur;

        while (pCur && pCur->data != x) {
            pPrev = pCur;
            pCur  = pCur->next;
        }

        if (pCur==nullptr)  // not found
            return false;

        if (pCur == head) {   // first element matches
            head = pCur->next;
        } else {
            pPrev->next = pCur->next;
        }

        // pCur now is excluded from the list

        delete pCur; 
        theSize--;
        return true;
    }

private:
    Node<Object> *head;
    int theSize;
};

 int main()
 {
     singleList<int> *lst = new singleList<int>();
     lst->add(10);
     lst->add(12);
     lst->add(15);
     lst->add(6);
     lst->add(3);
     lst->add(8);
     lst->add(3);
     lst->add(18);
     lst->add(5);
     lst->add(15);

     cout << "The original linked list: ";
     lst->print();
     cout << endl;
     lst->remove(6);
     lst->remove(15);
     cout << "The updated linked list: ";
     lst->print();
     cout << endl;
     cout << "The number of node in the list: " << lst->size() << endl;

     return 0;
 }

Careful there. You're starting to use SO's answers like forum posts. Generally you should write one answer and edit corrections into it rather than creating a second answer unless the second answer is radically different. In this case I don't think it's different enough to rate a whole new answer. — user4581301, Sep 18 '21 at 03:45

error in remove method for singly linked list

2 Answers2