Using linked lists on C++ need assistance in two functions, insertSorted and rem

Question

Using linked lists on C++

need assistance in two functions, insertSorted and removeSorted. I am a bit stuck and not able to wrap my head around this so well. With the insert sorted function, not allowed to use looping statements. Only change the List header for functions, source can be used whichever way to test.

insert directions : Function insertSorted() inserts a new entry into the sorted list as indicated below:
Using a pointer to create a new node that contains the new entry: Node<ItemType> newNodePtr=new Node<ItemType>(newEntry);
If the list is empty, add the new node to the beginning of the list.
If all the items in the list is greater than or equal to the newEntry, add the new node at the beginning of the list as well.Otherwise, insert the new node into the list right before the first node that contains the item that is greater than or equal to the newEntry. If all the entries in the list are less than newEntry, add the new entry at the end of the list. You may need following two pointers to complete the insertion: preNode=getNodeBefore(newEntry); curNode=preNode->getNext();

remove directions:

The Function removeSorted() removes a given entry from the sorted list. If the list is empty, return false. (removal failed) Otherwise, you may use following statements to find a pointer: preNode=getNodeBefore(anEntry); If preNode=NULL, that means either the item in the first node of the list is greater than anEntry or the item in the first node of the list is equal to anEntry. If the item is greater than the anEntry, then return false (anEntry is not in the list). If the item is equal to the anEntry, remove the first node of the list. If preNode!=NULL, find following pointer: curNode=preNode->getNext(); If curNode==NULL or curNode->getItem()>anEntry, return false (anEntry is not in the list). If curNode->getItem()==anEntry, remove the node that curNode points to.

header: https://pastebin.com/Sp6Ve0Rb

header(node): https://pastebin.com/981LAp7L

source: https://pastebin.com/FnhXbEHt

Explanation / Answer

Here is your linkedlist code.

/*************************/SortedList.h

/*
* SortedList.h
*
* Created on: 19-Mar-2018
*      Author: tan
*/
#include <iostream>
using namespace std;

template<typename T>
struct Node{
       T data;
       Node* next;
   };

template<typename T>
class SortedList{

   Node<T>* head;
public:
   SortedList<T>();
   SortedList<T>(T val);
   Node<T>* createNode(T value);
   void insertSorted(T val);
   void removeSorted(T val);

   void printList();
};
template<typename T>
SortedList<T>::SortedList(){
   head=NULL;
}
template<typename T>
SortedList<T>::SortedList(T val){
   head=createNode(val);
}
template<typename T>
Node<T>* SortedList<T>::createNode(T value){
   Node<T>* ptr=new Node<T>;
   ptr->data=value;
   ptr->next=NULL;
   return ptr;
}
template<typename T>
void SortedList<T>::insertSorted(T value){
   if(head==NULL){
       head=createNode(value);
       return;
   }
   Node<T>* ptr=head;
   if(value<ptr->data){
       Node<T>* tmp=createNode(value);
       tmp->next=ptr;
       head=tmp;
   }
   else{
       while(ptr->next!=NULL){
           if(value>ptr->next->data)
           ptr=ptr->next;
           else
               break;
       }
       Node<T>* tmp=createNode(value);
       tmp->next=ptr->next;
       ptr->next=tmp;
   }

}

template<typename T>
void SortedList<T>::printList(){
   Node<T>* ptr=head;
   while(ptr){
       cout<<ptr->data<<"->";
       ptr=ptr->next;
   }
   cout<<endl;
}
template<typename T>
void SortedList<T>::removeSorted(T value){
   if(head==NULL){
       cout<<"REmoval fail"<<endl;
       return;
   }
   Node<T>* ptr=head;
   if(value==ptr->data){
       Node<T>* tmp=ptr;
       ptr=ptr->next;
       delete tmp;
   }
   else{
       while(ptr->next!=NULL){
           if(value!=ptr->next->data)
           ptr=ptr->next;
           else
               break;
       }
       Node<T>* tmp=ptr->next;
       ptr->next=ptr->next->next;
       delete tmp;
   }

}

/************************/LinkedList.cpp

/*
LL.h

LL.cpp

I have finished the first part of the assignment, you need to do the part 2 and 3, also when you try to count the number of object, use static instead of iterator.

Here's the part 1 code

Address.h:

TicketOrder.h

Test.cpp
*/
#include<iostream>

#include "SortedList.h"

using namespace std;

int main()
{
cout << "Welcome!" << endl;
SortedList<int> slist(10);
slist.insertSorted(5);
slist.insertSorted(15);
slist.insertSorted(35);
slist.insertSorted(25);
slist.printList();
slist.removeSorted(15);
slist.printList();
return 0;
}

/************************/output

Welcome!
5->10->15->25->35->
5->10->25->35->

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

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