In C++ Part - 1: Implement a singly linked list ADT to store a collection of dou
ID: 3856506 • Letter: I
Question
In C++
Part - 1: Implement a singly linked list ADT to store a collection of doubles.
PLEASE USE THE LINKS PROVIDED BELOW
(You are allowed to extend the demo code posted on GitHub for this homework. link: https://github.com/Premdeep/CSC340-Summer-2017/tree/master/LinkedList ).
Make sure to provide an interactive user interface to test these new functions in the main() for grader . Your ADT will include the following member functions:
--- a default constructor
--- the "big-3": destructor, copy constructor and overloaded assignment operator
1. a member function pushFront(data) that inserts a node with data at the front of the list
2. a member function pushBack(data) that appends a node with data at the back of the list
3. a member function popFront() that removes first node of the list.
4. a member function popBack() that removes last node of the list.
5. a member function insert(index, val) that inserts a new node with value "val" at a specific position mentioned by the index argument.
6. a member function deleteDuplicates(val) that deletes a node with that number and all its copies from the list, where these copies can be located anywhere in the list.
7. a member function mtoLastElement(M) that returns Mth to the last element of a list such that when M = 0, the last element of the list is returned.
8. a member function size() that returns the size of the list.
9. an overloaded put operator (<<) to print out all the data items stored in a linked list. Note that you are recommended to overload this operator as a friend function of the LinkedList class.
10. a member function reverseList() that reverses a linked list without recreating a temporary copy of this linked list. In other words, your function CAN NOT use the 'new' operator. Here is an example, if a list contains the following data items, 3 -> 5 -> 1 -> 7; this reverse() function will change the list to 7 -> 1 -> 5 -> 3.
Explanation / Answer
Given below is the code and output for the question. Post a comment in case of any issues. Please rate the answer , if it helped. Thank you.
linkedlist.h
// HeaderFile (Interface)
#include <iostream>
using namespace std;
#pragma once
struct node{
int data;
node* next;
};
class linkedlist{
private:
node* head;
int lsize;
public:
linkedlist();
linkedlist(int val);
linkedlist(const linkedlist &other);//copy constructor
~linkedlist();
void printList() const;
void pushBack(int val);
void pushFront(int val);
void popBack();
void popFront();
void insert(int index, int val);
void deleteDuplicates(int val);
int mtoLastElement(int m);
void reverseList();
void deleteList();
bool operator==(const linkedlist& rhs);
int size() const;
friend ostream& operator<<(ostream& out, const linkedlist& rhs); // As a friend function.
linkedlist& operator=(const linkedlist& rhs);
};
// As a stand alone function
//ostream& operator<<(ostream& out, const linkedlist& rhs);
linkedlist.cpp
// Implementation file
#include "linkedlist.h"
linkedlist::linkedlist(){
head = NULL;
lsize = 0;
}
linkedlist::linkedlist(const linkedlist &list2)
{
*this = list2;
}
linkedlist::linkedlist(int val){
pushBack(val);
}
void linkedlist::printList()const{
node* walk = head;
while(walk != NULL){
cout<<walk->data<<" ";
walk = walk->next;
}
cout<<endl;
//cout<<"this-> "<<this<<endl;
}
void linkedlist::pushBack(int val){
node* temp = new node;
temp->data = val;
temp->next = NULL;
if(head == NULL)
head = temp;
else{
node* last = head;
while(last->next != NULL)
last = last->next;
last->next = temp;
}
lsize++;
}
void linkedlist::pushFront(int val){
node* first = new node;
first->data = val;
first->next = head;
head = first;
lsize++;
}
void linkedlist::popFront(){
if(head == NULL)
return;
else{
node* first = head;
head = head->next;
delete first;
first = NULL;
lsize--;
}
}
void linkedlist::popBack(){
if(head == NULL)
return;
else{
node* curr = head;
node* prev = NULL;
while( curr->next != NULL){
prev = curr;
curr = curr->next;
}
if(curr == head) //deleting head node which is the only 1 in list
head = NULL;
else
prev->next = NULL;
delete curr;
curr = NULL;
lsize--;
}
}
void linkedlist::insert(int index, int val)
{
int idx = 0;
node *curr = head, *prev = NULL;
while(curr != NULL){
if(idx == index){
node *temp = new node;
temp->data = val;
temp ->next = NULL;
if(prev == NULL){
temp->next = head;
head = temp;
}
else{
temp->next = curr;
prev->next = temp;
}
lsize++;
break;
}
idx ++;
prev = curr;
curr = curr->next;
}
}
void linkedlist::deleteDuplicates(int val)
{
node* curr = head;
node* prev = NULL;
while(curr != NULL){
if(curr->data == val){
if(prev != NULL){ //deleting a node which is not the first node
prev->next = curr->next;
delete curr;
curr = NULL;
curr = prev->next;
}
else{ //deleting first node
head = curr->next;
delete curr;
curr = NULL;
curr = head;
}
}
else{
prev = curr;
curr = curr->next;
}
}
}
int linkedlist::mtoLastElement(int m)
{
if(m >= lsize || head == NULL)
return -1;
int neededIdx = lsize - 1 - m ; //the index of the node that is distance m from last node
node *curr = head;
for(int i = 0; i < neededIdx; i++)
curr = curr->next;
return curr->data;
}
void linkedlist::reverseList()
{
if(head == NULL || head->next == NULL )//nothing to do for empty list or list with 1 element only
return;
node *first = NULL;
node *second = head;
node *third = head->next;
while(third != NULL)
{
second->next = first;
first = second;
second = third;
third = third->next;
}
second->next = first;
head = second;
}
void linkedlist::deleteList(){
node* temp;
while(head != NULL){
temp = head;
head = head->next;
delete temp;
temp = NULL;
}
head = NULL;
lsize = 0;
}
linkedlist::~linkedlist(){
cout<<"in destructor"<<endl;
deleteList();
}
bool linkedlist::operator==(const linkedlist& rhs){
if(head == rhs.head)
return true;
if(lsize != rhs.lsize)
return false;
node* lhshead = head;
node* rhshead = rhs.head;
int sz = lsize;
while(sz -- != 0){
if(lhshead->data != rhshead->data)
return false;
lhshead = lhshead->next;
rhshead = rhshead->next;
}
return true;
}
int linkedlist::size()const {
return lsize;
}
ostream& operator<<(ostream& out, const linkedlist& rhs){
out<<"[head->"<<rhs.head<< "]: ";
rhs.printList();
//cout<<"this-> "<<this<<endl;
return out;
}
linkedlist& linkedlist::operator=(const linkedlist& rhs){
if(rhs.head == NULL)
deleteList();
else{
deleteList();
node* rhshead = rhs.head;
while(rhshead != NULL){
pushBack(rhshead->data);
rhshead = rhshead->next;
}
}
return *this;
}
main.cpp
#include "linkedlist.h"
int main(){
linkedlist one;
linkedlist two;
linkedlist* three = new linkedlist();
for(int i = 0; i < 5; i++)
one.pushBack(i);
for(int i = 0; i < 5; i++)
two.pushFront(i);
for(int i = 10; i < 15; i++)
three->pushBack(i);
// one.printList();
// two.printList();
*three = two;
three->pushBack(25);
two.pushBack(99);
cout<<one;
cout<<"address of one : "<<&one<<endl;
cout<<two;
cout<<"address of two : "<<&two<<endl;
cout<<*three;
cout<<"address of three : "<<three<<endl;
cout << "list1: " << one;
cout << "list2: " << two;
cout << "list3: " << *three;
if(one == two)
cout<<"lists 1 and 2 are same"<<endl;
else
cout<<"list 1 is not equal to list2"<<endl;
cout << "creating list 4 from list 2 using copy constructor " <<endl;
linkedlist four(two);
cout << "list4: " << four << endl;
if(four == two)
cout<<"lists 4 and 2 are same"<<endl;
else
cout<<"list 4 is not equal to list2"<<endl;
linkedlist five;
five = one;//assignment operator
cout << "list5 assigned list 1, using assignment opertaor " << endl << five << endl;
cout << "insert 100 at index 3 in list 1 " << endl;
one.insert(3, 100);
cout << "list1: " << one << endl;
cout << "getting element 2 to last element from list1 = " << one.mtoLastElement(2) << endl;
cout<< "reversing list1" << endl;
one.reverseList();
cout <<"list1: " << one << endl;
cout << "pop front and pop back from list1" << endl;
one.popFront();
one.popBack();
cout <<"list1: " << one << endl;
cout <<"pushBack 3 in list1 " << endl;
one.pushBack(3);
cout <<"list1: " << one << endl;
cout <<"deleteDuplicates 3 in list1 " << endl;
one.deleteDuplicates(3);
cout <<"list1: " << one << endl;
delete three;
return 0;
}
output
[head->0x100201560]: 0 1 2 3 4
address of one : 0x7fff5fbff598
[head->0x100201ca0]: 4 3 2 1 0 99
address of two : 0x7fff5fbff588
[head->0x1002004c0]: 4 3 2 1 0 25
address of three : 0x100203640
list1: [head->0x100201560]: 0 1 2 3 4
list2: [head->0x100201ca0]: 4 3 2 1 0 99
list3: [head->0x1002004c0]: 4 3 2 1 0 25
list 1 is not equal to list2
creating list 4 from list 2 using copy constructor
list4: [head->0x1005004f0]: 4 3 2 1 0 99
lists 4 and 2 are same
list5 assigned list 1, using assignment opertaor
[head->0x100301090]: 0 1 2 3 4
insert 100 at index 3 in list 1
list1: [head->0x100201560]: 0 1 2 100 3 4
getting element 2 to last element from list1 = 100
reversing list1
list1: [head->0x1002005e0]: 4 3 100 2 1 0
pop front and pop back from list1
list1: [head->0x100202ca0]: 3 100 2 1
pushBack 3 in list1
list1: [head->0x100202ca0]: 3 100 2 1 3
deleteDuplicates 3 in list1
list1: [head->0x1003013a0]: 100 2 1
in destructor
in destructor
in destructor
in destructor
in destructor