Write this function given the template for linked lists in C++ with the given re

Question

Write this function given the template for linked lists in C++ with the given requirements:

Given implementation of Linked list that can be helpful for writing function:

IMPLEMENTATION: template class List private: // struct for singly-linked list nodes struct Node T data: Node next; Node (const T &dTI, Node *n - nullptr) :datad, nextin /Data members of List class: a front and back pointer Node front; Node *back; QUESTION: Function: linked list remove occurence Description: removes all occurrences of x (if any) in given list (calling object) returns number of matches found/deleted Relative order of undeleted elementsis unchanged. Requirements: O() Worst case runtime Function Template (Cannot change paremeters) int fast remove all (const T &x) return 0

Explanation / Answer

Solution:

Singly linked list template implementation:

#include <iostream>
using namespace std;

template <class T>
struct node {
node(T data) : data(data), next(NULL) {}
T data;
node<T> *next;
};

template <class T>
class linkedlist {
template<class U>
friend ostream &operator<<(ostream &os, const linkedlist<U> &rhs);
private:
node<T> *head;
public:
linkedlist() : head(NULL) {};
~linkedlist();
linkedlist(const linkedlist &rhs);
linkedlist &operator=(const linkedlist &rhs);
void insert(const T data);
bool search(const T data) const;
void remove(const T data);
bool isEmpty() const;
bool operator==(const linkedlist<T> &rhs) const;
bool operator!=(const linkedlist<T> &rhs) const;
bool operator<(const linkedlist<T> &rhs) const;
bool operator>(const linkedlist<T> &rhs) const;
};

template <class T>
bool linkedlist<T>::operator!=(const linkedlist<T> &rhs) const
{
return !(*this == rhs);
}

template<class T>
bool linkedlist<T>::operator<(const linkedlist<T>& rhs) const
{
node<T> *lhsTemp = head;
node<T> *rhsTemp = rhs.head;
while (lhsTemp != NULL && rhsTemp != NULL)
{
if (lhsTemp->data > rhsTemp->data)
return false;
lhsTemp = lhsTemp->next;
rhsTemp = rhsTemp->next;
}
return true;
}

template<class T>
bool linkedlist<T>::operator>(const linkedlist<T>& rhs) const
{
return rhs < *this;
}

template <class T>
bool linkedlist<T>::operator==(const linkedlist<T> &rhs) const
{
node<T> *lhsTemp = head;
node<T> *rhsTemp = rhs.head;
while (lhsTemp != NULL || rhsTemp != NULL)
{
if (lhsTemp != NULL && rhsTemp == NULL || lhsTemp == NULL && rhsTemp != NULL)
return false;
else if (lhsTemp->data != rhsTemp->data)
return false;
lhsTemp = lhsTemp->next;
rhsTemp = rhsTemp->next;
}
return true;
}

template<class T>
linkedlist<T>::~linkedlist()
{
while (head != NULL)
{
node<T> *tmp = head;
head = head->next;
delete tmp;
}
delete head;
}

template<class T>
linkedlist<T>::linkedlist(const linkedlist & rhs) : head(NULL)
{
*this = rhs;
}

template <class T>
linkedlist<T> & linkedlist<T>::operator=(const linkedlist<T> &rhs)
{
if (this != &rhs)
{
node<T> *temp;
while (head != NULL)
{
temp = head;
head = head->next;
delete temp;
}

if (rhs.head != NULL)
head = new node<T>(rhs.head->data);

node<T> *tmpHead = head;

for (node<T> *tmp = rhs.head->next; tmp != NULL; tmp = tmp->next)
{
tmpHead->next = new node<T>(tmp->data);
tmpHead = tmpHead->next;
}
}
return *this;
}

template<class T>
void linkedlist<T>::insert(const T data)
{
if (head == NULL)
{
head = new node<T>(data);
}
else
{
node<T> *temp = head;
for (temp = head; temp->next != NULL; temp = temp->next);
temp->next = new node<T>(data);
}
}

template<class T>
bool linkedlist<T>::search(const T data) const
{
if (head == NULL)
return false;

for (node<T> *tmp = head; tmp != NULL; tmp = tmp->next)
if (tmp->data == data)
return true;

return true;
}

template<class T>
void linkedlist<T>::remove(const T data)
{
bool removed = false;
node<T> *curr = head;
node<T> *prev = head;

for (; curr != NULL && removed == false; curr = curr->next)
{
if (head->data == data)
{
node<T> *tmp = head;
head = head->next;
delete tmp;
removed = true;
}
else if (curr->data == data)
{
node<T> *tmp = curr;
prev->next = curr->next;
delete tmp;
removed = true;
}
prev = curr;
}
}

template<class T>
bool linkedlist<T>::isEmpty() const
{
return head == NULL;
}

template<class T>
ostream & operator<<(ostream & os, const linkedlist<T>& rhs)
{
for (node<T> *temp = rhs.head; temp != NULL; temp = temp->next)
{
os << temp->data;
if (temp->next != NULL)
os << ", ";
}
return os;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.