Question

Using C++

• Implement the following in both string linked list and in the template version of the class:

• Add to the back and remove from back of the list :

- void addBack(….);

- string removeBack(); E removeBack(…);

• Insert elements in a sorted list i.e., find the position where an element fits and add it to the list. Note you must call the addBack and addFront functions if you insert in the front or rare of the list (same for remove functions) :

- void insert(string value); void insert(E value)

- void delete(string value); void delete(E value);

//SNode.h

#pragma once
#include
#include

template
class SNode {

private:
   E elem;
   SNode* next;
   friend class SLinkedList;
};

//SLinkedList.h

#pragma once
#include
#include

template
class SLinkedList {

public:
   SLinkedList();
   ~SLinkedList();
   bool empty() const;
   const E& front() const;
   void addFront(const E& e);
   void removeFront();
private:
   SNode* head;

};

template
SLinkedList::SLinkedList() : head(NULL) {}

template
bool SLinkedList::empty() const {
   return head == NULL;
}

template
const E& SLinkedList::front() const {
   return head->elem;
}

template
SLinkedList::~SLinkedList() {
   while (!empty()) removeFront();
}

template
void SLinkedList::addFront(const E& e) {
   SNode* v = new SNode;
   v->elem = e;
   v->next = head;
   head = v;
}

template
void SLinkedList::removeFront() {
   SNode* old = head;
   head = old->next;
   delete old;
}

Answer 1

//SNode.h
template<class E>
class SNode {
public:
E elem;
SNode<E>* next;
};

//SLinkedList.h

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

template<class E>
class SLinkedList {

public:
SLinkedList();
~SLinkedList();
bool empty() const;
const E& front() const;
void addFront(const E& e);
void removeFront();
void addBack(const E& e);
void removeBack();
void insert(E value);
void Delete(E value);
void display();
private:
SNode<E>* head;

};

template<typename E>
SLinkedList<E>::SLinkedList() {
   head = NULL;
}

template<typename E>
bool SLinkedList<E>::empty() const {
return head == NULL;
}

template<typename E>
const E& SLinkedList<E>::front() const {
return head->elem;
}

template<typename E>
SLinkedList<E>::~SLinkedList() {
while (!empty()) removeFront();
}

template<typename E>
void SLinkedList<E>::addFront(const E& e) {
SNode<E>* v = new SNode<E>;
v->elem = e;
v->next = head;
head = v;
}

template<typename E>
void SLinkedList<E>::removeFront() {
   if(!head)return;
SNode<E>* old = head;
head = old->next;
delete old;
}

template<typename E>
void SLinkedList<E>::addBack(const E& e) {
SNode<E>* v = new SNode<E>;
v->elem = e;
v->next = NULL;
if(head==NULL)head = v;
SNode<E>*current = head;
while(current->next)current = current->next;
current->next = v;
}

template<typename E>
void SLinkedList<E>::removeBack() {
if(!head)return;
SNode<E>* current = head,*prev=head;
if(head->next==NULL){
    head = current->next;
delete current;
return;
}
while(current->next){
    prev=current;
    current = current->next;
}

prev ->next = current->next;
delete current;
return ;
}

template<typename E>
void SLinkedList<E>::insert(E value){
if(head==NULL || head->elem>value){
    addFront(value);
    return;
}
SNode<E>* v = new SNode<E>;
v->elem = value;
v->next = NULL;
SNode<E>* previous = head;
SNode<E>* current = head->next;
       while (current != NULL && value > current->elem)
       {
       previous = current;
       current = current->next;
       }
   previous->next = v;
        v->next = current;
}
template<typename E>
void SLinkedList<E>::Delete(E value){
   if(head==NULL)return;
   if(head->elem==value){
       removeFront();
       return;
   }
   SNode<E>* previous = head;
SNode<E>* current = head->next;
  
while(current && current->elem!=value){
   previous=current;
   current=current->next;
   }
if(!current){
   cout<<"No found in list\n";
   return;
   }
  
   if(current->next==NULL){
       removeBack();
       return;
   }
   previous->next = current->next;
   delete current;
}
template<typename E>
void SLinkedList<E>::display(){
   SNode<E>*current = head;
   cout<<"List is : ";
   while(current){
       cout<<current->elem<<" ";
       current= current->next;
   }
   cout<<"\n\n";
}

//Main.cpp

#include"SLinkedList.h"

int main(){
  
   SLinkedList<int>list;
  
   list.insert(5);
   list.insert(3);
   list.insert(2);
   list.insert(1);
   list.insert(4);
  
   list.display();
  
   list.Delete(1);
  
   list.display();
  
   list.Delete(5);
  
   list.display();
  
  
   SLinkedList<string>list1;
  
   list1.insert("Dog");
   list1.insert("Mango");
   list1.insert("Apple");
   list1.insert("Cat");
   list1.insert("Hello");
  
   list1.display();
  
   list1.Delete("Mango");
  
   list1.display();
  
   list1.Delete("Cat");
  
   list1.display();
   return 0;
}

//sample output

C\Users\IshuManish\Documents SLinkedList.exe List is : 1 2 3 4 5 List is 2 3 4 5 List is :2 34 IList is Apple Cat Dog Hello Mango Apple Cat Dog Hello IList is IList is Apple Dog Hello Process exited after 0.1907 seconds with return value 0 Press any key to continue