I am tasked with removing all duplicate entries in the linked list. Assuming the list is ordered from smallest to largest, therefore all I need to do is remove the duplicates next to each other.
For example: If the list contains {1,2,2,2,3,3,4,5,5,5,5,5,6} before calling remove_duplicates(), it should contain{1,2,3,4,5,6} after.
My problem is that my code will print the duplicates as well whenever remove_duplicates() is called.
Here is my code:
list.cpp:
#include <iostream>
using namespace std;
#include "list.h"
// on some machines member variables are not automatically initialized to 0
List::List()
{
m_head = NULL;
m_length = 0;
}
// delete all Nodes in the list
// since they are dynamically allocated using new, they won't go away
// automatically when the list is deleted
// Rule of thumb: destructor deletes all memory created by member functions
List::~List()
{
while (m_head)
{
Node *tmp = m_head;
m_head = m_head->m_next;
delete tmp;
}
}
// always insert at the front of the list
// Note: this works even in the SPECIAL CASE that the list is empty
void List::insert(int value)
{
if (!m_head || value < m_head->m_value)
{
m_head = new Node(value, m_head);
}
else
{
Node *ptr = m_head;
while (ptr->m_next != NULL && value > ptr->m_next->m_value)
{
ptr = ptr->m_next;
}
ptr->m_next = new Node(value, ptr->m_next);
}
m_length++;
}
// iterate through all the Nodes in the list and print each Node
void List::print()
{
for (Node *ptr = m_head; ptr; ptr = ptr->m_next)
{
cout << ptr->m_value << endl;
}
}
void List::remove_duplicates()
{
Node *curr = m_head;
Node *temp = m_head;
Node *delPtr = NULL;
if(curr == NULL)
{
return;
}
if(curr != NULL)
{
if(curr -> m_value == curr ->m_next ->m_value)
{
delPtr = curr;
curr = curr -> m_next;
temp ->m_next = curr;
delete delPtr;
}
else
{
curr = curr -> m_next;
}
}
}
list.h:
class List
{
public:
List();
~List();
void insert(int value); // insert at beginning of list
void print(); // print all values in the list
int length() {return m_length;}
void remove_duplicates();
int *convert_to_array(int &size);
private:
class Node
{
public:
Node(int value, Node *next)
{m_value = value; m_next = next;}
int m_value;
Node *m_next;
};
Node *m_head;
int m_length;
};
main.cpp:
#include <assert.h>
#include <iostream>
using namespace std;
#include "list.h"
int main()
{
List list;
int value;
// read values and insert them into list
while (cin >> value)
{
list.insert(value);
}
cout << "printing original list: \n";
list.print();
list.remove_duplicates();
cout << "printing list after removing duplicates: \n";
list.print();
}
Note: Everything has been given to me by my instructor, the only code that I am supposed to write is void List::remove_duplicates()
I have looked up other examples on stackoverflow, but none seem to help me with my situation. Also, I do want to mention that I am still very new to Linked Lists and how they function. Therefore I am not exactly sure where to go from here. Any help would be appreciated
std::vector). How would you remove the duplicates in a loop? Assume you have two indices (just like you have two links, curr and curr->next). Also assume there is an "erase" function that erases the item at a certain index. What logic would be involved in making sure that the indices don't get messed up, or you don't miss any duplicates? Whatever that logic is, it is the same logic for a linked list, only that you are dealing with curr and curr->next, instead of indexiandi+1.