This is probably the last time I will post this data structure that I have been working on. I have added in an iterator and const_iterator class (although I do not use them probably where I should be). I also did not follow another persons advice to add emplace, emplace_front, and emplace_back simply because I have no idea how nor can I find any code to refer to online.
The idea of this post is to gain more insight in what I need to change in my class most likely with the additional classes I have added i.e. iterator and const_iterator. This is my first time implementing an iterator class and to be honest I am not sure where to change my code to use iterator and where not to.
I want to again thank the community for helping me I really appreciate the effort.
Here is my header file:
#ifndef SINGLELINKEDLIST_h
#define SINGLELINKEDLIST_h
template <class T>
class SingleLinkedList {
private:
struct Node {
T data;
std::unique_ptr<Node> next = nullptr;
// disable if noncopyable<T> for cleaner error msgs
explicit Node(const T& x, std::unique_ptr<Node>&& p = nullptr)
: data(x)
, next(std::move(p)) {}
// disable if nonmovable<T> for cleaner error msgs
explicit Node(T&& x, std::unique_ptr<Node>&& p = nullptr)
: data(std::move(x))
, next(std::move(p)) {}
};
std::unique_ptr<Node> head = nullptr;
Node* tail = nullptr;
void do_pop_front() {
head = std::move(head->next);
}
public:
// Constructors
SingleLinkedList() = default; // empty constructor
SingleLinkedList(SingleLinkedList const &source); // copy constructor
// Rule of 5
SingleLinkedList(SingleLinkedList &&move) noexcept; // move constructor
SingleLinkedList& operator=(SingleLinkedList &&move) noexcept; // move assignment operator
~SingleLinkedList();
// Overload operators
SingleLinkedList& operator=(SingleLinkedList const &rhs);
// Memeber functions
void swap(SingleLinkedList &other) noexcept;
bool empty() const { return head.get() == nullptr; }
int size() const;
void push_back(const T &theData);
void push_back(T &&theData);
void push_front(const T &theData);
void push_front(T &&theData);
void insert(int pos, const T &theData);
void clear();
void pop_front();
void pop_back();
void delete_specific(int delValue);
bool search(const T &x);
// Create an iterator class
class iterator;
iterator begin();
iterator end();
// Create const iterator class
class const_iterator;
const_iterator cbegin() const;
const_iterator cend() const;
const_iterator begin() const;
const_iterator end() const;
};
template <class T>
SingleLinkedList<T>::SingleLinkedList(SingleLinkedList<T> const &source) {
for(Node* loop = source.head.get(); loop != nullptr; loop = loop->next.get()) {
push_back(loop->data);
}
}
template <class T>
SingleLinkedList<T>::SingleLinkedList(SingleLinkedList<T>&& move) noexcept {
move.swap(*this);
}
template <class T>
SingleLinkedList<T>& SingleLinkedList<T>::operator=(SingleLinkedList<T> &&move) noexcept {
move.swap(*this);
return *this;
}
template <class T>
SingleLinkedList<T>::~SingleLinkedList() {
clear();
}
template <class T>
void SingleLinkedList<T>::clear() {
while (head) {
do_pop_front();
}
}
template <class T>
SingleLinkedList<T>& SingleLinkedList<T>::operator=(SingleLinkedList const &rhs) {
SingleLinkedList copy{ rhs };
swap(copy);
return *this;
}
template <class T>
void SingleLinkedList<T>::swap(SingleLinkedList &other) noexcept {
using std::swap;
swap(head, other.head);
swap(tail, other.tail);
}
template <class T>
int SingleLinkedList<T>::size() const {
int size = 0;
for (auto current = head.get(); current != nullptr; current = current->next.get()) {
size++;
}
return size;
}
template <class T>
void SingleLinkedList<T>::push_back(const T &theData) {
std::unique_ptr<Node> newNode = std::make_unique<Node>(theData);
if (!head) {
head = std::move(newNode);
tail = head.get();
}
else {
tail->next = std::move(newNode);
tail = tail->next.get();
}
}
template <class T>
void SingleLinkedList<T>::push_back(T &&thedata) {
std::unique_ptr<Node> newnode = std::make_unique<Node>(std::move(thedata));
if (!head) {
head = std::move(newnode);
tail = head.get();
}
else {
tail->next = std::move(newnode);
tail = tail->next.get();
}
}
template <class T>
void SingleLinkedList<T>::push_front(const T &theData) {
std::unique_ptr<Node> newNode = std::make_unique<Node>(theData);
newNode->next = std::move(head);
head = std::move(newNode);
if (!tail) {
tail = head.get();
}
}
template <class T>
void SingleLinkedList<T>::push_front(T &&theData) {
std::unique_ptr<Node> newNode = std::make_unique<Node>(std::move(theData));
newNode->next = std::move(head);
head = std::move(newNode);
if (!tail) {
tail = head.get();
}
}
template <class T>
void SingleLinkedList<T>::insert(int pos, const T &theData) {
if (pos < 0) {
throw std::out_of_range("The insert location is invalid.");
}
auto node = head.get();
int i = 0;
for (; node && node->next && i < pos; node = node->next.get(), i++);
auto newNode = std::make_unique<Node>(theData);
if (node) {
newNode->next = std::move(node->next);
if (!newNode->next) tail = newNode.get(); // created in case we insert after the current tail
node->next = std::move(newNode);
}
else {
head = std::move(newNode);
tail = head.get();
}
}
template <class T>
void SingleLinkedList<T>::pop_front() {
if (empty()) {
throw std::out_of_range("List is Empty!!! Deletion is not possible.");
}
do_pop_front();
}
template <class T>
void SingleLinkedList<T>::pop_back() {
if (!head) return;
auto current = head.get();
Node* previous = nullptr;
while (current->next) {
previous = current;
current = current->next.get();
}
if (previous) {
previous->next = nullptr;
}
else {
head = nullptr;
}
tail = previous;
previous->next = nullptr;
}
template <class T>
void SingleLinkedList<T>::delete_specific(int delValue) {
if (!head.get()) {
throw std::out_of_range("List is Empty!!! Deletion is not possible.");
}
auto temp1 = head.get();
Node* temp2 = nullptr;
while (temp1->data != delValue) {
if (temp1->next == nullptr) {
throw std::invalid_argument("Given node not found in the list!!!");
}
temp2 = temp1;
temp1 = temp1->next.get();
}
temp2->next = std::move(temp1->next);
}
template <class T>
bool SingleLinkedList<T>::search(const T &x) {
return std::find(begin(), end(), x) != end();
}
template <typename T>
std::ostream& operator<<(std::ostream &str, SingleLinkedList<T>& list) {
for (auto const& item : list) {
str << item << "\t";
}
return str;
}
template <class T>
class SingleLinkedList<T>::iterator {
Node* node = nullptr;
public:
using iterator_category = std::forward_iterator_tag;
using value_type = T;
using difference_type = std::ptrdiff_t;
using pointer = T * ;
using reference = T & ;
iterator(Node *node = nullptr) : node(node) {}
bool operator!=(const iterator& other) const { return node != other.node; }
bool operator==(const iterator& other) const { return node == other.node; }
T& operator*() const { return node->data; }
T& operator->() const { return node->data; }
iterator& operator++() { node = node->next.get(); return *this; }
};
template <class T>
class SingleLinkedList<T>::const_iterator {
Node* node = nullptr;
public:
using iterator_category = std::forward_iterator_tag;
using value_type = T;
using difference_type = std::ptrdiff_t;
using pointer = T * ;
using reference = T & ;
const_iterator(Node *node = nullptr) : node(node) {}
bool operator!=(const iterator& other) const { return node != other.node; }
bool operator==(const iterator& other) const { return node == other.node; }
const T& operator*() const { return node->data; }
const T& operator->() const { return node->data; }
const_iterator& operator++() { node = node->next.get(); return *this; }
};
template<class T>
typename SingleLinkedList<T>::iterator SingleLinkedList<T>::begin() {
return head.get();
}
template<class T>
typename SingleLinkedList<T>::iterator SingleLinkedList<T>::end() {
return {};
}
template <class T>
typename SingleLinkedList<T>::const_iterator SingleLinkedList<T>::begin() const {
return head.get();
}
template <class T>
typename SingleLinkedList<T>::const_iterator SingleLinkedList<T>::end() const {
return {};
}
template <class T>
typename SingleLinkedList<T>::const_iterator SingleLinkedList<T>::cbegin() const {
return head.get();
}
template <class T>
typename SingleLinkedList<T>::const_iterator SingleLinkedList<T>::cend() const {
return {};
}
#endif /* SingleLinkedList_h*/
Here is my main.cpp file:
#include <iostream>
#include <iterator>
#include <memory>
#include <utility>
#include <stdexcept>
#include <iosfwd>
#include <stdexcept>
#include <ostream>
#include "SingleLinkedList.h"
#include "DoubleLinkedList.h"
int main(int argc, const char * argv[]) {
///////////////////////////////////////////////////////////////////////
///////////////////////////// Single Linked List //////////////////////
///////////////////////////////////////////////////////////////////////
SingleLinkedList<int> obj;
obj.push_back(2);
obj.push_back(4);
obj.push_back(6);
obj.push_back(8);
obj.push_back(10);
std::cout<<"\n--------------------------------------------------\n";
std::cout<<"---------------displaying all nodes---------------";
std::cout<<"\n--------------------------------------------------\n";
std::cout << obj << "\n";
std::cout<<"\n--------------------------------------------------\n";
std::cout<<"----------------Inserting At Start----------------";
std::cout<<"\n--------------------------------------------------\n";
obj.push_front(50);
std::cout << obj << "\n";
std::cout<<"\n--------------------------------------------------\n";
std::cout<<"-------------inserting at particular--------------";
std::cout<<"\n--------------------------------------------------\n";
obj.insert(5,60);
std::cout << obj << "\n";
std::cout << "\n--------------------------------------------------\n";
std::cout << "-------------Get current size ---=--------------------";
std::cout << "\n--------------------------------------------------\n";
std::cout << obj.size() << "\n";
std::cout<<"\n--------------------------------------------------\n";
std::cout<<"----------------deleting at start-----------------";
std::cout<<"\n--------------------------------------------------\n";
obj.pop_front();
std::cout << obj << "\n";
std::cout<<"\n--------------------------------------------------\n";
std::cout<<"----------------deleting at end-----------------------";
std::cout<<"\n--------------------------------------------------\n";
obj.pop_back();
std::cout << obj << "\n";
std::cout<<"\n--------------------------------------------------\n";
std::cout<<"--------------Deleting At Particular--------------";
std::cout<<"\n--------------------------------------------------\n";
obj.delete_specific(4);
std::cout << obj << "\n";
obj.search(8) ? printf("yes"):printf("no");
std::cout << "\n--------------------------------------------------\n";
std::cout << "--------------Testing copy----------------------------";
std::cout << "\n--------------------------------------------------\n";
SingleLinkedList<int> obj1 = obj;
std::cout << obj1 << "\n";
std::cin.get();
}
Here is also the following post I made here
