for the function clone the list given needs to be cloned in a new list exatcly l

Question

for the function clone the list given needs to be cloned in a new list exatcly like a deep copy.

#ifndef LIST_H
#define LIST_H

#include <algorithm>
#include <iostream>

/**
* class List<T>
*
* General description: class for storing and manipulating sequences of items
* where item type is specified via template.
*
* Underlying organization: the implementation uses a singly-linked list data structure
* with pointers to both the front (first node) and back (last node) of the list.
*
* A private struct Node is used to represent individual nodes in a list.
*/

template <typename T>
class List
{
private:

struct Node
{
T data;
Node *next;

Node(const T &d = T{}, Node *n = nullptr)
: data{d}, next{n} {}
};

/* Data members of List class: a front and back pointer */
Node *front;
Node *back;
int list_size;
public:
// constructor
List() {
front = nullptr;
back = nullptr;
list_size = 0;
}

// destructor
~List() {
clear();
}
/**
* Disclaimer: C++ conventions tell us that we should have a couple
* of additional constructors here (a copy constructor, assignment operator
* etc.)
*
* However, to keep things simple for now we will ignore that convention
* (since the exposure to C++ is pretty variable it seems -- some students
* having taken 141 before last semester; some students coming from 107,
* etc.)
*/

/**
* function: clear
* desc: makes the calling list empty (but the list still
* exists).
*/
void clear()
{
Node *p = front;
Node *pnext;

while (p != nullptr)
{
pnext = p->next;
delete p;
p = pnext;
}
front = back = nullptr;
}

int length() const
{
return list_size;
}
public:
/**
* function: is_empty
* desc: Returntrue if the list is empty, false otherwise.
*/
bool is_empty() const
{
return front == nullptr;
}

/**
* function: print
* desc: self-evident: simply prints the elements/values of the list in order.
*/
void print() const
{
Node *p = front;

std::cout << "[ ";
while (p != nullptr)
{
std::cout << p->data << " ";
p = p->next;
}
std::cout << "] ";
}

/**
* function: push_front
* desc: adds a new element to the front of the list (calling object) containing val.
* Equivalently, you can think of this as an "prepend" operation.
*/
void push_front(const T &data)
{
front = new Node(data, front);

if (back == nullptr)
back = front;
list_size++;
}

/**
* function: pop_front
* desc: if the list (calling object) is non-empty, the first element (front of list)
* is removed and the value it stored is 'passed back' to the caller via the reference
* parameter val. In this case (non-empty list), true is returned for success.
*
* Otherwise (the list is empty), false is returned and the reference parameter val has
* no meaning.
*/
bool pop_front(T &val)
{
Node *tmp;

if (front == nullptr)
return false;
val = front->data;

tmp = front;
front = front->next;
delete tmp;
if (front == nullptr)
back = nullptr;
list_size++;

return true;

}

/**
* function: push_back
* desc: adds a new element to the end of the list (calling object) containing val.
* Equivalently, you can think of this as an "append" operation.
*/
void push_back(const T &val)
{
Node *tmp = new Node(val, nullptr);

if (front == nullptr)
{
front = back = tmp;
}
else
{
back->next = tmp;
back = tmp;
list_size--;
}
}

/**
* function: remove_first
* desc: removes first ocflience of x (if any) in given list (calling object).
* if a match is found (and removed), true is returned.
* Otherwise (no match found), false is returned and the list is unchanged.
*/
bool remove_first(const T &x)
{
Node *p, *tmp;
T dummy;

if (front == nullptr)
return false;
if (front->data == x)
{
pop_front(dummy);
return true;
}
p = front;
while (p->next != nullptr)
{
if (x == p->next->data)
{
tmp = p->next;
p->next = tmp->next;
if (tmp == back)
back = p;
delete tmp;
return true;
}
p = p->next;
}
return false;
}

/**
* function: slow_remove_all
* desc: removes all occurrences of x (if any) in given list (calling object).
* returns number of matches found/deleted. Relative order of undeleted elements
* is unchanged.
*
* approach: repeatedly calls remove_first until it fails.
*
* Note: function is designated with the slow_ prefix because, in the worst case, it can
* take quadratic time.
*/
int slow_remove_all(const T &x)
{
int n = 0;

while (remove_first(x))
n++;
return n;
list_size--;
}

/**
* function: is_sorted
* desc: returns true if elements in list are in sorted order from
* smallest to largest (duplicates allowed); returns false otherwise.
*
* Note: requires that type T has the > operator defined on it (perhaps via
* operator overloading as in the case of the string class)
*/
bool is_sorted() const
{
Node *p = front;

while (p != nullptr && p->next != nullptr)
{
if (p->data > p->next->data)
return false;
p = p->next;
}
return true;
}

int count(const T &x) const
{
int frequency = 0;

if (this->is_empty())
return frequency;

Node* temp1 = front;
while (temp1 != nullptr) {

if (temp1->data == x)
frequency++;
temp1 = temp1->next;
}
return frequency;

}

bool pop_back(T &data)
{
if(front == nullptr)
return false;
else{
Node *temp1 = front;
while(temp1->next->next != nullptr) {
temp1 = temp1->next;
}
this->back = temp1;
temp1=temp1->next ;
data = temp1-> data;
delete (temp1);
return true;
  

}

}

/**

   * TODO

   * function: clone

   *

   * description: makes a "deep copy" of the given list a

   * and returns it (as a List pointer).

   *

   * NOTE: this functionality would normally be folded into

   * a "copy constructor"

   *

   */

List<T> *clone() const

{

}

Explanation / Answer

#ifndef LIST_H

#define LIST_H

#include <algorithm>

#include <iostream>

/**

* class List<T>

*

* General description: class for storing and manipulating sequences of items

* where item type is specified via template.

*

* Underlying organization: the implementation uses a singly-linked list data structure

* with pointers to both the front (first node) and back (last node) of the list.

*

* A private struct Node is used to represent individual nodes in a list.

*/

template <typename T>

class List

{

private:

struct Node

{

T data;

Node *next;

Node(const T &d = T{}, Node *n = nullptr)

: data{d}, next{n} {}

};

/* Data members of List class: a front and back pointer */

Node *front;

Node *back;

int list_size;

public:

// constructor

List() {

front = nullptr;

back = nullptr;

list_size = 0;

}

// destructor

~List() {

clear();

}

/**

* Disclaimer: C++ conventions tell us that we should have a couple

* of additional constructors here (a copy constructor, assignment operator

* etc.)

*

* However, to keep things simple for now we will ignore that convention

* (since the exposure to C++ is pretty variable it seems -- some students

* having taken 141 before last semester; some students coming from 107,

* etc.)

*/

/**

* function: clear

* desc: makes the calling list empty (but the list still

* exists).

*/

void clear()

{

Node *p = front;

Node *pnext;

while (p != nullptr)

{

pnext = p->next;

delete p;

p = pnext;

}

front = back = nullptr;

}

int length() const

{

return list_size;

}

public:

/**

* function: is_empty

* desc: Returntrue if the list is empty, false otherwise.

*/

bool is_empty() const

{

return front == nullptr;

}

/**

* function: print

* desc: self-evident: simply prints the elements/values of the list in order.

*/

void print() const

{

Node *p = front;

std::cout << "[ ";

while (p != nullptr)

{

std::cout << p->data << " ";

p = p->next;

}

std::cout << "] ";

}

/**

* function: push_front

* desc: adds a new element to the front of the list (calling object) containing val.

* Equivalently, you can think of this as an "prepend" operation.

*/

void push_front(const T &data)

{

front = new Node(data, front);

if (back == nullptr)

back = front;

list_size++;

}

/**

* function: pop_front

* desc: if the list (calling object) is non-empty, the first element (front of list)

* is removed and the value it stored is 'passed back' to the caller via the reference

* parameter val. In this case (non-empty list), true is returned for success.

*

* Otherwise (the list is empty), false is returned and the reference parameter val has

* no meaning.

*/

bool pop_front(T &val)

{

Node *tmp;

if (front == nullptr)

return false;

val = front->data;

tmp = front;

front = front->next;

delete tmp;

if (front == nullptr)

back = nullptr;

list_size--;

return true;

}

/**

* function: push_back

* desc: adds a new element to the end of the list (calling object) containing val.

* Equivalently, you can think of this as an "append" operation.

*/

void push_back(const T &val)

{

Node *tmp = new Node(val, nullptr);

if (front == nullptr)

{

front = back = tmp;

}

else

{

back->next = tmp;

back = tmp;

list_size++;

}

}

/**

* function: remove_first

* desc: removes first ocflience of x (if any) in given list (calling object).

* if a match is found (and removed), true is returned.

* Otherwise (no match found), false is returned and the list is unchanged.

*/

bool remove_first(const T &x)

{

Node *p, *tmp;

T dummy;

if (front == nullptr)

return false;

if (front->data == x)

{

pop_front(dummy);

return true;

}

p = front;

while (p->next != nullptr)

{

if (x == p->next->data)

{

tmp = p->next;

p->next = tmp->next;

if (tmp == back)

back = p;

delete tmp;

return true;

}

p = p->next;

}

return false;

}

/**

* function: slow_remove_all

* desc: removes all occurrences of x (if any) in given list (calling object).

* returns number of matches found/deleted. Relative order of undeleted elements

* is unchanged.

*

* approach: repeatedly calls remove_first until it fails.

*

* Note: function is designated with the slow_ prefix because, in the worst case, it can

* take quadratic time.

*/

int slow_remove_all(const T &x)

{

int n = 0;

while (remove_first(x))

n++;

return n;

list_size--;

}

/**

* function: is_sorted

* desc: returns true if elements in list are in sorted order from

* smallest to largest (duplicates allowed); returns false otherwise.

*

* Note: requires that type T has the > operator defined on it (perhaps via

* operator overloading as in the case of the string class)

*/

bool is_sorted() const

{

Node *p = front;

while (p != nullptr && p->next != nullptr)

{

if (p->data > p->next->data)

return false;

p = p->next;

}

return true;

}

int count(const T &x) const

{

int frequency = 0;

if (this->is_empty())

return frequency;

Node* temp1 = front;

while (temp1 != nullptr) {

if (temp1->data == x)

frequency++;

temp1 = temp1->next;

}

return frequency;

}

bool pop_back(T &data)

{

if(front == nullptr)

return false;

else{

Node *temp1 = front;

while(temp1->next->next != nullptr) {

temp1 = temp1->next;

}

this->back = temp1;

temp1=temp1->next ;

data = temp1-> data;

delete (temp1);

return true;

}

}

/**

   * TODO

   * function: clone

   *

   * description: makes a "deep copy" of the given list a

   * and returns it (as a List pointer).

   *

   * NOTE: this functionality would normally be folded into

   * a "copy constructor"

   *

   */

List<T> *clone() const

{  

    // create a new list

    List *new_list = new List();

   

    // if the list is empty

    if( this->front == NULL )

        return new_list;

   

    // point trav to the front of the list

    Node *trav = this->front;

   

    // traverse through the list

    while( trav != NULL )

    {

        // get the value of the current node

        T temp = trav->data;

       

        // add the current node to the end of the new list

        new_list.push_back(temp);

       

        // go to next node

        trav = trav->next;

    }

   

    return new_list;

}

};

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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