In C++ Part - 2: Implement a Double linked List ADT to store a collection of int
ID: 3856508 • Letter: I
Question
In C++
Part - 2: Implement a Double linked List ADT to store a collection of integers.
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
main.cpp
---------------------------------
#include <iostream>
#include "DoubleLinked.h"
using namespace std;
int main() {
DoubleLinked* l1 = new DoubleLinked(); //default constructer
DoubleLinked* l2 = new DoubleLinked(55); //custom constructer
DoubleLinked* l3 = new DoubleLinked();
l1 ->append(1);
l1 ->append(2);
l1 ->append(3);
l1 ->append(4); //append
l1 ->append(5);
l1 ->append(6);
l1 ->append(7);
cout<<"FIRST LIST"<<endl;
cout<<"Testing append of 1, 2 ,3 ,4 ,5 ,6, 7"<<endl;
cout<<l1;
cout<<"testing instert front '0'"<<endl;
l1->insertFront(0);
cout<<l1;
cout<<"testing pop front "<<endl; // (<<) overload
l1->deleteFront();
cout<<l1;
cout<<"testing pop last"<<endl;
l1->deleteBack();
cout<<l1;
cout<<"testing reverse list"<<endl;
l1->listReverse();
cout<<l1;
cout<<"testing return size of list"<<endl;
cout<<l1->listSize()<<endl;
cout<<"-------------------------"<<endl;
cout<<"NEW LIST"<<endl;
l2->insertFront(90);
l2 ->append(90);
l2 ->append(91);
l2 ->append(90);
l2 ->append(93);
l2 ->append(90);
l2 ->append(95);
l2->append(90);
cout<<l2;
cout<<"testing delete all copies of number from list, delete all copies of '90'"<<endl;
l2->deleteDuplicates(90);
cout<<l2;
cout<<"testing return Mth term '0' which returns last term and '1' which returns second to last term"<<endl;
cout<<"last term = "<<l2->MtoLastElement(0)<<endl;
cout<<"second to last term = "<<l2->MtoLastElement(1)<<endl;
cout<<"testing = overload, LIST 2 = LIST 1"<<endl;
cout<<" l1 = "<<l1;
cout<<" l2 = "<<l2;
cout<<"l2 = l1"<<endl;
*l2 = *l1;
cout<<" l1 = "<<l1;
cout<<" l2 = "<<l2;
cout<<"test by appending 99 to l1 , l2 should not be effected"<<endl;
l1->append(99);
cout<<" l1 = "<<l1;
cout<<" l2 = "<<l2;
cout<<"-------------------------"<<endl;
cout<<"NEW LIST"<<endl;
l3->insertFront(10);
l3 ->append(11);
l3 ->append(12);
l3 ->append(13);
l3 ->append(14);
l3 ->append(15);
l3 ->append(16);
l3->append(17);
cout<<"testing copy constructor"<<endl;
cout<<"l3 = "<<l3;
cout<<"l4 = Nothing"<<endl;
cout<<" LinkedList l4(l3) "<<endl;
DoubleLinked l4(*l3);
cout<<"l4 = "<<&l4;
cout<<"l3 = "<<l3;
cout<<"test by appending 99 to l3 , l4 should not be effected"<<endl;
l3->append(99);
cout<<"l4 = "<<&l4;
cout<<"l3 = "<<l3;
cout<<"testing destructor"<<endl;
cout<<"delete l1, l2, l3, l4"<<endl;
delete l2;
delete l3;
delete l1;
return 0;
}
----------------------------------------------------------------------------
DoubleLinked.cpp
-----------------------------------------------------
#include <iostream>
#include "DoubleLinked.h"
using namespace std;
DoubleLinked :: DoubleLinked():head(NULL), size(0), tail(NULL){}
DoubleLinked :: DoubleLinked(int data){
node* current = new node;
current->data = data;
head = current;
tail = current;
size = 1;
current->next = NULL;
current->prev = NULL;
}
void DoubleLinked :: append(int data){
node* current = new node;
current->data = data;
current->next = NULL;
if (head == NULL && tail == NULL){
head = current;
tail = current;
size = 1;
current->prev = NULL;
return;
}
else{
node* temp = tail;
temp->next = current;
current->prev = temp;
tail = current;
size++;
}
}
void DoubleLinked:: printList(){
if(head == NULL){
return;
}
node* current = head;
while(current->next != NULL){
cout<<current->data<<"=>";
current = current->next;
}
cout<<current->data<<endl;
}
void DoubleLinked:: insertFront(int data){
node* current = new node;
current->data = data;
if(head == NULL && tail == NULL){
head = current;
tail = current;
size = 1;
current->prev = NULL;
current->next = NULL;
return;
}
else{
current->next = head;
head->prev = current;
head = current;
current->prev = NULL;
size++;
}
}
void DoubleLinked:: deleteList(){
if(head == NULL){
return;
}
node* current = head;
while(current->next != NULL){
node* temp = current;
current = current->next;
delete temp;
current->prev = NULL;
}
delete current;
head = NULL;
tail = NULL;
size = 0;
}
void DoubleLinked:: deleteFront(){
if (head == NULL && tail == NULL){
return;
}
else if(size == 1){
deleteList();
}
else{
node* temp = head;
head = head->next;
temp->next = NULL;
delete temp;
head -> prev = NULL;
size--;
}
}
int DoubleLinked:: listSize(){
return size;
}
void DoubleLinked:: deleteBack(){
if (head == NULL && tail == NULL){
return;
}
else if(size == 1){
deleteList();
size = 0;
}
else{
node* temp;
temp = tail;
tail = tail->prev;
temp->prev = NULL;
tail->next = NULL;
delete temp;
size--;
}
}
void DoubleLinked:: deleteDuplicates(int value){
if(head==NULL && tail == NULL){
return;
}
node* current = head;
while(current->data == value && current == head){
node* temp = head;
head = head->next;
temp->next = NULL;
delete temp;
head -> prev = NULL;
size--;
current = head;
}
current = current->next;
while (current->next != NULL){
if (current->data == value){
node* temp = current;
node* prev;
current = current->next;
prev = temp ->prev;
prev->next = current;
current->prev = prev;
temp->next = NULL;
temp ->prev = NULL;
delete temp;
size--;
}
else{
current = current->next;
}
}
if (size == 1 && current->data == value){
deleteList();
size = 0;
}
else if(current->data == value && current == tail){
node* temp;
temp = tail;
tail = tail->prev;
temp->prev = NULL;
tail->next = NULL;
delete temp;
size--;
}
}
int DoubleLinked:: MtoLastElement(int M){
if ((M - size) *-1 > size){
cout<<"You inputted an integer outside of the range, the function will return 0"<<endl;
return 0;
}
node* current = head;
int count = 1;
M = M - size;
M = M * -1;
while(count != M ){
current = current->next;
count ++;
}
return current->data;
}
void DoubleLinked:: listReverse(){
if (head == tail){
return;
}
if (head == NULL && tail == NULL){
return;
}
node* current = head;
node* next = NULL;
node* prev = NULL;
node* findTail = head;
while(tail->prev != NULL){
next = current->next;
current->next = prev;
current->prev = next;
prev = current;
current = next;
}
head = tail;
tail = findTail;
}
ostream& operator<<(ostream& stream, DoubleLinked* link){
if(link->head == NULL){
return stream;
}
DoubleLinked :: node* current = link->head;
while(current->next != NULL){
stream<<current->data<<"=>";
current = current->next;
}
stream<<current->data<<endl;
return stream;
}
DoubleLinked :: ~DoubleLinked(){
deleteList();
cout<<"Destructor called"<<endl;
}
DoubleLinked& DoubleLinked :: operator=(const DoubleLinked& rhs){
if(rhs.head == NULL && tail == NULL){
this->deleteList();
cout<<"Overloaded = function was called"<<endl;
return *this;
}
this->deleteList();
this->head = new node;
node* rhsHead = rhs.head;
node* link = this->head;
link->data = rhsHead->data;
rhsHead = rhsHead->next;
while(rhsHead != NULL){
node* secondNode = new node;
secondNode->data = rhsHead->data;
link->next = secondNode;
link = link->next;
rhsHead = rhsHead->next;
}
this -> tail = link;
this -> size = rhs.size;
link->next = NULL;
cout<<"Overloaded = function was called"<<endl;
return *this;
}
DoubleLinked :: DoubleLinked(const DoubleLinked& rhs){
if(rhs.head == NULL && tail == NULL){
head = NULL;
tail = NULL;
size = 0;
}
else{
this->head = new node;
node* rhsHead = rhs.head;
node* link = this->head;
link->data = rhsHead->data;
rhsHead = rhsHead->next;
while(rhsHead != NULL){
node* secondNode = new node;
secondNode->data = rhsHead->data;
link->next = secondNode;
link = link->next;
rhsHead = rhsHead->next;
}
link->next = NULL;
tail = link;
size = rhs.size;
}
cout<<"copy constructor was called"<<endl;
}
------------------------------------------------------------------------------------------
DoubleLinked.h
-----------------------------------------
#ifndef DoubleLinked_h
#define DoubleLinked_h
#include <iostream>
#include <ctype.h>
#include <cmath>
using namespace std;
class DoubleLinked{
private:
struct node{
node* next;
node* prev;
int data;
};
public:
node* head;
node* tail;
int size;
DoubleLinked();
DoubleLinked(int data);
void append(int data);
void printList();
void insertFront(int data);
void deleteList();
void deleteFront();
int listSize();
void deleteBack();
void deleteDuplicates(int value);
int MtoLastElement(int M);
void listReverse();
friend ostream& operator<<(ostream& stream, DoubleLinked* link);
~DoubleLinked(); //destructor
DoubleLinked& operator=(const DoubleLinked& rhs); // = overload
DoubleLinked(const DoubleLinked& rhs); //cppy constructor
};
#endif /* DoubleLinked_h */