As a classic first data structures assignment, you will take the skeleton code p
ID: 3907985 • Letter: A
Question
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.
I need some help with this lab. I get the concepts and idea but the syntax is what i always struggle with. any help would be greatly appreciated. I need the code for the areas marked "CODE HERE". There are three different sections I need help with: LL.h, Stack.h, and Deque.h. Thanks again.
LL.h
#ifndef LL_H
#define LL_H
#include
// 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 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 & 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
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
Stack.h
#ifndef STACK_H
#define STACK_H
#include "LL.h"
template class Stack {
private:
// using a LinkedList as the storage for this Stack
LinkedList & data;
public:
// constructor
Stack ():
data {*(new LinkedList())} {}
// accessors -----------------------------------------------------
// returns a copy of the pointer to the local data variable
LinkedList& 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
Deque.h
#ifndef DEQUE_H
#define DEQUE_H
#include "LL.h"
template class Deque {
private:
// using a LinkedList as the storage for this Deque
LinkedList& data;
public:
Deque():
data {*(new LinkedList())} {}
// accessors -----------------------------------------------------
LinkedList& getData() const {
return data;
}
// for your testing purposes - should print out each element of
// the deque without destroying the original deque
void printDeque() const {
data.printList();
}
// returns the back element
T getBack() const {
// CODE HERE
return T {}; // PLACEHOLDER FOR COMPILING
}
// returns the front element
T getFront() const {
// CODE HERE
return T {}; // PLACEHOLDER FOR COMPILING
}
// inserts element thing at back of Deque
void pushBack(T thing){
// CODE HERE
}
// inserts element thing at front of Deque
void pushFront(T thing){
// CODE HERE
}
// removes element at back of Deque and returns it
T popBack(){
// CODE HERE
return T {}; // PLACEHOLDER FOR COMPILING
}
// removes element at front of Deque and returns it
T popFront(){
// CODE HERE
return T {}; // PLACEHOLDER FOR COMPILING
}
};
#endif
Explanation / Answer
#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<class 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
-------------------------------------------------------
#ifndef STACK_H
#define STACK_H
#include "LL.h"
template<class 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
-------------------------------------
#ifndef DEQUE_H
#define DEQUE_H
#include "LL.h"
template<class T>
class Deque {
private:
// using a LinkedList as the storage for this Deque
LinkedList<T> data;
public:
Deque():
data {(new LinkedList<T>())} {}
// accessors -----------------------------------------------------
LinkedList<T>& getData() const {
return data;
}
// for your testing purposes - should print out each element of
// the deque without destroying the original deque
void printDeque() const {
data.printList();
}
// returns the back element
T getBack() const {
// CODE HERE
return data.getTail();
// PLACEHOLDER FOR COMPILING
}
// returns the front element
T getFront() const {
// CODE HERE
return data.getHead(); // PLACEHOLDER FOR COMPILING
}
// inserts element thing at back of Deque
void pushBack(T thing){
// CODE HERE
data.add(thing);
}
// inserts element thing at front of Deque
void pushFront(T thing){
// CODE HERE
data.insert(thing);
}
// removes element at back of Deque and returns it
T popBack(){
// CODE HERE
T d = data.getTail();
data.removeTail();
return d; // PLACEHOLDER FOR COMPILING
}
// removes element at front of Deque and returns it
T popFront(){
// CODE HERE
T d = data.getHead();
data.rmoveHead();
return d; // PLACEHOLDER FOR COMPILING
}
};
#endif
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.