Implement a singly linked list ADT to store a collection of doubles Make sure to
ID: 3855480 • Letter: I
Question
Implement a singly linked list ADT to store a collection of doublesMake 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.
Submission: submit your header file and the two .cpp files for each ADT as whole zip.
Implement a singly linked list ADT to store a collection of doubles
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.
Submission: submit your header file and the two .cpp files for each ADT as whole zip.
Implement a singly linked list ADT to store a collection of doubles
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.
Submission: submit your header file and the two .cpp files for each ADT as whole zip.
Explanation / Answer
Here is a generic singly linked list created by me
/*
* Llist.h
*
* Created on: 13-Apr-2017
* Author: Rj
*/
#ifndef LLIST_H_
#define LLIST_H_
#include <iostream>
#include "RjExceptions.cpp"
template <typename T>
struct Node {
Node<T> *next;
T val;
};
/**
* Creates a singly linked list with a **head** and a **last**. **head** will be
* used to store the address of the first node ever created and the latest will
* be stored in the last.
*/
template <typename T>
class Llist {
// This will store the first node's address.
Node<T> *head;
// This is going to hold the latest node's address.
Node<T> *last;
public:
// CONSTRUCTOR
Llist();
// Adds a val to list.
void add(T val);
// Add object at given index.
void add(int indx, T val);
// Add to start.
void add_front(T val);
// Iterate.
void iterate();
// Reverse iterate.
void iterate_reverse();
// Get the element at index.
T at(int indx);
// Gets the index of certain object.
int indexOf(T val);
// Add object at given index.
void update(int indx, T val);
// Delete
void remove(int indx);
void pop_front();
void pop_back();
};
#endif /* LLIST_H_ */
/*
* Llist.cpp
*
* Created on: 13-Apr-2017
* Author: Rj
*/
#include "Llist.h"
/**
* Constructor function
* This function Initializes head and last to NULL.
*/
template <typename T>
Llist<T>::Llist() : head{ NULL }, last{ NULL }
{};
/**
* Adds a val to the list.
* @param { T } val - val of the object to add.
*/
template <typename T>
void Llist<T>::add(T val) {
// If it is the first node
// Just normal initializing does not produce new objects every time the method is
// called.
Node<T> *nd1 = new Node<T>;
nd1->next = NULL;
if (head == NULL) {
head = nd1;
}
else {
last->next = nd1;
}
nd1->val = val;
last = nd1;
};
/**
* @Overload
* Add given object at a given index.
* @param { int } indx - Index to append at.
* @param { T } val - Object to append.
*/
template <typename T>
void Llist<T>::add(int indx, T val) {
Node<T> *temp1{ head };
Node<T> *temp2{ NULL };
int i{ 0 };
do {
if (i == indx && i != 0) {
Node<T> *nd1 = new Node<T>;
// Copy Previous one's.
nd1->next = temp1;
nd1->val = val;
temp2->next = nd1;
}
++i;
temp2 = temp1;
temp1 = temp1->next;
} while(temp1 != NULL);
}
/**
* Iterates over the list from start to end and prints to the screen.
*/
template <typename T>
void Llist<T>::iterate() {
if (head == NULL) {
list_un_inited err;
throw err;
}
// Iterate through the list until you hit a NULL.
Node<T> *temp{ head };
do {
std::cout << temp->val << std::endl;
temp = temp->next;
} while(temp != NULL);
};
/**
* Returns the object at the given index.
* @param { int } indx - Index of the object to get.
*/
template <typename T>
T Llist<T>::at(int indx) {
Node<T> *temp{ head };
int i{ 0 };
do {
if (i == indx) {
return temp->val;
}
++i;
temp = temp->next;
} while(temp != NULL);
out_of_bounds_index err;
throw err;
}
template <typename T>
int Llist<T>::indexOf(T val)
{
Node<T> *temp{ head };
int i{ 0 };
do {
if (temp->val == val) {
return i;
}
++i;
temp = temp->next;
} while(temp != NULL);
out_of_bounds_index err;
throw err;
}
/**
* Adds an object to the start of an array.
* @param { T } val - Object to add.
*/
template <typename T>
void Llist<T>::add_front(T val) {
// Create a new node.
Node<T> *nd1 = new Node<T>;
// Set its prev to NULL.
nd1->next = head;
nd1->val = val;
// Change others
head = nd1;
};
/**
* Adds an object to the start of an array.
* @param { int } indx - Index of object to change.
* @param { T } val - Object to change index to.
*/
template <typename T>
void Llist<T>::update(int indx, T val) {
Node<T> *temp{ head };
int i{ 0 };
do {
if (i == indx) {
temp->val = val;
}
++i;
temp = temp->next;
} while(temp != NULL);
};
/**
* Deletes an object at given index
* @param { int } indx - Index of object to remove.
*/
template <typename T>
void Llist<T>::remove(int indx) {
Node<T> *temp1{ head };
Node<T> *temp2{ NULL };
int i{ 0 };
do {
if (i != 0 && i == indx) {
temp2->next = temp1->next;
}
++i;
temp2 = temp1;
temp1 = temp1->next;
} while(temp1 != NULL);
temp2->next = NULL;
};
/**
* Deletes the first element of the array.
*/
template <typename T>
void Llist<T>::pop_front() {
head = head->next;
};
/**
* Deletes the last element of an array.
*/
template <typename T>
void Llist<T>::pop_back() {
Node<T> *temp1{ head };
Node<T> *temp2{ NULL };
do {
temp2 = temp1;
temp1 = temp1->next;
} while(temp1->next != NULL);
temp2->next = NULL;
};
/*
* RjExceptions.cpp
*
* Created on: 13-Apr-2017
* Author: Rj
*/
#include <exception>
/**
* Array index goes out of bounds! Then throw this error.
*/
class out_of_bounds_index : public std::exception {
public:
const char* what() const throw() {
return "The index you provided was out of bounds!";
}
};
/**
* Use when methods are called on empty lists.
*/
class list_un_inited : public std::exception {
public:
const char* what() const throw() {
return "The index you provided was out of bounds!";
}
};
//============================================================================
// Name : SinglyLinkedListDriver.cpp
// Author : Ramachandra jr
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include "Llist.cpp"
#include <cstdlib>
int main() {
srand(time(NULL));
Llist<int> mylist1{};
const int MAX_NUM = 100;
for (int i = 0; i < 20; ++i) {
int randnum = (rand()%MAX_NUM)+1;
mylist1.add(randnum);
}
mylist1.iterate();
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.