Question

What is the specific answer for 1. and 2. Thanks!

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.

2. Write the method definition/implementation.

Test by running the main() function below and capture the console screen output, by attaching it as a captured image (use CTRL+PrtSc) or printed out as a file.

#include <iostream>

#include "SinglyLinkedList.hpp"

using std::cout;

using std::endl;

int main() {

SinglyLinkedList<int> ds;

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

   ds.append(i);

Node<int> *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;

}

----

CODE for SinglyLinkedList:

#pragma once
	#include <stdexcept>
	template<typename T>
	struct Node {
	T data;
	Node<T>* next;
	Node() = delete; // Intentionally no default constructor
	Node( const T & element ) : data( element ), next( nullptr ) {}
	};
	template<typename T>
	class SinglyLinkedList {
	private:
	Node<T>* head;
	Node<T>* 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<T>*, const T& );
	void removeAfter( Node<T>* );
	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<typename T>
	SinglyLinkedList<T>::SinglyLinkedList() : head( nullptr ), tail( nullptr ) {}
	template<typename T>
	bool SinglyLinkedList<T>::empty() {
	return head == nullptr;
	}
	template<typename T>
	void SinglyLinkedList<T>::append( const T& newData ) {
	Node<T> * newNode = new Node<T>( newData ); // create new node
	if (head == nullptr) { // List empty
	head = newNode;
	tail = newNode;
	}
	else{
	tail->next = newNode;
	tail = newNode;
	}
	}
	template<typename T>
	void SinglyLinkedList<T>::prepend( const T& newData ) {
	Node<T> * newNode = new Node<T>( newData ); // create new node
	if (head == nullptr) { // list empty
	head = newNode;
	tail = newNode;
	}
	else {
	newNode->next = head;
	head = newNode;
	}
	}
	template<typename T>
	void SinglyLinkedList<T>::insertAfter(Node<T>* curNode, const T& newData) {
	// Construct new node
	Node<T>* newNode = new Node<T>( 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<typename T>
	void SinglyLinkedList<T>::removeAfter(Node<T>* curNode) {
	if( empty() ) throw std::length_error( "empty list" );
	// Special case, remove head
	if (curNode == nullptr && head != nullptr) {
	Node<T> *sucNode = head->next;
	head = sucNode;
	if (sucNode == nullptr) { // Removed last item
	tail = nullptr;
	}
	}
	else if (curNode->next != nullptr) {
	Node<T> *sucNode = curNode->next->next;
	curNode->next = sucNode;
	if (sucNode == nullptr) { // Removed tail
	tail = curNode;
	}
	}
	}
	template <typename T>
	void SinglyLinkedList<T>::pop_front() {
	removeAfter(nullptr);
	}
	template <typename T>
	T& SinglyLinkedList<T>::front() {
	if( empty() ) throw std::length_error( "empty list" );
	return head->data;
	}
	template <typename T>
	T& SinglyLinkedList<T>::back() {
	if( empty() ) throw std::length_error( "empty list" );
	return tail->data;
	}
	template<typename T>
	void SinglyLinkedList<T>::clear() {
	while( !empty() )
	pop_front();
	}
	template<typename T>
	SinglyLinkedList<T>::~SinglyLinkedList() {
	clear();
	}
	template <typename T>
	SinglyLinkedList<T>::SinglyLinkedList( const SinglyLinkedList<T> & original ) : SinglyLinkedList() {
	// Walk the original list adding copies of the elements to this list maintaining order
	for( Node<T> * position = original.head; position != nullptr; position = position->next ) {
	append( position->data );
	}
	}
	template <typename T>
	SinglyLinkedList<T> & SinglyLinkedList<T>::operator=( const SinglyLinkedList<T> & 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<T> * position = rhs.head; position != nullptr; position = position->next ) {
	append( position->data );
	}
	}
	return *this;
	}

Answer 1

// SinglyLinkedList.hpp

#pragma once

#include <stdexcept>

template<typename T>

struct Node {

T data;

Node<T>* next;

Node() = delete; // Intentionally no default constructor

Node( const T & element ) : data( element ), next( nullptr ) {}

};

template<typename T>

class SinglyLinkedList {

private:

Node<T>* head;

Node<T>* 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<T>*, const T& );

void removeAfter( Node<T>* );

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();

Node<T> *find(T data);// return the node containing the data, else nullptr if data not present

};

template<typename T>

SinglyLinkedList<T>::SinglyLinkedList() : head( nullptr ), tail( nullptr ) {}

template<typename T>

bool SinglyLinkedList<T>::empty() {

return head == nullptr;

}

template<typename T>

void SinglyLinkedList<T>::append( const T& newData ) {

Node<T> * newNode = new Node<T>( newData ); // create new node

if (head == nullptr) { // List empty

head = newNode;

tail = newNode;

}

else{

tail->next = newNode;

tail = newNode;

}

}

template<typename T>

void SinglyLinkedList<T>::prepend( const T& newData ) {

Node<T> * newNode = new Node<T>( newData ); // create new node

if (head == nullptr) { // list empty

head = newNode;

tail = newNode;

}

else {

newNode->next = head;

head = newNode;

}

}

template<typename T>

void SinglyLinkedList<T>::insertAfter(Node<T>* curNode, const T& newData) {

// Construct new node

Node<T>* newNode = new Node<T>( 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<typename T>

void SinglyLinkedList<T>::removeAfter(Node<T>* curNode) {

if( empty() ) throw std::length_error( "empty list" );

// Special case, remove head

if (curNode == nullptr && head != nullptr) {

Node<T> *sucNode = head->next;

head = sucNode;

if (sucNode == nullptr) { // Removed last item

tail = nullptr;

}

}

else if (curNode->next != nullptr) {

Node<T> *sucNode = curNode->next->next;

curNode->next = sucNode;

if (sucNode == nullptr) { // Removed tail

tail = curNode;

}

}

}

template <typename T>

void SinglyLinkedList<T>::pop_front() {

removeAfter(nullptr);

}

template <typename T>

T& SinglyLinkedList<T>::front() {

if( empty() ) throw std::length_error( "empty list" );

return head->data;

}

template <typename T>

T& SinglyLinkedList<T>::back() {

if( empty() ) throw std::length_error( "empty list" );

return tail->data;

}

template<typename T>

void SinglyLinkedList<T>::clear() {

while( !empty() )

pop_front();

}

template<typename T>

SinglyLinkedList<T>::~SinglyLinkedList() {

clear();

}

template <typename T>

SinglyLinkedList<T>::SinglyLinkedList( const SinglyLinkedList<T> & original ) : SinglyLinkedList() {

// Walk the original list adding copies of the elements to this list maintaining order

for( Node<T> * position = original.head; position != nullptr; position = position->next ) {

append( position->data );

}

}

template <typename T>

SinglyLinkedList<T> & SinglyLinkedList<T>::operator=( const SinglyLinkedList<T> & 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<T> * position = rhs.head; position != nullptr; position = position->next ) {

append( position->data );

}

}

return *this;

}

template <typename T>

Node<T>*::SinglyLinkedList<T>:: find(T data)

{

       Node<T> *curr = head;

       while(curr != nullptr)

       {

             if(curr->data == data)

                    return curr;

             curr = curr->next;

       }

       return nullptr;

}

//end of SinglyLinkedList.hpp

#include <iostream>

#include "SinglyLinkedList.hpp"

using std::cout;

using std::endl;

int main() {

SinglyLinkedList<int> ds;

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

   ds.append(i);

Node<int> *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;

}

Output: