Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

Use the class below #pragma once #include template struct Node { T data; Node * next; Node() = delete; // Intentionally no default constructor Node(

Use the class below

#pragma once
#include
template
struct Node {
T data;
Node* next;
Node() = delete; // Intentionally no default constructor
Node( const T & element ) : data( element ), next( nullptr ) {}
};
template
class SinglyLinkedList {
private:
Node* head;
Node* tail;
public:
// Constructors
SinglyLinkedList();
SinglyLinkedList(const SinglyLinkedList&);
SinglyLinkedList& operator=(const SinglyLinkedList&); // assignment operator
~SinglyLinkedList(); // destructor
// Getters / Setters
bool empty();
int size() = delete; // INTENTIONALLY NOT IMPLEMENTED !!
void append( const T& );
void prepend( const T& );
void insertAfter( Node*, const T& );
void removeAfter( Node* );
void pop_front(); // remove element at front of list
T& front(); // return list's front element
T& back(); // return list's back element
void clear();
};
template
SinglyLinkedList::SinglyLinkedList() : head( nullptr ), tail( nullptr ) {}
template
bool SinglyLinkedList::empty() {
return head == nullptr;
}
template
void SinglyLinkedList::append( const T& newData ) {
Node * newNode = new Node( newData ); // create new node
if (head == nullptr) { // List empty
head = newNode;
tail = newNode;
}
else{
tail->next = newNode;
tail = newNode;
}
}
template
void SinglyLinkedList::prepend( const T& newData ) {
Node * newNode = new Node( newData ); // create new node
if (head == nullptr) { // list empty
head = newNode;
tail = newNode;
}
else {
newNode->next = head;
head = newNode;
}
}
template
void SinglyLinkedList::insertAfter(Node* curNode, const T& newData) {
// Construct new node
Node* newNode = new Node( newData );
if (head == nullptr) { // List empty
head = newNode;
tail = newNode;
} else if (curNode == tail) { // Insert after tail
tail->next = newNode;
tail = newNode;
} else {
newNode->next = curNode->next;
curNode->next = newNode;
}
}
template
void SinglyLinkedList::removeAfter(Node* curNode) {
if( empty() ) throw std::length_error( "empty list" );
// Special case, remove head
if (curNode == nullptr && head != nullptr) {
Node *sucNode = head->next;
head = sucNode;
if (sucNode == nullptr) { // Removed last item
tail = nullptr;
}
}
else if (curNode->next != nullptr) {
Node *sucNode = curNode->next->next;
curNode->next = sucNode;
if (sucNode == nullptr) { // Removed tail
tail = curNode;
}
}
}
template
void SinglyLinkedList::pop_front() {
removeAfter(nullptr);
}
template
T& SinglyLinkedList::front() {
if( empty() ) throw std::length_error( "empty list" );
return head->data;
}
template
T& SinglyLinkedList::back() {
if( empty() ) throw std::length_error( "empty list" );
return tail->data;
}
template
void SinglyLinkedList::clear() {
while( !empty() )
pop_front();
}
template
SinglyLinkedList::~SinglyLinkedList() {
clear();
}
template
SinglyLinkedList::SinglyLinkedList( const SinglyLinkedList & original ) : SinglyLinkedList() {
// Walk the original list adding copies of the elements to this list maintaining order
for( Node * position = original.head; position != nullptr; position = position->next ) {
append( position->data );
}
}
template
SinglyLinkedList & SinglyLinkedList::operator=( const SinglyLinkedList & rhs ) {
if( this != &rhs ) // avoid self assignment
{
// Release the contents of this list first
clear(); // An optimization might be possible by reusing already allocated nodes
// Walk the right hand side list adding copies of the elements to this list maintaining order
for( Node * position = rhs.head; position != nullptr; position = position->next ) {
append( position->data );
}
}
return *this;
}

Add a new method, find, to class SinglyLinkedList (defined here) that takes as input a data value and returns a pointer to a node. If the input data is present in the linked list, the returned pointer should point to that node; if not, the returned pointer is nullptr.

  1. Write the (single line) method declaration/specification.

  1. Write the method definition/implementation.

Main function to test

#include

#include "SinglyLinkedList.hpp"

using std::cout;

using std::endl;

int main() {

SinglyLinkedList ds;

for (int i=10; i<20; i++)

ds.append(i);

Node *ptr = ds.find(15);

if (ptr != nullptr)

cout << "Found: " << ptr->data << " matches " << 15 << endl;

else

cout << "15 not found" << endl;

ptr = ds.find(30);

if (ptr != nullptr)

cout << "Found: " << ptr->data << " matches " << 30 << endl;

else

cout << "30 not found" << endl;

return 0;

}

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Pro PowerShell For Database Developers

Authors: Bryan P Cafferky

1st Edition

1484205413, 9781484205419

More Books

Students also viewed these Databases questions