C++ Modify the Linked List program to create a sorted version of the linked list

Question

C++

Modify the Linked List program to create a sorted version of the linked list that maintains the list in ascending order.

The only function you need to change is the insert function which should take in just a value. The item should be placed into the list in the appropriate position based on the value, so the user does not need to provide an index.

below are the programs

typedef int ListItemType;

struct node {
ListItemType item;
node *next;
};

class List {
public:
List();
~List();
bool isEmpty();
int getLength();
void insert(int index, ListItemType newItem);
void remove(int index);
ListItemType retrieve(int index);
private:
node *head;
int size;
node *find(int index);
};

_________________________________________________________________________________________________

#include "ListVersionTwo.h"
#include <cstdlib>
#include <iostream>
using namespace std;

List::List(){
size = 0;
head = NULL;
}

List::~List(){
while (size > 0) {
remove(0);
}
}

bool List::isEmpty(){
return size==0;
}

int List::getLength(){
return size;
}

void List::remove(int index){
if ((index < 0) || (index > size-1)){
cout << "remove failed" << endl;
return;
}

if (index==0) {
node *cur = head;
head = head->next;
delete cur;
}
else {
node *prev = find(index-1);
node *cur = prev->next;
prev->next = cur->next;
delete cur;
}
size--;
}

ListItemType List::retrieve(int index){
if ((index < 0) || (index > size-1)){
cout << "remove failed" << endl;
return -1;
}
node *cur = find(index);
return cur->item;
}

void List::insert(int index, ListItemType newItem){
if ((index < 0)||(index > size)) {
cout << "insert failed" << endl;
return;
}
node *cur = new node;
cur->item = newItem;
  
if (index == 0) {
cur->next = head;
head = cur;
}
else {
node *prev = find(index-1);
cur->next = prev->next;
prev->next = cur;
}
size++;
}

node *List::find(int index) {
node *cur = head;
for (int i = 0; i < index; i++) {
cur = cur->next;   
}
return cur;
}

Explanation / Answer

Answer :

void List::insert(int index, ListItemType newItem)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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