Anyone could help to finish the function insert_sorted() ? template <typename T>
ID: 3751866 • Letter: A
Question
Anyone could help to finish the function insert_sorted()?
template <typename T>
class List
{
private:
// struct for singly-linked list nodes
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;
public:
// constructor
List() {
front = nullptr;
back = nullptr;
}
// destructor
~List() {
clear();
}
/** 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
please give thumbs up, thanks
class List
{
private:
// struct for singly-linked list nodes
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;
public:
// constructor
List() {
front = nullptr;
back = nullptr;
}
// destructor
~List() {
clear();
}
/** 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)
{
Node *ptr=this->front;
Node *temp=new Node(x,nullptr);
// if list is empty
if(ptr==nullptr)
{
this->front=temp;
this->back=temp;
}
// if the node is to be inserted at the beginning
// of the doubly linked list
else if(ptr->data>=temp->data)
{
temp->next=this->front;
temp->next->prev=temp;
this->front=temp;
}
else
{
// locate the node after which the new node
// is to be inserted
while(ptr!=this->back && ptr->next->data<temp->data)
{
ptr=ptr->next;
}
/* Make the appropriate links */
temp->next=ptr->next;
// if the new node is not inserted
// at the end of the list
if(ptr->next!=this->back)
temp->next->prev=temp;
ptr->next=temp;
temp->prev=ptr;
}
}
};
class List
{
private:
// struct for singly-linked list nodes
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;
public:
// constructor
List() {
front = nullptr;
back = nullptr;
}
// destructor
~List() {
clear();
}
/** 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)
{
Node *ptr=this->front;
Node *temp=new Node(x,nullptr);
// if list is empty
if(ptr==nullptr)
{
this->front=temp;
this->back=temp;
}
// if the node is to be inserted at the beginning
// of the doubly linked list
else if(ptr->data>=temp->data)
{
temp->next=this->front;
this->front=temp;
}
else
{
// locate the node after which the new node
// is to be inserted
while(ptr!=this->back && ptr->next->data<temp->data)
{
ptr=ptr->next;
}
/* Make the appropriate links */
temp->next=ptr->next;
if(ptr==this->back)
{
this->back=temp;
}
}
}
};
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.