Linked-list. Anyone could help to finish the function insert_sorted() ? template

Question

Linked-list. 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

Given below is the completed code.
Please do rate the answer if it was helpful. Thank you

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)
{
Node *n = new Node(x, nullptr);
if(front == nullptr) //1st node being added
{
front = back = n;
return;
}
//find the location where to insert
Node *prev = nullptr;
Node *curr = front;
while(curr != nullptr)
{
if(x < curr->data)
break;
prev = curr;
curr = curr->next;
}
n->next = curr;
if(curr == front) //add the node in the front of list? update front
front = n;
else
prev->next = n;
if(prev == back) //if insertion at the end of list? update back
back = n;
}
}

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

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