RemoveDuplicate in DoublyLinkedList

[pendo826]

Hey my doubly linked list remove duplictes function will only work when the players in the list are together as in position 1 and 2 or 3 and 4. Otherwise if there not together it will delete the two players. For example, if i have luis suarez at position 1 and have him again at position 3, both luis suarez objects will be deleted when only one is supposed to be removed hence remove duplicate. Here is my code:

void RemoveDuplicates(DoublyLinkedListIterator<Datatype> m_itr, string searchByFirstName, string searchBySecondName)
{
    query.clock1();
    for(m_itr.Start(); m_itr.Valid(); m_itr.Forth())
        {
            if ((m_itr.Item().getFirstName() == searchByFirstName )&& (m_itr.Item().getSecondName() == searchBySecondName))
            {
                //This part was helped by Stack Overflow.
                DoublyLinkedListIterator<Datatype> toDelete = m_itr; 
                m_itr.Forth(); 
                Remove(toDelete);
            }   
            //break;
        }
    query.clock2();
    cout << "\nTime Taken : " << query.time2 - query.time1 << "\n";
}

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

My program has 3 classes DLLMode, DLLList and DLLIterator. The remove function is in the DoublyLinkedList.h.

Any help is much appreciated

[Ancient Dragon]

In function RemoveDuplicates(), first find the first instance of the two search strings. Only after that one is found do you want to start removing all other instances. That means you will have two loops in the function, not just one.

[Liuqahs15]

I didn't read all of the code, but I read your loop. The problem you're having makes perfect sense if you think about it from an objective standpoint:

for(m_itr.Start(); m_itr.Valid(); m_itr.Forth())

Look at the above for-loop declaration. It checks if m_itr.Valid() == true, which means it's going to keep cycling through the linked list even if you've found and removed the "player" you wanted to get rid of. Remember that. Your code should be more like:

bool playerWasFound = false;
for(m_itr.Start(); m_itr.Valid() && !playerWasFound; m_itr.Forth())

Next, look at the stuff going on in your if statement:

if ((m_itr.Item().getFirstName() == searchByFirstName )&& (m_itr.Item().getSecondName() == searchBySecondName))
{
    //This part was helped by Stack Overflow.
    DoublyLinkedListIterator<Datatype> toDelete = m_itr;
    m_itr.Forth();
    Remove(toDelete);
} 

First, you create a pointer to the "player" that you've found. Good. But then you call m_itr.Forth(). This means you've moved ahead in the list. Imagine it like this:

Node 1: Luis
Node 2: John
Node 3: Luis

If you're looking for Luis, what happens according to your code?

1. You find Luis at Node 1.
2. You create a pointer to him.
3. You call Forth(), which moves m_itr to Node 2, which is John.
4. You Remove() Luis.
5. You go through another cycle in the loop, which calls Forth() and moves m_irt to Node 3, which points to Luis.
6. You go back to step 1, finding Luis at Node 3.

When it's designed that way, it won't ever check Node 2 because you iterate to it before the loop can finish. In fact, the node directly after the node you're looking for is never checked.

Here's the fix:

bool playerWasFound = false;
m_itr.Start();
while(m_itr.Valid() && !playerWasFound)
{
    if ((m_itr.Item().getFirstName() == searchByFirstName )&& (m_itr.Item().getSecondName() == searchBySecondName))
    {
        Remove(m_itr);
        playerWasFound = true;
    }
    m_itr.Forth();
}

Just call m_itr.Forth() at the end of a while() loop. You do this because the for-loop will check the condition before it calls m_itr.Forth(), which can cause problems. So just call m_itr.Forth() yourself before the loop ends. That should definitely work. Let me know if you're confused.

[Ancient Dragon]

I think you missed the point -- there may be multiple nodes that have the same data strings, so the loop needs to run though the entire list in order to find and remove them all except the first one found.

[Liuqahs15]

Ah, I see. Well in that case, it should be like this:

    m_itr.Start();
    while(m_itr.Valid())
    {
        if ((m_itr.Item().getFirstName() == searchByFirstName )&& (m_itr.Item().getSecondName() == searchBySecondName))
        {
            Remove(m_itr);
        }
        m_itr.Forth();
    }

You still only want to be calling m_itr.Forth() only once per loop. In your current code, you call it twice sometimes, which makes you skip a node.

[Liuqahs15]

Sorry, I just realized I'm missing a key part in that solution:

 m_itr.Start();
 DoublyLinkedListIterator<Datatype> toDelete = NULL;
  while(m_itr.Valid())
  {
    if ((m_itr.Item().getFirstName() == searchByFirstName )&& (m_itr.Item().getSecondName() == searchBySecondName))
    {
    toDelete = m_itr;
    }

       m_itr.Forth();

    if(toDelete)
    {
       Remove(toDelete);
       toDelete = NULL;
    }
  }

That'll work. My previous answer will cause a runtime error because you'll try to call m_itr.Forth() after deleting m_itr.