CODEWITHSUNDEEP
c++singly-linked-list
Derked
Derked

Reputation: 994

c++ remove similar nodes linked list

For a homework assignment I need to remove all similar nodes that the number passed into. For example if I have on the list

3 5 5 4

the 5's will be removed from the linked list and I will end with

3 4

we are not allowed to use the std library for this class and here is the header file

    namespace list_1
{
    class list
    {
    public:
        // CONSTRUCTOR
        list( );
        // postcondition: all nodes in the list are destroyed.
        ~list();
        // MODIFICATION MEMBER FUNCTIONS
        //postcondition: entry is added to the front of the list
        void insert_front(const int& entry);
        //postcondition: entry is added to the back of the list
        void add_back(const int& entry);
        // postcondition: all nodes with data == entry are removed from the list
        void remove_all(const int& entry);
        // postcondition: an iterator is created pointing to the head of the list
        Iterator begin(void);

        // CONSTANT MEMBER FUNCTIONS
        // postcondition: the size of the list is returned
        int size( ) const;
    private:
        Node* head;
    };

}

I can understand how to remove the front, and the back of the list. But for some reason I can't wrap my head around going through the list and removing all of the number that is passed in. Anything helps! Thanks

edited to include Node.h

#pragma once

namespace list_1
{
    struct Node
    {
        int data;
        Node *next;

        // Constructor
        // Postcondition: 
        Node (int d);
    };
}

Upvotes: 1

Views: 699

Answers (1)

BinderNews
BinderNews

Reputation: 560

There are two ways of doing this. The first is to iterate through the list and remove the nodes. This is tricky because to do that you have to keep a pointer to the previous node so you can change its next value. The code for removing a node would look like this (assume current is the current node and prev is the previous node)

Node* next = current->next;
delete current;
prev->next = next;

Maintaining a reference to the previous node can be a bit tedious though, so here is another way to do it. In this method, you essentially create a new list but don't insert Nodes who's data is equal to entry.

The code might look a little like this

void list::remove_all(const int &entry)
{
    Node* newHead = NULL;
    Node* newTail = NULL;
    Node* current = head;

    // I'm assuming you end your list with NULL
    while(current != NULL)
    {
        // save the next node in case we have to change current->next
        Node* next = current->next;
        if (current->data == entry)
        {
            delete current;
        }
        else
        {
            // if there is no head, the set this node as the head
            if (newHead == NULL)
            {
                newHead = current;
                newTail = current;
                newTail->next = NULL; // this is why we saved next
            }
            else
            {
                // append current and update the tail
                newTail->next = current;
                newTail = current;
                newTail->next = NULL; // also why we saved next
            }
        }
        current = next; // move to the next node
    }
    head = newHead; // set head to the new head
}

Note: I didn't test this, I just typed it up off the top of my head. Make sure it works. =)

Hope this helps! ;)

Upvotes: 2

Related Questions