Below is the code I wrote to implement a singly linked list. To keep things simple, I omitted things like copy constructor. Aside from general feedback, here are some specifics I would like addressed:
- C++20 features
- Did I implement iterators correctly? Should I add anything to the iterators (e.g., different types of iterators)?
- Can/should I use smart pointers for the
nextpointers? - Can/should I split the namespace blocks into different header files? I split the implementation of different classes' member function into different namespace blocks, but it still feels cluttered when they are put in the same file.
- When printing single characters to cout, should I enclose them in single or double quotes? I remember reading that double quotes are better since character literals are converted to string literals anyways, but I can't seem to find information on this at the moment.
- If I remove the forward declaration of
operator<<()in line 14, I get a compile error related to line 83. Why do I need to forward declare the template? I know you don't have to forward declare it if the function is not a template.
SinglyLinkedList.hpp:
#pragma once
#include <iostream> // for type of cout
#include <stdexcept> // for std::out_of_range
#include <cstddef> // for std::size_t
namespace Custom_SLL { // member functions are defined in separate namespace blocks
template <typename T>
class SinglyLinkedList; // forward declaration necessary for `friend class
// SinglyLinkedList<T>` in `Node`'s definition.
template <typename T>
class Iterator; // forward declaration needed for the same reason
template <typename T>
auto operator<<(
decltype(std::cout)& out,
SinglyLinkedList<T>& list
) -> decltype(out)&;
template <typename T>
struct Node {
public:
using nodetype = Node<T>;
using pointertype = nodetype*;
using valuetype = T;
Node(valuetype value, pointertype next)
: value{value}, next{next}
{}
private:
valuetype value{};
pointertype next{nullptr};
friend class SinglyLinkedList<T>;
friend class Iterator<T>;
};
template <typename T>
class Iterator {
public:
using valuetype = T;
using nodetype = Node<T>;
using pointertype = nodetype*;
using iterator = Iterator<T>;
Iterator(pointertype node_p);
auto operator*() -> valuetype&;
auto operator++() -> iterator&;
auto operator+(std::size_t offset) -> iterator;
auto operator==(const iterator& other) -> bool;
auto operator!=(const iterator& other) -> bool;
friend class SinglyLinkedList<T>;
private:
pointertype node_p;
};
template <typename T>
class SinglyLinkedList {
public:
using nodetype = Node<T>;
using pointertype = nodetype*;
using valuetype = T;
using iterator = Iterator<T>;
SinglyLinkedList() = default;
~SinglyLinkedList();
auto empty() const -> bool;
auto addFront(const valuetype& value) -> iterator;
auto insertAfter(iterator& it, const valuetype& value) -> iterator;
// these members are not defined for simplicity:
SinglyLinkedList(const SinglyLinkedList<T>& other) = delete;
SinglyLinkedList(const SinglyLinkedList<T>&& other) = delete;
SinglyLinkedList<T>& operator=(SinglyLinkedList<T>& other) = delete;
SinglyLinkedList<T>& operator=(SinglyLinkedList<T>&& ohter) = delete;
auto removeAfter(iterator& it) -> iterator = delete;
auto begin() -> iterator;
auto end() -> iterator;
friend auto operator<< <>(
decltype(std::cout)& out,
SinglyLinkedList<T>& list
) -> decltype(out)&;
private:
pointertype head{nullptr};
};
}
namespace Custom_SLL { // definitions of Iterator member functions
template <typename T>
Iterator<T>::Iterator(const pointertype node_p) : node_p{node_p}
{}
template <typename T>
auto Iterator<T>::operator*() -> valuetype& {
if (node_p == nullptr) {
throw std::out_of_range("Cannot dereference end iterator");
}
return node_p->value;
}
template <typename T>
auto Iterator<T>::operator++() -> iterator& {
if (node_p == nullptr) {
throw std::out_of_range("Cannot increment end iterator");
}
node_p = node_p->next;
return *this;
}
template <typename T>
auto Iterator<T>::operator+(std::size_t offset) -> iterator {
if (node_p == nullptr) {
throw std::out_of_range("Cannot add to end iterator");
}
iterator it = *this;
while (offset > 0) {
if (it.node_p == nullptr) {
throw std::out_of_range("Target element is out of bounds");
}
++it;
--offset;
}
return it;
}
template <typename T>
auto Iterator<T>::operator==(const iterator& other) -> bool {
return node_p == other.node_p;
}
template <typename T>
auto Iterator<T>::operator!=(const iterator& other) -> bool {
return !(*this == other);
}
}
namespace Custom_SLL { // definitions of SinglyLinkedList member functions
template <typename T>
auto SinglyLinkedList<T>::empty() const -> bool {
return head == nullptr;
}
template <typename T>
SinglyLinkedList<T>::~SinglyLinkedList() {
auto curr_node = head;
while (curr_node != nullptr) {
const auto next_node = curr_node->next;
delete curr_node;
curr_node = next_node;
}
}
template <typename T>
auto SinglyLinkedList<T>::addFront(const valuetype& value) -> iterator {
auto new_node = new nodetype{value, head};
head = new_node;
return new_node;
}
template <typename T>
auto SinglyLinkedList<T>::insertAfter(iterator& it, const valuetype& value) -> iterator {
auto curr_node = it.node_p;
auto new_node = new nodetype{value, nullptr};
if (curr_node == nullptr) {
head = new_node;
} else {
new_node->next = curr_node->next;
curr_node->next = new_node;
}
return new_node;
}
template <typename T>
auto SinglyLinkedList<T>::begin() -> iterator {
return head;
}
template <typename T>
auto SinglyLinkedList<T>::end() -> iterator {
return nullptr;
}
template <typename T>
auto operator<<(
decltype(std::cout)& out,
SinglyLinkedList<T>& list
) -> decltype(out)& {
for (auto first = true; const auto& elem : list) {
out << (first ? "" : " ") << elem;
first = false;
}
return out;
}
}
main.cpp:
#include "SinglyLinkedList.hpp"
#include <iostream>
auto main() -> int {
using std::cout;
using std::boolalpha;
using Custom_SLL::SinglyLinkedList;
SinglyLinkedList<int> list{};
cout << boolalpha << list.empty() << '\n';
for (auto i = 0; i < 10; ++i) {
list.addFront(i);
}
cout << boolalpha << list.empty() << '\n';
cout << list << "\n";
for (auto it = list.begin(); it != list.end(); ++it) {
std::cout << *it << " ";
}
cout << "\n";
auto target_it = list.begin() + 5;
list.insertAfter(target_it, 99); // should insert after node with value 4
cout << list << "\n";
return 0;
}
