Deleting elements from a linked list

[gdz98]

Hi guys I m practicing with this problem :
"Write a program to remove an element from a linked list; the remove function should take just the element to be removed."
I m trying to do it personal. Before to get to that function (that I ve no idea of how to write it to be honest ) i' d like to create a program that let the user insert name and age (choosing it only between 20, 30, or 40 yo) of a person and store it in a structure. Afterwards, it should print all the names of these people and the user can choose which one to delete. End eventually reprint all their names (except the one deleted obviously).

  #include <iostream>
#include <string>
using namespace std;
struct Group
{
    string name;
    int age;
    Group* p_next_element;
};
Group* Get20Years (Group* head)
{
    Group* person = new Group;
    person->age = 20;
    person->p_next_element = head;
    head = person;
    return person;
}
Group* Get30Years (Group* head)
{
    Group* person = new Group;
    person->age = 30;
    person->p_next_element = head;
    head = person;
    return person;
}
Group* Get40Years (Group* head)
{
    Group* person = new Group;
    person->age = 40;
    person->name;
    person->p_next_element = head;
    head = person;
    return person;
}
int main()
{
    int input;
    int age;
    Group* person;
    Group* head = NULL;
    while ( input != 1)
    {
        cout<<"How old is he/she? 20, 30, or 40?"<<endl;
        cin>> age;
        switch (age)
        {
            case 20: person = Get20Years (head); break;
            case 30: person = Get30Years (head);break;
            case 40: person = Get40Years (head);break;
        }
        cout << "What s his/her name?"<<endl;
        cin >> person->name;
        cout <<" Press 1 to see all the people set so far or any other number to keep adding"<<endl;
        cin >>input;
    }
    Group* p_current = head;
    while (p_current)
    {
        cout<<p_current->name<< " ";
        cout<<p_current->age<< " years old"<<endl;
        p_current = p_current->p_next_element; // From what i ve learnt in my book, this should be a way to make p_current
                                              // point to the previous element
    }
}

This is what I ve written so far, but wwhen I run it and I press 1 the program quits itself. Any help?
p.s. I m a very beginner and this is the knowledge I ve got so far... I know that probably many of you would have done it differently.
p.s.s. sorry if I said anything wrong.... my English may not be perfect as well

[MikeyBoy]

You are passing head into your functions by value. This means that, when you change the value of head inside the function, you're changing a local copy of it; the value of head in the calling code (i.e. the main() function) doesn't change.

This means that, in main(), head stays set to NULL, which means your while loop doesn't perform any iterations.

You need to pass head into those functions by reference.

[icy1]

make a class like GroupManager that handles Group stuff -- creation/deletion etc. Most importantly, it has its own head_ and (and possibly tail_) private variables, so that a caller of this class shouldnt have to pass a pointer to some node every time he wants to InsertFront (what you're trying to do...?) or Append to the back. The "Get" series of methods are misnamed here because they dont just retrieve but also create new things.

Should abstract the age as another parameter.

head = person; looks like an error in your methods

Remove all the cin stuff and practice with some data until it works.

[gdz98]

are you telling me that I should write like this?:

 switch (age)
        {
            case 20: person = Get20Years (&head); break;
            case 30: person = Get30Years (&head);break;
            case 40: person = Get40Years (&head);break;
        }

because it doesn t even compile if I do so. It tells me: error: cannot convert 'Group' to 'Group*' for argument 1 to 'Group* Ger20Years (Group*)'
… Sorry if I didn t get you but I may not have clear thought...

[gdz98]

hi icy1.
Ok I got what you mean and actually it d also make my life easier, but how do I create a class with its own head that update itself every time the callee is repeted?

And furthermore my book hasn t explained me how to create a tail yet, but it also told me that I should use it for this exercise…. so I don't really know what to do :/

[MikeyBoy]

are you telling me that I should write like this?:

OK, you need to understand that a Group* is a different type to a Group** (i.e. a pointer to a Group*). You can't just pass a pointer of the wrong type into your function, and hope it magically works. You'll need to redefine your functions to take the correct type of pointer.

Alternatively, you can use a reference to a Group*, which will make the syntax a little more straightforward. Again, you'll need to redefine the function to take the reference as an argument.

[gdz98]

OK, you need to understand that a Group* is a different type to a Group**

Yeah but both my pointer "head" and my class "Get20Years" are of type *Group … sorry but I m really confused, could you give me an example of what I should change? So maybe get what you mean properly

[MikeyBoy]

Yeah but both my pointer "head" and my class "Get20Years" are of type *Group

Yes. And it's the value of the Group* that you want to change. Which means you need to pass a pointer to a Group*, or a Group**. And that's not the same thing as a Group*.

(Or, you can pass a reference to a Group*, i.e. a Group*& - see https://www.cprogramming.com/tutorial/references.html if you're not familiar with references.)

[icy1]

I had something very similar already lying around, so it wasn't too much trouble to tweak it to fit this. The inserting to front logic is similar to what you had; not sure why it initially seemed off to me.

#include <iostream>
#include <string>
#include <sstream>
#include <vector>

using namespace std;

struct Person
{
    Person(string name, int age) : name(name), age(age)
    {        
    }

    string Stringify()
    {
        ostringstream oss;
        oss << name << "(" << age << ")";        
        return oss.str();
    }

    string Verbose()
    {
        ostringstream oss;
        oss << "[" << Stringify() << " ";
        if (prev)
            oss << "prev:"<<prev->Stringify() << " ";
        if (next)
            oss << "next:"<<next->Stringify();
        oss << "] ";
        return oss.str();
    }   

    string name;
    int age;
    Person* prev;
    Person* next;
};

class PersonManager
{
public:
    PersonManager() : size_(0)
    {
    }

    // Deallocate memory
    ~PersonManager()
    {
        CleanUp();
    }

    // Add as a new head
    //TODO: possibly check for unique names (same for Append)
    void InsertFront(string name, int age)
    {
        Person* p = new Person(name, age);
        if (!head_)
        {
            head_ = p;
            tail_ = p;
        }
        else
        {
            head_->prev = p;
            p->next = head_;
            head_ = p;
        }
        size_ += 1;
    }
    
    // Appends to the back
    void Append(string name, int age)
    {
        Person* p = new Person(name, age);
        if (!head_)
        {
            head_ = p;
            tail_ = p;
        }
        else
        {
            tail_->next = p;
            p->prev = tail_;
            tail_ = p;
        }
        size_ += 1;
    }
    
    size_t Size()
    {
        return size_;
    }

    void Show(bool verbose=false)
    {
        if (!head_)
        {
            cout << "List is empty.\n";
        }
        else
        {
            Person* p = head_;
            while(p)
            {
                if (verbose)
                    cout << p->Verbose() << endl;
                else
                    cout << p->Stringify() << endl;
                p = p->next;
            }
            cout << endl;
        }
    }
    
    // Delete all nodes
    void CleanUp()
    {
        Person* p = head_;
        Person* tmp;
        while(p)
        {
            tmp = p->next;
            delete p; 
            p = tmp;
        }
        head_ = nullptr;
        tail_ = nullptr;
        size_ = 0;
    }
    
private:
    Person* head_;
    Person* tail_;
    size_t size_;
};

int main() 
{
    PersonManager pm;

    vector<pair<string,int>> people = 
    {
        { "John Doe", 30 },
        { "Loren Zimmerman", 55 },
        { "Rodney Vega", 43 },
        { "Raquel Cannon", 15 },
        { "Lynette Bush", 10 },
        { "Perry Carr", 37 },
        { "Judy Richardson", 45 },
        { "Juanita Andrews", 31 },
        { "Olive Shelton", 57 },
        { "Ervin Warren", 29 },
        { "Jana Bradley", 13 },
        { "Jane Doe", 28 }
    };
    
    // First half appended to back
    for (int i=0; i<=people.size()/2 - 1; ++i)
        pm.Append(people[i].first, people[i].second);

    // Second half inserted to the front
    for (int i=people.size()/2; i<people.size(); ++i)
        pm.InsertFront(people[i].first, people[i].second);
    
    cout << "List of size " << pm.Size() << endl;
    pm.Show();

    return 0;
}

Runnable at https://repl.it/@icy_1/MenacingVastBraces

List of size 12
Jane Doe(28)
Jana Bradley(13)
Ervin Warren(29)
Olive Shelton(57)
Juanita Andrews(31)
Judy Richardson(45)
John Doe(30)
Loren Zimmerman(55)
Rodney Vega(43)
Raquel Cannon(15)
Lynette Bush(10)
Perry Carr(37)

Verbose view, if instead you'd call pm.Show(true) :

List of size 12
[Jane Doe(28) next:Jana Bradley(13)] 
[Jana Bradley(13) prev:Jane Doe(28) next:Ervin Warren(29)] 
[Ervin Warren(29) prev:Jana Bradley(13) next:Olive Shelton(57)] 
[Olive Shelton(57) prev:Ervin Warren(29) next:Juanita Andrews(31)] 
[Juanita Andrews(31) prev:Olive Shelton(57) next:Judy Richardson(45)] 
[Judy Richardson(45) prev:Juanita Andrews(31) next:John Doe(30)] 
[John Doe(30) prev:Judy Richardson(45) next:Loren Zimmerman(55)] 
[Loren Zimmerman(55) prev:John Doe(30) next:Rodney Vega(43)] 
[Rodney Vega(43) prev:Loren Zimmerman(55) next:Raquel Cannon(15)] 
[Raquel Cannon(15) prev:Rodney Vega(43) next:Lynette Bush(10)] 
[Lynette Bush(10) prev:Raquel Cannon(15) next:Perry Carr(37)] 
[Perry Carr(37) prev:Lynette Bush(10) ] 

[gdz98]

I ve tried to change approach (cause that approach was not right, and sooner or later I would hav found many other problems) as well as I reviewed a few things about pointers which I didn t get very well, now my code looks like this:

#include <iostream>
#include <string>

using namespace std;

struct Group
{
   int age;
   string name;
   Group* next_element;
};

Group* GetNewElement (int years, string name, Group* head)
{
    Group* person = new Group;
    person->age = years;
    person->name = name;
    person ->next_element = head;
    return person;
}


int main ()
{
    int years;
    string name;
    int input;
    Group* person;
    Group*  head = NULL;
    while (input != 1)
    {
       cout<< "Enter a person's name"<<endl;
       cin>>name;
       cout<< "Enter his/her age "<<endl;
       cin>>years;
       person, head = GetNewElement (years, name, head);
       cout << " Press 1 if you want to show the list of the people set so far, otherwise press any other number to keep adding people"<<endl;
       cin>>input;
    }
    Group* p_current = head;
    Group* p_prev = NULL;
    while (p_current != NULL)
    {
        cout<<p_current->name<<" "<<p_current->age<<" years old"<<endl;
        p_current= p_current->next_element;//now the problem s here
    }
}

now when it should print out the list it prints an infinite loop made up of only the last person who has been set

[gdz98]

As if I said nothing guys :D I eventually managed to do it and now it works as I expected... this is my code:

#include <iostream>
#include <string>

using namespace std;

struct Group
{
   int age;
   string name;
   Group* next_element;
};

Group* GetNewElement (int years, string name, Group* head)
{
    Group* person = new Group;
    person->age = years;
    person->name = name;
    person ->next_element = head;
    return person;
}

void List (Group* person)
{
    cout<<person->name<<" ";
    cout<<person->age<<" years old"<<endl;
}

void Deleting (string value, Group*  head)
{
   Group* p_current = NULL;
   Group* p_prev = NULL;
   for (p_current = head; p_current != NULL; p_prev = p_current, p_current = p_current->next_element)
    {
      if (p_current->name == value)
      {
          if (p_prev==NULL)
            head=p_current->next_element;
          else
            p_prev->next_element = p_current->next_element;
      }
    }
}


int main ()
{
    int years;
    string name;
    int input;
    Group* person;
    Group*  head = NULL;
    string Delete;
    while (input != 1)
    {
       cout<< "Enter a person's name"<<endl;
       cin>>name;
       cout<< "Enter his/her age "<<endl;
       cin>>years;
       person, head = GetNewElement (years, name, head);
       cout << " Press 1 if you want to show the list of the people set so far, otherwise press any other number to keep adding people"<<endl;
       cin>>input;
    }
    Group* p_current = head;
    Group* p_prev = NULL;
    while (p_current != NULL)
    {
        List(p_current);
        p_current=p_current->next_element;
    }
    cout<<"Select the one you want to delete from the list by his name"<<endl;
    cin >> Delete;
    Deleting (Delete, head);
    cout<<"This is your final list: "<<endl;
    p_current=head;
    while (p_current != NULL)
    {
        List(p_current);
        p_current=p_current->next_element;
    }

}

Could you only suggest me where I should deallocate all the memory I ve used?

[MikeyBoy]

As if I said nothing guys :D

*Shrug* people have lives - jobs, families, holidays, social lives. Sometimes, no-one's going to be around to answer your questions, and that's just life.

So, you've reworked your code for creating new elements, to avoid having to think about changing the value of head within the funtion. But you still have the same problem with Deleting() - you modify head within the function, but the head pointer in main() does not change.

As for freeing memory, it would make sense to do that in your Deleting() function.

[dhayden]

First, you still have a couple of bugs:
Line 53: the first time through the loop, input is uninitialized. Initialize it to something other than 1 at line 49. You might also consider changing your while loop to a do/while loop since that better expresses what you're doing:

do {
    ...
} while (input != 1);

Line 59: remove person, . This code has no effect. The comma operator is somewhat like a semicolon: it separates expressions that are evaluated sequentially. Thus, line 59, is like:

person;   // Evaluate person and throw away the result. In other words, do nothing.
head = GetNewElement (years, name, head);  // add the new element. 

As for freeing the memory, ask yourself "who owns the memory?" In other words, who has the most important pointer? Who has a pointer that, if changed, would cause the memory to leak?

For the linked list, each node contains the pointer to the next node. So it makes sense that when you delete one node, you should delete the node after it.

struct Group
{
    ~Group {
        delete next_element;
    }
    ...
};

This is defining a destructor, which you might not have learned about. You may wonder why I don't check for a NULL pointer in next_element. Delete will do that for you: it's legal to call delete on a null pointer.

Now all that's left is to delete the first element. You can do that at line 80:
delete head;

There's one other source of leaked memory: Deleting() unlinks an item but doesn't delete it. After line 39 add:

p_current->next_element = NULL;   // So we don't delete the items after p_current
delete p_current;             // delete it 

But this actually introduces another bug! The for loop keeps running, and now it accesses p_current, which is no longer valid. Now worries, we can fix that by simply returning after immediately after deleting p_current:

p_current->next_element = NULL;   // So we don't delete the items after p_current
delete p_current;             // delete it
return;

[gdz98]

Ok thanks a lot now I think my ideas are clearer. Anyway doing the Deleting () how you suggested me to do made come out an error.... indeed if I tried to delete the first element of the list (the "head") when the list was subsequently reprinted it was nothing but just random numbers. so I thought that s because the deleting function is a void so it doesn t return the new value of head. So I changed my code like this:

#include <iostream>
#include <string>

using namespace std;

struct Group
{
   int age;
   string name;
   Group* next_element;
   delete
};

Group* GetNewElement (int years, string name, Group* head)
{
    Group* person = new Group;
    person->age = years;
    person->name = name;
    person ->next_element = head;
    return person;
}

void List (Group* person)
{
    cout<<person->name<<" ";
    cout<<person->age<<" years old"<<endl;
}

Group* Deleting (string value, Group*  head) // made the function Group*
{
   Group* p_current = NULL;
   Group* p_prev = NULL;
   for (p_current = head; p_current != NULL; p_prev = p_current, p_current = p_current->next_element)
    {
      if (p_current->name == value)
      {
          if (p_prev==NULL)
          {
            head=p_current->next_element;
          }
          else
          {
            p_prev->next_element = p_current->next_element;
          }
          p_current->next_element = NULL;
          delete p_current;
          return head;
      }
    }
}


int main ()
{
    int years;
    string name;
    int input = 0;
    Group* person;
    Group*  head = NULL;
    string Delete;
    while (input != 1)
    {
       cout<< "Enter a person's name"<<endl;
       cin>>name;
       cout<< "Enter his/her age "<<endl;
       cin>>years;
       head = GetNewElement (years, name, head);
       cout << " Press 1 if you want to show the list of the people set so far, otherwise press any other number to keep adding people"<<endl;
       cin>>input;
    }
    Group* p_current = head;
    Group* p_prev = NULL;
    while (p_current != NULL)
    {
        List(p_current);
        p_current=p_current->next_element;
    }
    cout<<"Select the one you want to delete from the list by his name"<<endl;
    cin >> Delete;
    head = Deleting (Delete, head);//Keeping head updated
    cout<<endl<<"This is your final list: "<<endl;
    p_current=head;
    while (p_current != NULL)
    {
        List(p_current);
        p_current=p_current->next_element;
    }
    delete head;

}

Now it seems to work all the times and in any situation.
As regard this:

For the linked list, each node contains the pointer to the next node. So it makes sense that when you delete one node, you should delete the node after it.

I didn t get it.... should I delete the next_element pointer in the structure like this?:

struct Group
{
   int age;
   string name;
   Group* next_element;
   delete next_element;
};

If I do in this way isn't it like not having a next_element pointer at all?

[dhayden]

There's still a path in Deleting() that doesn't return a value. Try changing it to:

Group* Deleting (string value, Group*  head) // made the function Group*
{
   Group* p_current = NULL;
   Group* p_prev = NULL;
   for (p_current = head; p_current != NULL; p_prev = p_current, p_current = p_current->next_element)
    {
      if (p_current->name == value)
      {
          if (p_prev==NULL)
          {
            head=p_current->next_element;
          }
          else
          {
            p_prev->next_element = p_current->next_element;
          }
          p_current->next_element = NULL;
          delete p_current;
          break;
      }
    }
    return head;
}

[icy1]

Just seems like too much burden on main() to have it manage four raw pointers... if you delete the wrong one or pass the wrong one in to a function, you could forever lose the head of the list.

[gdz98]

ok guys thanks everybody for your time and help.... now I ve finally made it :D