Removing duplicates from a DoublyLinkedList

Question

I'm trying to remove duplicate items in C++. I've managed to get the object to = null by using the objects default constructor. But I am unable to completely remove it from the list. This code also deletes the two objects rather than just one. This is a re-post from another question. My code and partially my post has changed.How to remove duplicates from a doubly linked list by full name. Can anyone help me with this? Here is my removeDuplicates function:

***Remove Duplicates***
    void RemoveDuplicates(DoublyLinkedListIterator<Datatype> m_itr, string searchByFirstName, string searchBySecondName)
    {
        for (m_itr.Start(); m_itr.Valid(); m_itr.Forth())
            {
                if ((m_itr.Item().getFirstName() == searchByFirstName )
                          && (m_itr.Item().getSecondName() == searchBySecondName))
                {
                    for (m_itr.Item(); m_itr.Valid(); m_itr.Forth())
                    {
                        if ((m_itr.Item().getFirstName() == searchByFirstName )&&
                            (m_itr.Item().getSecondName() == searchBySecondName))
                                {
                                    m_itr.Item() = Stats();
                                }
                    }
                }
            }
        delete m_itr.Item();
    }
***Remove***
    void Remove(DoublyLinkedListIterator<Datatype> m_itr)
        {
            query.clock1();
            DoublyLinkedListNode<Datatype>* node = m_head;
            //Check to see if the iterator belongs to this list, if not return nothing.
            if (m_itr.m_list != this)
                return;
            //Check to see if the node is valid, if not return nothing.
            if (m_itr.m_node == 0)
                return;
            //If the iterator is pointing to the head...
            if (m_itr.m_node == m_head)
            {
                //Move the iterator forward.
                m_itr.Forth();
                //Delete the head.
                RemoveHead();
                //Decrement the size.
                m_count--;
            }
            //If the iterator is not pointing to the head...
            else
            {
                //Search forward through the list until you find
                //the node prior to the node you want to remove.
                while (node->m_next != m_itr.m_node)
                node = node->m_next;
                // move the iterator forward.
                m_itr.Forth();
                //If the node being are deleted is the tail...
                //Then update the tail node.
                if (node->m_next == m_tail)
                {
                    //Tail is now equal to node.  Which means we can now delete the node.
                    m_tail = node;
                }
                //Delete the node.
                delete node -> m_next;
                //Relink the list.
                node -> m_next = m_itr.m_node;
                //Decrement the count because a node was removed.
                m_count--;
                query.clock2();
                cout << "\nTime Taken : " << query.time2 - query.time1 << "\n";
            }
        }

***Class Declarations***
template <class Datatype>
class DoublyLinkedList
{   
public:
//-------------------------------------------------------------------------------------------
//  Member Vairables.
//-------------------------------------------------------------------------------------------
DoublyLinkedListNode<Datatype>* m_head;
DoublyLinkedListNode<Datatype>* m_tail;
int m_count;

template<class Datatype>
class DoublyLinkedListNode
{
public:
//-------------------------------------------------------------------------------------------
//  Member Vairables.
//-------------------------------------------------------------------------------------------
    DoublyLinkedListNode<Datatype>* m_next; //The next node.
    DoublyLinkedListNode<Datatype>* m_prev; //The previous node.
    Datatype m_data;                        //The data in the node.

template <class Datatype>
class DoublyLinkedListIterator
{
public:
//-------------------------------------------------------------------------------------------
//  Member Vairables.
//-------------------------------------------------------------------------------------------
    DoublyLinkedListNode<Datatype>* m_node; //A node for the Iterator to pointn to.
    DoublyLinkedList<Datatype>* m_list;     //A list for the Iteraotor to go through.
//-------------------------------------------------------------------------------------------
//  Name:           Constructor.
//  Description:    Constructs the DoublyLinkedListIterator.
//-------------------------------------------------------------------------------------------
    DoublyLinkedListIterator(DoublyLinkedList<Datatype>* p_list= 0, DoublyLinkedListNode<Datatype>* p_node= 0)
    {
        m_list= p_list;
        m_node= p_node;
    }

// ------------------------------------------------------------------
//  Name:           Start
//  Description:    Resets the iterator to the beginning of the list.
//  Arguments:      None.
//  Return Value:   None.
// ------------------------------------------------------------------
    void Start()
    {
        if(m_list!= 0)
        m_node= m_list -> m_head;
    }

// ----------------------------------------------------------------
//  Name:           End
//  Description:    Resets the iterator to the end of the list.
//  Arguments:      None.
//  Return Value:   None.
// ----------------------------------------------------------------
    void End()
    {
        if(m_list!= 0)
        m_node = m_list->m_tail;
    }

// ----------------------------------------------------------------
//  Name:           Forth
//  Description:    Moves the iterator forward by one position.
//  Arguments:      None.
//  Return Value:   None.
// ----------------------------------------------------------------
    void Forth()
    {
        if(m_node != 0)
        {
        m_node = m_node ->m_next;
        }
    }

// ----------------------------------------------------------------
//  Name:           Back
//  Description:    Moves the iterator back by one position.
//  Arguments:      None.
//  Return Value:   None.
// ----------------------------------------------------------------
    void Back()
    {
        if(m_node!= 0)
        m_node = m_node->m_prev;
    }


// ----------------------------------------------------------------
//  Name:           Item
//  Description:    Gets the item that the iterator is pointing to.
//  Arguments:      None.
//  Return Value:   Reference to the data in the node.
// ----------------------------------------------------------------
    Datatype& Item()
    {
        return m_node->m_data;
    }
//-----------------------------------------------------------------
//  Name:           Valid
//  Description:    Determines if the node is valid.
//  Arguments:      None.
//  Return Value:   true if valid.
// ----------------------------------------------------------------
    bool Valid()
    {
        return (m_node!= 0);
    }
};

You already have this question up - no need for another. stackoverflow.com/questions/16124663/… — Victor Sand
– Victor Sand, Commented Apr 20, 2013 at 23:11
Im not deleting a local variable anymore and in fairness. My code is different and so is the post Hey im trying to remove duplicate items in c++. Ive managed to get the object to = null by using the objects default constructor. But i am unable to completely remove it from the list. This code also deletes the two objects rather than just one. — Becca
– Becca, Commented Apr 20, 2013 at 23:13
What you need to do is use built-in functions in the DoublyLinkedList to delete it. What do the DoublyLinkedList functions look like? — Victor Sand
– Victor Sand, Commented Apr 20, 2013 at 23:15
@Becca: It's fine to recast a question in a new form, but you should explain that it's a variant of a previous question and what's different about it. (I.e., your comment in answer to Victor Sand should have been part of the question.) — Marcelo Cantos
– Marcelo Cantos, Commented Apr 20, 2013 at 23:16
Remove Head,Tail, Remove(which only takes an itr). Thats all the delete functions i have. — Becca
– Becca, Commented Apr 20, 2013 at 23:17

Victor Sand · Accepted Answer · 2013-04-21 00:28:09Z

2

Use the DoublyLinkedList's built-in Remove function and pass it the iterator. The delete call is the bare bones C++ variant which doesn't deal with the deletion of nodes and re-linking the list properly. The call to delete only removes what's in the node, not the node itself!

Remove(m_itr);

Instead of

delete m_itr.Item();

Also, I think the place of your deletion might be off (you will always delete the last item, it seems). Maybe you want to do something like below. Not sure what Stats() does, but hopefully you'll get the idea. Basically you need to put away the item to delete, step forward the regular iterator and then remove the one you put away. Alternatively, stop the iteration completely once removal is complete. This is needed because when the iterator gets removed, it can't be used for further iterating.

    if ((m_itr.Item().getFirstName() == searchByFirstName ) &&
        (m_itr.Item().getSecondName() == searchBySecondName))
    {
      DoublyLinkedListIterator<Datatype> toDelete = m_itr; 
      m_itr.Forth(); 
      Remove(toDelete);
    }

edited Apr 21, 2013 at 0:28

answered Apr 20, 2013 at 23:17

Victor Sand

2,3601 gold badge17 silver badges33 bronze badges

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

6 Comments

Becca Over a year ago

I tried this. But to my amazement it doesn't delete it. ill post the remove function if you wish.

Victor Sand Over a year ago

Please do! Maybe it doesn't do what we think it does.

Becca Over a year ago

I get a run-time error when i do this. i think because im literally deleting the iterator. The Stats is basically setting it to the default constructor. So the player would be null. NExt best thing to deleting haha.

Victor Sand Over a year ago

Yeah, I missed that the first time around. You have to "save" the iterator. See edit!

Becca Over a year ago

Brilliant it worked :) I am delighted. I did try and save the itr before but i done it stupidly. Thank you so much :)

|

user2303289 · Accepted Answer · 2013-04-20 23:33:49Z

2

The inner for loop isn't doing anything for you: It's just continuing the iteration started by the outer loop.

There's a lot of issues here, I am guessing you're learning and I applaud your efforts: Good for you for reaching out.

void RemoveDuplicates(DoublyLinkedListIterator<Datatype> m_itr, string searchByFirstName, string searchBySecondName)
{
    for (m_itr.Start(); m_itr.Valid(); m_itr.Forth())
        {
            if ((m_itr.Item().getFirstName() == searchByFirstName )&& (m_itr.Item().getSecondName() == searchBySecondName))
            {
                    if ((m_itr.Item().getFirstName() == searchByFirstName )&&
                        (m_itr.Item().getSecondName() == searchBySecondName))
                            {
                                m_itr.Item() = Stats();
                            }
                }
        }
    delete m_itr.Item();
}

The assigning of the item to stats also probably isn't what you want: You want to delete the item, and then remove that entry from the list. I'd need to see the api for the iterator and doubly linked list, but you need to both delete the item, AND remove it from the list, probably involving something like this:

              m_itr.Item().m_prev.m_next = m_itr.Item().m_next;
              if (m_itr.Item().m_next != null)
                m_itr.Item().m_next.m_prev = m_itr.Item().m_prev;
              // now that the item is spliced out of the list, delete it.

Hope this helps.

answered Apr 20, 2013 at 23:33

user2303289

211 bronze badge

1 Comment

Becca Over a year ago

Thanks i appreciate that. Unfortunately i cant reach m_next because its in the node class so it just says m_next and m_prev is undefined. I added in code in there are the functions i have in the iterator class.

Marcelo Cantos · Accepted Answer · 2013-04-20 23:40:41Z

1

I don't know anything about the library you're using, but in the standard library, deleting as you go goes something like this:

for (auto i = begin(list); i != end(list);) {
    if (dont_want(*i)) {
        i = list.erase(i);
    } else {
        ++i;
    }
}

The basic idea is that, inside the loop, either you are erasing the current node, and it is up to list.erase(…) to inform you which node to continue iterating from after it has erased the current node, or you are keeping the node, in which case you move past it by simply incrementing the iterator.

In your code, the equivalent of ++i is m_itr.Forth(), and list.erase(…) is Remove(…). However, since Remove() doesn't return any information about how to keep progressing through the list, you get stuck; you can't call m_itr.Forth() because the node it points to no longer exists.

I don't know that I can help you much further, since I'm struggling to understand how your code works. The expression m_itr.Item().getFirstName() implies that m_itr.Item() is a reference to an object, whereas delete m_itr.Item() means that it must be a pointer, not a reference.

Note that the above code conforms to C++11. The C++03 equivalent is:

for (std::list<Datatype>::iterator i = list.begin(); i != list.end();) { … }

edited Apr 20, 2013 at 23:40

answered Apr 20, 2013 at 23:22

Marcelo Cantos

187k40 gold badges338 silver badges366 bronze badges

2 Comments

Becca Over a year ago

Ive never seen this before. Does it loop through the list the same as the iterator and im doing this in the header file so i will have to pass in m_list rather than the actual list defined in the main.

Becca Over a year ago

Basically i have 3 classes, DLLList, DLNode and DLLIterator. Item is a fucntion from the iterator class to get the nodes data. So using this i can say m_itr.Item().getFirstName() to get the obj's first name and so on.

Collectives™ on Stack Overflow

Removing duplicates from a DoublyLinkedList

3 Answers 3

6 Comments

1 Comment

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

6 Comments

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related