Question

**HELP**

Write a function that takes a linked list of items and deletes all repetitions from the list. In your implementation, assume that items can be compared for equality using ==, that you used in the lab.

The prototype may look like:

void delete_repetitions(LinkedList& list);

** Node.h **

#ifndef Node_h

#define Node_h

class Node

{

public:

// TYPEDEF

typedef double value_type;

// CONSTRUCTOR

Node(const value_type& init_data = value_type( ), Node* init_link = NULL)

{ data_field = init_data; link_field = init_link; }

// Member functions to set the data and link fields:

void set_data(const value_type& new_data) { data_field = new_data; }

void set_link(Node* new_link) { link_field = new_link; }

// Constant member function to retrieve the current data:

value_type data() const { return data_field; }

// Two slightly different member functions to retrieve the current link:

const Node* link() const { return link_field; } // returns pointer to a const type

Node* link() { return link_field; }

private:

value_type data_field;

Node* link_field;

};

#endif /* Node_h */

**LinkedList.h**

#ifndef LinkedList_h

#define LinkedList_h

#include "Node.h"

#include <iostream>

#include <cstdlib>

class LinkedList

{

public:

typedef Node::value_type data_type;

typedef size_t size_type;

LinkedList();

size_type list_length() const {return node_count;};

bool isEmpty() const;

void head_insert(const Node::value_type& value);

void list_insert(Node* prev_ptr, const Node::value_type& value);

Node* getHeadPtr() {return head_ptr;};

const Node* getHeadPtr() const {return getHeadPtr();};

Node* getTailPtr() {return tail_ptr;};

const Node* getTailPtr() const {return getTailPtr();};

Node* list_search(const Node::value_type& target);

const Node* list_search(const Node::value_type& target) const {return list_search(target);};

void clear_list();

void head_remove(Node* temp);

void list_remove(Node* prev_ptr);

~LinkedList();

LinkedList(const LinkedList & l);

void list_copy(const LinkedList& source_list, LinkedList& destination_list );

LinkedList( LinkedList & l);

bool operator == (LinkedList &a);

void operator=(LinkedList &a);

private:

Node *head_ptr;

Node *tail_ptr;

size_type node_count;

};

void display(Node* head);

#endif /* LinkedList_h */

**LinkedList.cpp**

#include <iostream>

#include <cstdlib>

#include "Node.h"

#include "LinkedList.h"

using namespace std;

LinkedList::LinkedList()

{

node_count = 0;

head_ptr = NULL;

tail_ptr = NULL;

}

//Inserts a node at the beginning of the list

void LinkedList::head_insert(const Node::value_type& value)

{

Node* newNode = new Node(value, head_ptr);

head_ptr = newNode;

if(tail_ptr == NULL)

{

tail_ptr = head_ptr;

}

node_count++;

}

//Inserts new node into list

void LinkedList::list_insert(Node* prev_ptr, const Node::value_type& value)

{

if(prev_ptr != NULL)

{

Node* newNode = new Node(value, prev_ptr->link());

if(prev_ptr->link() == NULL)

{

tail_ptr = newNode;

}

prev_ptr->set_link(newNode);

}

else if(head_ptr == NULL)

{

head_insert(value);

}

node_count++;

}

//Searches for a certain number in a node

Node* LinkedList::list_search(const Node::value_type& target)

{

Node *temp = head_ptr;

while(temp != NULL)

{

if(target == temp->data())

{

return temp->link();

}

temp = temp->link();

}

return NULL;

}

bool LinkedList::isEmpty() const

{

return (node_count == 0);

}

//displays final list

void display(Node* head)

{

while(head != NULL)

{

cout << head->data() << " ";

head = head->link();

}

cout << endl;

}

void LinkedList::list_copy(const LinkedList& source_list, LinkedList& destination_list )

{

   const Node *head_source = source_list.getHeadPtr();

Node *tail_dest = destination_list.getTailPtr();

while(head_source != NULL)

{

destination_list.list_insert(tail_dest,head_source->data());

head_source = head_source->link();

tail_dest = tail_dest->link();

}

}

void LinkedList::head_remove(Node* temp)

{

Node* temp2 = temp;

temp2 = head_ptr;

head_ptr = head_ptr -> link();

   // delete temp2;

}

void LinkedList::list_remove(Node* prev_ptr)

{

Node* temp = prev_ptr -> link();

//temp - > link();

prev_ptr -> set_link(temp -> link());

delete temp;

node_count--;

}

void LinkedList::clear_list()

{

Node* temp;

while (head_ptr != NULL)

{

head_remove(temp);

}

}

LinkedList::~LinkedList()

{

clear_list();

}

bool LinkedList::operator==( LinkedList &dest)

{

if(this->list_length() != dest.list_length() )

{

return false;

}

Node* a = this -> getHeadPtr();

Node* b = dest.getHeadPtr();

while( a != NULL)

{

if(a -> data() != b -> data() )

{

return false;

}

a = a ->link();

b = b ->link();

}

return true;

}

void LinkedList::operator= (LinkedList &dest)

{

if(dest.list_length() == 0)

return;

  

Node* b = dest.getHeadPtr();

this-> head_insert(b -> data());

b = b -> link();

while(b != NULL)

{

Node* a = this -> getTailPtr();

this -> list_insert(a,b->data());

b = b->link();

  

}

  

}

LinkedList::LinkedList( LinkedList &l)

{

head_ptr = NULL;

tail_ptr = NULL;

node_count = 0;

  

//creates a deep copy

*this=l;

  

}

Answer 1

LinkedList is assumed to be unsorted and to remove repetitions a set is used. To use set you have to include unordered_set using the following in the LinkedList.cpp:

#include <unordered_set>

Below is the code of the delete_repetitions method:

void delete_repetitions(LinkedList &list)

{

// Hash to store seen values

unordered_set<int> seen;

/* Pick elements one by one */

Node *curr = list.getHeadPtr();

Node *prev = NULL;

while (curr != NULL)

{

// If current value is seen before

if (seen.find(curr->data()) != seen.end())

{

prev->set_link(curr->link());

delete (curr);

}

else

{

seen.insert(curr->data());

prev = curr;

}

curr = prev->link();

}

}