Can you check why removing an Item from a linked list is not working in this code?

Question

I've been asked by a friend to help him with an exercise, basically the idea is like below.

Car number = fr50000       Car owner = AlexNelson       Parking time = 3.5 hours.

He was told not to use stuff like string or getline, so it's simple app just to learn the idea of working with linked lists.

So I made this program. When I'm calling the remove() function the first time, it says the list is empty at the beginning (as it should do). But the second and third time, it's saying that the car is removed, but when I call the display() function, the car is still there (it didn't remove from the list)

Can you tell me what's wrong with my code?

#include <iostream>
using namespace std;

int length = 0;//variable of how many items in the list

struct node
{
    char carNumber[15];
    char carOwner[20];
    float parkingTime;
    node *link;
};
typedef struct node node;

node *head;//the begining of a list;

bool isempty()
{
    if (length == 0)
        return true;
    else
        return false;
}

void insert()
{
    if (isempty())
    {
        head = new node;
        cout << "Enter car number: ";
        cin >> head->carNumber;
        cout << "Enter Car owner: ";
        cin >> head->carOwner;
        cout << "Enter parking time: ";
        cin >> head->parkingTime;
        head->link = NULL;
        length++;
    }
    else
    {
        node *p = head;
        node *pnext = new node;
        while (true)
        {
            if (p->link == NULL)
            {
                p->link = pnext;
                break;
            }
            p = p->link;
        }
    
        cout << "Enter car number: ";
        cin >> pnext->carNumber;
        cout << "Enter Car owner: ";
        cin >> pnext->carOwner;
        cout << "Enter parking time: ";
        cin >> pnext->parkingTime;
        pnext->link = NULL;
        length++;
    }
}

void remove()
{
    if (isempty())
    {
        cout << "List is empty\n";
        return;
    }

    char carnumber[15];
    cout << "Enter car number to remove: ";
    cin >> carnumber;
    node *p;
    p = head;
    while (p != NULL)
    {
        if (strcmp(p->carNumber, carnumber) == 0)
        {
            p = p->link;
            cout << "Car removed\n";
            return;
        }
        p = p->link;
    }
    
    cout << "Car was not found, check the number\n";
}

void display()
{
    if (isempty())
    {
        cout << "List is empty\n";
        return;
    }

    cout << "Car Number\t\tCar Owner\t\tParking Time\n";
    node *p = head;
    while (p != NULL)
    {
        cout << p->carNumber << "\t\t" << p->carOwner << "\t\t" << p->parkingTime << " Hours\n";
        p = p->link;
    }
}

int main()
{
    string number;
    display();
    insert();
    insert();
    insert();
    display();
    remove();
    display();
    insert();
    remove();
    display();
}

Does this exercise *require* you to write linked-list code? It can be implemented much more easily otherwise. — cigien, Jul 06 '20 at 22:16
Your `remove` function doesn't do anything to change the list. — interjay, Jul 06 '20 at 22:19
See [How do I properly delete nodes of linked list in C++](https://stackoverflow.com/questions/22121257/how-do-i-properly-delete-nodes-of-linked-list-in-c). Pay special attention to the **Alternative Using Pointer To Pointer** — user4581301, Jul 06 '20 at 22:22

score 0 · Answer 1 · answered Jul 06 '20 at 22:19

0

p = p->link; You're modifying the value of the local variable p, not the list. You need to modify the previous node's link field.

answered Jul 06 '20 at 22:19

Paramecium13

345
1
7

can you suggest a small code or explain it more to just to understand what you mean please ? I couldn't get it. – Ali Jul 06 '20 at 22:23

score 0 · Accepted Answer · answered Jul 06 '20 at 22:26

Your remove() function is not actually removing (or destroying) a node from the list. You need to update the link of the previous node in the list to point to the next node in the list. And you need to update the head too, if removing the 1st node in the list.

Try this instead:

void remove()
{
    if (isempty())
    {
        cout << "List is empty\n";
        return;
    }

    char carnumber[15];
    cout << "Enter car number to remove: ";
    cin >> carnumber;

    node *p = head;
    node *prev = NULL;

    while (p != NULL)
    {
        if (strcmp(p->carNumber, carnumber) == 0)
        {
            if (p == head)
                head = p->link;

            if (prev)
                prev->link = p->link;

            delete p;

            cout << "Car removed\n";
            return;
        }

        prev = p;
        p = p->link;
    }
    
    cout << "Car was not found, check the number\n";
}

Alternatively:

void remove()
{
    if (isempty())
    {
        cout << "List is empty\n";
        return;
    }

    char carnumber[15];
    cout << "Enter car number to remove: ";
    cin >> carnumber;

    node **p = &head;

    while (*p != NULL)
    {
        if (strcmp((*p)->carNumber, carnumber) == 0)
        {
            node *n = *p;
            *p = (*p)->link;

            delete n;

            cout << "Car removed\n";
            return;
        }

        p = &(p->link);
    }
    
    cout << "Car was not found, check the number\n";
}

Thank you so much !!! really appreciated, hope you have a good day sir! — Ali, Jul 06 '20 at 22:31

cigien · Answer 3 · 2020-07-06T22:36:15.973

0

In the loop in remove, you are doing p = p->link, when p points to the node you want to remove. But you actually need to update the link field of the node that is pointing to p.

Here's a simple way of doing that:

node **p = &head;
while(*p)
  if (strcmp((*p)->carNumber, carnumber) == 0)
     break;
  else p = &(*p)->link;

if (*p)
{  
    cout<<"Car removed\n";
    delete std::exchange(*p, (*p)->link);
}
else cout << "Car was not found, check the number\n";

If you can't use std::exchange, then you can replace that with:

auto h = *p;
*p = (*p)->link);
delete h;

edited Jul 06 '20 at 22:36

answered Jul 06 '20 at 22:29

cigien

57,834
11
73
112

If the OP's friend is not allowed to use things like `std::string` and `std::getline()`, they are certainly not going to be allowed to use `std::exchange()`, either. – Remy Lebeau Jul 06 '20 at 22:32
@RemyLebeau Oh, that was added to the question. Shame, this is much more elegant :p – cigien Jul 06 '20 at 22:35
"*this is much more elegant*" - using `std::(forward_)list` would be an even more elegant solution. But it seems the exercise doesn't want elegance ;-) – Remy Lebeau Jul 06 '20 at 22:36
cigien @RemyLebeau is right and tbh I haven't heard of it too, still learning about pointers as you see I made a huge mistake that I should've been aware of, Thanks a million for your efforts both of u guys. have a good day <3 – Ali Jul 06 '20 at 22:36
@AliGx Well, this is a goof opportunity to learn :) – cigien Jul 06 '20 at 22:37
2

@AliGx "*still learning about pointers*" - in all honestly, *modern* C++ code should strive to *stay away* from using *raw* pointers and `new` as much as possible. They have their share of uses, and they have their share of error-prone mistakes, too. The fewer *raw* pointers you use, the less error-prone your code will be. – Remy Lebeau Jul 06 '20 at 22:37
@RemyLebeau Exactly, that was my first question for the OP. But if they have to write a linked-list, they have to write it. Giving up one abstraction doesn't mean they have to give up all of them :) – cigien Jul 06 '20 at 22:38

Can you check why removing an Item from a linked list is not working in this code?

3 Answers3