this is the function that needs to be finished . insert_sorted #ifndef LIST_H #d

Question

this is the function that needs to be finished .  insert_sorted

#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;
//list_size++; go back to this

}

}

/** TODO

   * function: insert_sorted

   *

   * description: assumes given list is already in sorted order from

   * smallest to largest and inserts x into the appropriate position

   * retaining sorted-ness.

   * Note 1: duplicates are allowed.

   *

   * Note 2: if given list not sorted, behavior is undefined/implementation

   * dependent. We blame the caller.

   * So... you don't need to check ahead of time if it is sorted.

   *

   *

   * REQUIREMENTS:

   *

   * O(n) runtime

   */

void insert_sorted(const T &x)

{

}

Explanation / Answer

Below is your code

void insert_sorted(const T &x) {
  
Node *p = front;
Node *temp = new Node(x, front);

if(p == nullptr) {
return;
}
if(p->next == nullptr) {
push_back(x);
return;
}
while(p->next != nullptr) {
if(p->next->data > x) {
temp->next = p->next;
p->next = temp;
list_size++;
return;
}
p = p->next;
} // end while

}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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