**If the code isnt compiling correctly, go to Properties-->\"C/C++ Build\"-->col
ID: 3910553 • Letter: #
Question
**If the code isnt compiling correctly, go to Properties-->"C/C++ Build"-->collapse and select "Settings". Under Tool settings tab highlight Miscellaneous. Add -std=C++11 to the "Other Flags" input field
Fill in the CODE HERE parts
Initial Problem: As a classic first data structures assignment, you will take the skeleton code provided and fill in the functions for a complete Doubly-Linked List (in LL.h). After this Linked List is complete, use its public operations to fill in the Stack/Deque template classes as well. These are standard implementations for Stacks and Deques, the others using vectors as backend storage.
//Stack.h
#ifndef STACK_H
#define STACK_H
#include "LL.h"
template <typename T> class Stack {
private:
// using a LinkedList as the storage for this Stack
LinkedList<T> & data;
public:
// constructor
Stack ():
data {*(new LinkedList<T>())} {}
// accessors -----------------------------------------------------
// returns a copy of the pointer to the local data variable
LinkedList<T>& getData() const {
return data;
}
void printStack() const {
data.printList();
}
// return first element of stack without removing
T peek() const {
// CODE HERE
return T {}; // PLACEHOLDER FOR COMPILING
}
// mutators ------------------------------------------------------
// remove the element off the top of the stack and return it. If
// the stack is empty, return the empty constructor for type T.
T pop(){
// CODE HERE
return T {}; // PLACEHOLDER FOR COMPILING
}
// push item thing of type T onto the stack
void push(T thing) {
// CODE HERE
}
};
#endif
//LL.h
#ifndef LL_H
#define LL_H
#include <iostream>
// A template class takes in a type in the <>. Look at how we declare a vector
// with: vector<int> thing, there the <int> is the template type.
template <typename T> class LinkedList {
private:
// private struct for the LL
struct Node {
T data;
Node* next;
Node* prev;
Node(): // <- this is called an initializer list, the most common
// way to write constructors since C++11
data { T{} },
next {nullptr},
prev {nullptr} {};
explicit Node(const T & _dataMember): // <- the explicit means we
// can't pass in any extra values to this function or do
// implicit type casting – important only because this is
// allowed in C
data {_dataMember},
next {nullptr},
prev {nullptr} {};
explicit Node(const T && _dataMember):
data {_dataMember},
next {nullptr},
prev {nullptr} {};
};
Node* head; // head pointer: first Node in the LinkedList
Node* tail; // tail pointer: last Node in the LinkedList
int size; // int to keep the size of the list; should be modified
// as the data structure changes size
// checks if a given k is within the size of indices in LinkedList
// returns true if 0 <= k < size,
// false otherwise
bool kWithinBounds(int k) const {
if (k >= 0 && k < size){
return true;
}
return false;
}
// will return the kth Node in the LinkedList. This is private
// because we don't want to support this function for outside
// classes, this is just for internal usage
Node* getKthNode(int k) const {
// CODE HERE
return nullptr; // PLACEHOLDER FOR COMPILING
}
public:
// constructor/destructor
LinkedList(): // default values for LinkedList
head {nullptr},
tail {nullptr},
size {0} {};
~LinkedList(){ // calls a defined function empty() to clean up all
// memory in the LinkedList (delete all allocated memory)
empty();
}
// copy constructor -- note that this does a /deep/ copy
LinkedList (const LinkedList<T> & other):
head {nullptr}, tail {nullptr}, size {0} {
Node* temp = other.head;
while (temp != nullptr){
this->add(temp->data);
temp = temp->next;
}
}
// copy assignment operator
LinkedList& operator= (const LinkedList & other){
LinkedList copy = other;
std::swap(*this,copy);
return *this;
}
// move constructor
LinkedList (LinkedList<T> && other):
head {other.head}, tail {other.tail}, size {other.size} {
other.head = other.tail = nullptr;
other.size = 0;
}
// move assignment operator
LinkedList& operator= (LinkedList<T> && other){
std::swap(head, other.head);
std::swap(tail, other.tail);
std::swap(size, other.size);
return *this;
}
// accessors ----------------------------------------------
// returns the data stored in the tail Node
T getHead() const {
if (head != nullptr){
return head->data;
} else {
return T {};
}
}
// returns the data stored in the tail Node
T getTail() const {
if (tail != nullptr){
return tail->data;
} else {
return T {};
}
}
// returns the number of nodes in the list.
int getSize() const {
return size;
}
// will return the index of the item in the list, if it
// is found. If not, return -1.
int member(T dataMember) const {
// CODE HERE
return -1; // PLACEHOLDER
}
// returns the data at index j
T* findKth(int j) const {
// CODE HERE
return nullptr; // PLACEHOLDER
}
void printList() const {
Node* tmp = head;
std::cout << "[";
while (tmp != nullptr){
if (tmp->next != nullptr){
std::cout << tmp->data << ", ";
} else {
std::cout << tmp->data;
}
tmp = tmp->next;
}
std::cout << "]" << std::endl;
}
void printListBackwards() const {
Node* tmp = tail;
std::cout << "[";
while (tmp != nullptr){
if (tmp->prev != nullptr){
std::cout << tmp->data << ", ";
} else {
std::cout << tmp->data;
}
tmp = tmp->prev;
}
std::cout << "]" << std::endl;
}
// mutators -------------------------------------------------
// inserts at the first position, replacing the old head pointer
void insert(const T dataMember) {
// CODE HERE
}
// takes a T var called dataMember and makes it the kth
// value in the list, its next pointing to the node
// previously at the kth position. If k is out of range, don't
// insert anything.
// Note you can never insert at a position outside the
// size of the list, so no inserting at the end with
// this function.
void insertAtK(T dataMember, int k){
// CODE HERE
}
// insert at the end of the list
void add(T dataMember){
Node* temp = new Node(dataMember);
if (!head){
head = temp;
tail = temp;
} else {
tail->next = temp;
temp->prev = tail;
temp->next = nullptr;
tail = temp;
}
size++;
}
// deletes memory at head, sets head to be the prev node, or
// nullptr if only one node in list.
void removeHead(){
if (head != nullptr){
if (tail == head){ // if only one node
delete head;
head = tail = nullptr;
} else {
Node* temp = head;
head = head->next;
head->prev = nullptr;
delete temp;
}
size--;
}
}
// deletes memory at tail, sets tail to be the prev node, or
// nullptr if only one node in list.
void removeTail(){
// CODE HERE
}
// removes the kth item in the list
void removeAtK(int k){
// CODE HERE
}
// free all memory in the list with delete and reset
// head, tail and size.
void empty(){
// CODE HERE
}
};
#endif
Explanation / Answer
here is your answer : --------->>>>>>>>
LL.h : ----------->>>>>>>>
#ifndef LL_H
#define LL_H
#include<iostream>
using namespace std;
// A template class takes in a type in the <>. Look at how we declare a vector
// with: vector thing, there the is the template type.
template<typename T>
class LinkedList {
private:
// private struct for the LL
struct Node {
T data;
Node* next;
Node* prev;
Node(): // <- this is called an initializer list, the most common
// way to write constructors since C++11
data { T{} },
next {nullptr},
prev {nullptr} {};
explicit Node(const T & _dataMember): // <- the explicit means we
// can't pass in any extra values to this function or do
// implicit type casting – important only because this is
// allowed in C
data {_dataMember},
next {nullptr},
prev {nullptr} {};
explicit Node(const T && _dataMember):
data {_dataMember},
next {nullptr},
prev {nullptr} {};
};
Node* head; // head pointer: first Node in the LinkedList
Node* tail; // tail pointer: last Node in the LinkedList
int size; // int to keep the size of the list; should be modified
// as the data structure changes size
// checks if a given k is within the size of indices in LinkedList
// returns true if 0 <= k < size,
// false otherwise
bool kWithinBounds(int k) const {
if (k >= 0 && k < size){
return true;
}
return false;
}
// will return the kth Node in the LinkedList. This is private
// because we don't want to support this function for outside
// classes, this is just for internal usage
Node* getKthNode(int k) const {
// CODE HERE
if(k < 0 || k >= size){
return nullptr;
}
Node *cur = head;
for(int i = 0;i<k;i++){
cur = cur->next;
}
return cur;
}
public:
// constructor/destructor
LinkedList(): // default values for LinkedList
head {nullptr},
tail {nullptr},
size {0} {};
~LinkedList(){ // calls a defined function empty() to clean up all
// memory in the LinkedList (delete all allocated memory)
empty();
}
// copy constructor -- note that this does a /deep/ copy
LinkedList (const LinkedList & other):
head {nullptr}, tail {nullptr}, size {0} {
Node* temp = other.head;
while (temp != nullptr){
this->add(temp->data);
temp = temp->next;
}
}
// copy assignment operator
LinkedList& operator= (const LinkedList & other){
LinkedList copy = other;
std::swap(*this,copy);
return *this;
}
// move constructor
LinkedList (LinkedList && other):
head {other.head}, tail {other.tail}, size {other.size} {
other.head = other.tail = nullptr;
other.size = 0;
}
// move assignment operator
LinkedList& operator= (LinkedList && other){
std::swap(head, other.head);
std::swap(tail, other.tail);
std::swap(size, other.size);
return *this;
}
// accessors ----------------------------------------------
// returns the data stored in the tail Node
T getHead() const {
if (head != nullptr){
return head->data;
} else {
return T {};
}
}
// returns the data stored in the tail Node
T getTail() const {
if (tail != nullptr){
return tail->data;
} else {
return T {};
}
}
// returns the number of nodes in the list.
int getSize() const {
return size;
}
// will return the index of the item in the list, if it
// is found. If not, return -1.
int member(T dataMember) const {
// CODE HERE
int i = 0;
Node *cur = head;
while(cur != tail){
if(cur->data == dataMember){
return i;
}
i++;
cur = cur->next;
}
return -1; // PLACEHOLDER
}
// returns the data at index j
T* findKth(int j) const {
// CODE HERE
Node *cur = getKthNode(j);
if(cur != nullptr){
return &cur->data;
}
return nullptr; // PLACEHOLDER
}
void printList() const {
Node* tmp = head;
std::cout << "[";
while (tmp != nullptr){
if (tmp->next != nullptr){
std::cout << tmp->data << ", ";
} else {
std::cout << tmp->data;
}
tmp = tmp->next;
}
std::cout << "]" << std::endl;
}
void printListBackwards() const {
Node* tmp = tail;
std::cout << "[";
while (tmp != nullptr){
if (tmp->prev != nullptr){
std::cout << tmp->data << ", ";
} else {
std::cout << tmp->data;
}
tmp = tmp->prev;
}
std::cout << "]" << std::endl;
}
// mutators -------------------------------------------------
// inserts at the first position, replacing the old head pointer
void insert(const T dataMember) {
// CODE HERE
Node *temp = new Node(dataMember);
if(head == nullptr){
head = temp;
tail = temp;
size = 1;
return;
}else{
temp->next = head;
head->prev = temp;
head = temp;
size++;
return;
}
}
// takes a T var called dataMember and makes it the kth
// value in the list, its next pointing to the node
// previously at the kth position. If k is out of range, don't
// insert anything.
// Note you can never insert at a position outside the
// size of the list, so no inserting at the end with
// this function.
void insertAtK(T dataMember, int k){
// CODE HERE
Node *cur = getKthNode(k);
if(cur != nullptr){
if(cur == head){
insert(dataMember);
return;
}else if(cur == tail){
Node *temp = new Node(dataMember);
tail->next = temp;
temp->prev = tail;
tail = temp;
size++;
return;
}else{
Node *temp = new Node(dataMember);
temp->prev = cur->prev;
cur->prev->next = temp;
temp->next = cur;
cur->prev = temp;
size++;
return;
}
}
}
// insert at the end of the list
void add(T dataMember){
Node* temp = new Node(dataMember);
if (!head){
head = temp;
tail = temp;
} else {
tail->next = temp;
temp->prev = tail;
temp->next = nullptr;
tail = temp;
}
size++;
}
// deletes memory at head, sets head to be the prev node, or
// nullptr if only one node in list.
void removeHead(){
if (head != nullptr){
if (tail == head){ // if only one node
delete head;
head = tail = nullptr;
} else {
Node* temp = head;
head = head->next;
head->prev = nullptr;
delete temp;
}
size--;
}
}
// deletes memory at tail, sets tail to be the prev node, or
// nullptr if only one node in list.
void removeTail(){
// CODE HERE
if(head == nullptr){
return;
}
if(head == tail){
delete head;
head = tail = nullptr;
size = 0;
}else{
Node *cur = tail;
tail = cur->prev;
tail->next = nullptr;
delete cur;
size--;
}
}
// removes the kth item in the list
void removeAtK(int k){
// CODE HERE
if(head == nullptr){
return;
}
Node *cur = getKthNode(k);
if(cur != nullptr){
if(cur == head){
removeHead();
}else if(cur == tail){
removeTail();
}else{
cur->prev->next = cur->next;
cur->next->prev = cur->prev;
size--;
}
}
}
// free all memory in the list with delete and reset
// head, tail and size.
void empty(){
// CODE HERE
if(head != nullptr){
Node *cur = head;
while(cur != nullptr){
cur = cur->next;
if(cur != nullptr)
delete cur->prev;
}
if(tail != nullptr){
delete tail;
}
head = tail = nullptr;
size = 0;
}
}
};
#endif
Stack.h : ----------->>>>>>>>
#ifndef STACK_H
#define STACK_H
#include "LL.h"
template<typename T>
class Stack {
private:
// using a LinkedList as the storage for this Stack
LinkedList<T> data;
public:
// constructor
Stack ():
data {(new LinkedList<T>())} {}
// accessors -----------------------------------------------------
// returns a copy of the pointer to the local data variable
LinkedList<T>& getData() const {
return data;
}
void printStack() const {
data.printList();
}
// return first element of stack without removing
T peek() const {
// CODE HERE
return data.getHead(); // PLACEHOLDER FOR COMPILING
}
// mutators ------------------------------------------------------
// remove the element off the top of the stack and return it. If
// the stack is empty, return the empty constructor for type T.
T pop(){
// CODE HERE
T d = data.getHead();
data.removeHead();
return d;
// PLACEHOLDER FOR COMPILING
}
// push item thing of type T onto the stack
void push(T thing) {
// CODE HERE
data.insert(thing);
}
};
#endif
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.