How to delete node from linked list?

Question

Adding integers to list works fine, but there's something wrong with deleting and printing.

I'm not friendly with debugger yet, but I found out that there is error from node pointer 'first'. Its value is -17891602. I don't know what happened...

#include <iostream>
using namespace std;

class nodeList;

class node {
    friend class nodeList;
private:
    int data;
    node* link;
public:
    node() { //constructor
        data = 0;
        link = NULL;
    }
    node(int d) { //constructor
        data = d;
        link = NULL;
    }
    node(int d, node* l){ //constructor
        data = d;
        link = l;
    }
};

class nodeList {
private:
    node* first;
    int num = 0;
    node* nt;
public:
    nodeList() {
        first = new node();
    }
    node* end(node* t){ //return pointer of last element
        t = first;
        for (int i = 0; i < num; i++){
            t = t->link;
        }
        return t;
    }
    void add(int a){ //add 'a' at the end of the list
        node* x = new node(a);
        node* y = this->end(nt);
        y->link = x;
        num++;
    }

    void del(int n){ //n : data of element that you want to delete from list
        node* temp = first;
        node* pretemp = NULL;
        node* x;
        int i;
        for (i = 0; i <= this->num; i++){ //loop to find 'n'
            pretemp = temp;
            temp = temp->link;
            if (n == temp->data){
                break;
            }
        }
        temp = first;
        for (int j = 0; j<i; j++){ //i : where 'n' is,
            temp = temp->link;
        }
        x = temp->link;
        pretemp->link = x;
        delete temp;
        num--;
    }
    void printList(){
        node* temp = first;
        temp = temp->link;
        for (int i = 0; i<this->num; i++){
            cout << temp->data << endl;
            temp = temp->link;
        }
    }
};

int main(){
    nodeList *l = new nodeList();
    int a;
    int select;
    while (1){
        cout << "1. ADD  2. DELETE  3. PRINT" << endl;
        cin >> select;

        if (select == 1){
            cout << "Enter an integer: ";
            cin >> a;
            if (cin.fail()) {
                cout << "Wrong input" << endl;
                break;
            }
            l->add(a);
            l->printList();
        }

        if (select == 2){
            cout << "Enter the data of the element you want to delete: ";
            cin >> a;
            if (cin.fail()) {
                cout << "Wrong input" << endl;
                break;
            }
            l->del(a);
            l->printList();
        }

        if (select == 3){
            l->printList();
        }
    }
}

Answer 1

Your code is a bit over-complicated for what it needs.

Try something more like this instead:

#include <iostream>
#include <limits>

using namespace std;

class nodeList;

class node
{
    friend class nodeList;

private:
    int data;
    node* link;

public:
    node(int d = 0) //constructor
        : data(d), link(NULL)
    {
    }
};

class nodeList
{
private:
    node* first;
    int num;

public:
    nodeList()
        : first(NULL), num(0)
    {
    }

    ~nodeList()
    {
        node *n = first, *t;
        while (n)
        {
            t = n->link;
            delete n;
            n = t;
        }
    }

    void add(int data) //add 'data' at the end of the list
    {
        node* n = new node(data);
        if (!first)
            first = n;
        else
        {
            node *t = first;
            while (t->link)
                t = t->link;
            t->link = n;
        }
        ++num;
    }

    void del(int data) //data : data of element that you want to delete from list
    {
        node* n = first;
        node* prev = NULL;

        while (n) //loop to find 'data'
        { 
            if (data == n->data)
            {
                if (prev)
                    prev->link = n->link;
                if (n == first)
                    first = n->link;
                delete n;
                --num;
                return;
            }
            prev = n;
            n = n->link;
        }
    }

    void printList()
    {
        for(node* n = first; n != NULL; n = n->link)
            cout << n->data << endl;
    }
};

int main()
{
    nodeList l;
    int input;
    bool keepGoing = true;

    do
    {
        cout << "1. ADD  2. DELETE  3. PRINT  4. EXIT" << endl;
        if (!(cin >> input))
        {
            cout << "Wrong input" << endl;
            cin.clear();
            cin.ignore(numeric_limits<streamsize_t>::max(), '\n');
        }
        else
        {
            switch (input)
            {
                case 1:
                    cout << "Enter an integer: ";
                    if (!(cin >> input))
                    {
                        cout << "Wrong input" << endl;
                        cin.clear();
                        cin.ignore(numeric_limits<streamsize_t>::max(), '\n');
                    }
                    else
                    {
                        l.add(input);
                        l.printList();
                    }
                    break;

                case 2:
                    cout << "Enter the data of the element you want to delete: ";
                    if(!(cin >> input))
                    {
                        cout << "Wrong input" << endl;
                        cin.clear();
                        cin.ignore(numeric_limits<streamsize_t>::max(), '\n');
                    }
                    else
                    {
                        l.del(input);
                        l.printList();
                    }
                    break;

                case 3:
                    l.printList();
                    break;

                case 4:
                    keepGoing = false;
                    break;

                default:
                    cout << "Wrong input" << endl;
                    cin.clear();
                    cin.ignore(numeric_limits<streamsize_t>::max(), '\n');
                    break;
            }
        }
    }
    while (keepGoing);

    return 0;
}

If you add an extra node* member to your nodeList class, you can simplify and speed up your add() method:

class nodeList
{
private:
    node* first;
    node* last;
    int num;

public:
    nodeList()
        : first(NULL), last(NULL), num(0)
    {
    }

    ~nodeList()
    {
        node *n = first, *t;
        while (n)
        {
            t = n->link;
            delete n;
            n = t;
        }
    }

    void add(int data) //add 'data' at the end of the list
    {
        node* n = new node(data);
        if (!first)
            first = n;
        if (last)
            last->link = n;
        last = n;
        ++num;
    }

    void del(int data) //data : data of element that you want to delete from list
    {
        node* n = first;
        node* prev = NULL;

        while (n) //loop to find 'data'
        { 
            if (data == n->data)
            {
                if (prev)
                    prev->link = n->link;
                if (n == first)
                    first = n->link;
                if (n == last)
                   last = prev;
                delete n;
                --num;
                return;
            }
            prev = n;
            n = n->link;
        }
    }

    void printList()
    {
        for(node* n = first; n != NULL; n = n->link)
            cout << n->data << endl;
    }
};

And if you can change your list to be a double-linked list instead of a single-linked list, you can simplify your del() method as well:

#include <iostream>
#include <limits>

using namespace std;

class nodeList;

class node
{
    friend class nodeList;

private:
    int data;
    node* prev;
    node* next;

public:
    node(int d = 0) //constructor
        : data(d), prev(NULL), next(NULL)
    {
    }
};

class nodeList
{
private:
    node* first;
    node* last;
    int num;

public:
    nodeList()
        : first(NULL), last(NULL), num(0)
    {
    }

    ~nodeList()
    {
        node *n = first, *t;
        while (n)
        {
            t = n->next;
            delete n;
            n = t;
        }
    }

    void add(int data) //add 'data' at the end of the list
    {
        node* n = new node(data);
        if (!first)
            first = n;
        if (last)
            last->next = n;
        n->prev = last;
        last = n;
        ++num;
    }

    void del(int data) //data : data of element that you want to delete from list
    {
        for(node* n = first; n != NULL; n = n->next) //loop to find 'data'
        { 
            if (data == n->data)
            {
                if (n->prev)
                    n->prev->next = n->next;
                if (n->next)
                    n->next->prev = n->prev;
                if (n == first)
                    first = n->next;
                if (n == last)
                    last = n->prev;
                delete n;
                --num;
                return;
            }
        }
    }

    void printList()
    {
        for(node* n = first; n != NULL; n = n->next)
            cout << n->data << endl;
    }
};

Answer 2

Your del function deletes pretemp node (node that was before the one that you need to delete).

Here's possible fix:

//n : data of element that you want to delete from list
void del(int n)
{
    //loop to find 'n'
    for (node *tmp = first; tmp->link; tmp = tmp->link)
    {
        if (n == tmp->link->data)
        {
            node *x = tmp->link;
            tmp->link = tmp->link->link;
            delete x;
            num--;
            break;
        }
    }
}

Also, was your del supposed to delete all nodes with data == n?

Answer 3

These functions are a bit complicated. Here is a simpler idea:

void del(int n){
    node* pretemp = first, *temp = first->link;
    if(pretemp->data == n) { //handle the deleting of the first node
            first = first->link;
            delete pretemp;
            return;
    }
    while(temp != NULL && temp->data != n) { //find the node with the data member "n"
            pretemp = temp;
            temp = temp->link;
    }
    if(temp != NULL) { //if you found the node, delete it
            pretemp->link = temp->link;
            delete temp;
    }
    --num;
 }