C++

//

// main.cpp

#include

using namespace std;

class SortedLinkedList {

struct ListNode {

int data;

ListNode *next;

};

private:

ListNode *head;

int count;

public:

SortedLinkedList (); //default class constructor

~SortedLinkedList(); // class destructor

SortedLinkedList (const SortedLinkedList & other); //Class copy constructor

void insert(int item);

void remove(int item);

int search(int item) const;

// return position of node in list; -1 if not found

bool isEmpty() const;

int length() const;

void display() const;

};

SortedLinkedList::SortedLinkedList () {

// initialize new list to empty list

head = nullptr;

count = 0;

}

SortedLinkedList::~SortedLinkedList() // class destructor

{

// need to delete nodes one by one

// may want to write a member function delete first and use it to delete nodes

one by one until list becomes empty

}

SortedLinkedList::SortedLinkedList (const SortedLinkedList & other){

// copies other into this list. Copies the nodes one by one from other into

this list and updates count of this list (it does what's referred to as deep

copying)

}

void SortedLinkedList::insert(int item) {

// Insert new node in proper sorted order

// list is left sorted.

/*

1. create new node

2. find proper location of list in sorted order. Use two pointers one to point

to node before new node and one to point to node after new node. see VideoNote on

"Inerting a Node in a Linked List".

3. Insert node in the list

Be sure to take care to special cases: list empty, insert at beginning of

list, and inserting at end of list.

*/

}

void SortedLinkedList::remove(int item){

// Removes item from list if found. Does do anything if not found. Leave list

sorted

}

int SortedLinkedList::search(int item) const {

// return position of node in list; -1 if not found

int position = -1;

// find node and update position if found

return position;

}

bool SortedLinkedList::isEmpty() const{

return count == 0;

}

int SortedLinkedList::length() const {

return count;

}

void SortedLinkedList::display() const {

ListNode *p = head;

while (p ){

cout data

}

cout

}

int main() {

SortedLinkedList myList;

//Test length, display, and insert

cout

myList.insert(65);

myList.insert(11);

myList.insert(78);

myList.insert(102);

myList.insert(4);

myList.insert(55);

myList.display();

myList.length();

int index = myList.search(55);

cout

index = myList.search(88);

cout

//Test remove

myList.remove(65); // from inside

myList.display();

myList.remove(4); // from beginning

myList.display();

myList.remove(102); // from end

myList.display();

myList.remove(88); // not found

myList.display();

// Test copy constructor

SortedLinkedList list2 = myList;

list2.display();

list2.length();

myList.insert(100);

list2.display();

list2.length();

return 0;

}

1. A question that I got few times is about the sorting algorithm that need to be used in the sorted list class. Answer: You don't need to use any sorting algorithm. The idea is that items should always be inserted in the proper sorted order by the insert function and the delete function should also leave the list in sorted order. If the insert and delete functions work as described above then the list is always sorted and you never need to run a sorting algorithm. 2. See attached file below for a skeleton of the SortedLinkedList class. SortedLinked List.cpp D Note that you don't have to use the exact same names I used for the class or its members. I also include a sample test driver program to test your class. You may use for your screenshots. Design and implement your own linked list class to hold a sorted list of integers in ascending order. The class should have member functions for inserting an item in the list, deleting an item from the list, and searching the list for an item. Note: the search function should return the position of the item in the list (first item at position 0) and -1 if not found. In addition, it should have member functions to display the list, check if the list is empty, and return the length of the list. Be sure to have a class constructor, a class destructor, and a copy constructor for deep copy. Demonstrate your class with a driver program (be sure to include the following cases: insertion at the beginning, end, and inside the list, deletion of first item, last item, and an item inside, searching for an existingon-existing item, and modifying a list that was initialized to an existing list). Deliverables: submit the following 1. A copy of your class definition and your driver program in a text file. 2. Screen shots showing your class meets the problem specifications