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

Well, trace your program's expected behaviour with pen and paper and work out where it diverges from reality. — Lightness Races in Orbit
– Lightness Races in Orbit, Commented May 16, 2017 at 16:19

Pavel P · Accepted Answer · 2017-05-16 17:02:37Z

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?

edited May 16, 2017 at 17:02

answered May 16, 2017 at 16:27

Pavel P

17.3k11 gold badges91 silver badges143 bronze badges

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

1 Comment

Amre Over a year ago

Beat me to the punch. haha. Also, don't forget. This misses the edge case where the node that needs to be deleted is the first node in the list.

Jayson Boubin · Accepted Answer · 2017-05-16 16:37:11Z

0

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

answered May 16, 2017 at 16:37

Jayson Boubin

1,5142 gold badges12 silver badges19 bronze badges

Comments

Remy Lebeau · Accepted Answer · 2017-05-16 19:52:38Z

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

Collectives™ on Stack Overflow

How to delete node from linked list?

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related