5
\$\begingroup\$

I have decided to rewrite what I did here, following the suggestions to use smart pointers. I will rewrite the other data structures as well using smart pointers where appropriate.

I just want to see how my code stands now, I am sure there are still areas I need to improve or fix. I again want to thank this community in their effort in evaluating my code, I really appreciate it and I believe it is slowly but surely taking my coding skills to the next level.

Here is my header file:

#ifndef SingleLinkedList_h
#define SingleLinkedList_h

#include <iostream>

template <class T>
class SingleLinkedList {
private:

    struct Node {
        T data;
        std::unique_ptr<Node> next = nullptr;
        Node(T x) : data(x), next(nullptr) {}
    };
    std::unique_ptr<Node> head = nullptr;
    Node* tail = nullptr;

    // This function is for the overloaded operator << 
    void display(std::ostream &str) const {
        for (Node* loop = head.get(); loop != nullptr; loop = loop->next.get()) {
            str << loop->data << "\t";
        }
        str << "\n";
    }

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);
    friend std::ostream& operator<<(std::ostream &str, SingleLinkedList &data) {
        data.display(str);
        return str;
    }

    // Memeber functions
    void swap(SingleLinkedList &other) noexcept;
    bool empty() const { return head.get() == nullptr; }
    int getSize() const;
    void push(const T &theData);                            
    void push(T &&theData);
    void display() const;
    void insertHead(const T &theData);
    void insertTail(const T &theData);
    void insertPosition(int pos, const T &theData);
    void deleteHead();
    void deleteTail();
    void deleteSpecific(int delValue);
    bool search(const T &x);
};

template <class T>
SingleLinkedList<T>::SingleLinkedList(SingleLinkedList<T> const &source) {
    for(Node* loop = source.head.get(); loop != nullptr; loop = loop->next.get()) {
        push(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() {
    while (head != nullptr) {
        deleteHead();
    }
}

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>::getSize() 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(const T &theData) {
    std::unique_ptr<Node> newNode = std::make_unique<Node>(theData);

    if (head == nullptr) {
        head = std::move(newNode);
        tail = head.get();
    }

    else {
        tail->next = std::move(newNode);
        tail = tail->next.get();
    }
}

template <class T>
void SingleLinkedList<T>::push(T &&thedata) {
    std::unique_ptr<Node> newnode = std::make_unique<Node>(std::move(thedata));

    if (head == nullptr) {
        head = std::move(newnode);
        tail = head.get();
    }

    else {
        tail->next = std::move(newnode);
        tail = tail->next.get();
    }
}


template <class T>
void SingleLinkedList<T>::display() const {
    Node* newNode = head.get();
    while (newNode != nullptr) {
        std::cout << newNode->data << "\t";
        newNode = newNode->next;
    }
}

template <class T>
void SingleLinkedList<T>::insertHead(const T &theData) {
    std::unique_ptr<Node> newNode = std::make_unique<Node>(theData);
    newNode->next = std::move(head);
    head = std::move(newNode);
}

template <class T>
void SingleLinkedList<T>::insertTail(const T &theData) {
    std::unique_ptr<Node> newNode = std::make_unique<Node>(theData);
    tail->next = std::move(newNode);
    tail = tail->next.get(); 
}

template <class T>
void SingleLinkedList<T>::insertPosition(int pos, const T &theData) {
    if (pos > getSize() || 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++);

    if (i != pos) {
        throw std::out_of_range("Parameter 'pos' is out of range.");
    }

    auto newNode = std::make_unique<Node>(theData);


    if (node) {
        newNode->next = std::move(node->next);
        node->next = std::move(newNode);
    }
    else {
        head = std::move(newNode);
    }
}

template <class T>
void SingleLinkedList<T>::deleteHead() {
    if (!head.get()) {
        throw std::out_of_range("List is Empty!!! Deletion is not possible.");
    }

    auto current = head.get();
    auto next = std::move(current->next);
    head = std::move(next);
}

template <class T>
void SingleLinkedList<T>::deleteTail() {
    if (!head.get()) {
        throw std::out_of_range("List is Empty!!! Deletion is not possible.");
    }

    auto current = head.get();
    Node* previous = nullptr;

    while (current->next != nullptr) {
        previous = current;
        current = current->next.get();
    }
    tail = previous;
    previous->next = nullptr;
}

template <class T>
void SingleLinkedList<T>::deleteSpecific(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) {
    auto current = head.get();
    while (current != nullptr) {
        if (current->data == x) {
            return true;
        }
        current = current->next.get();
    }
    return false;
}




#endif /* SingleLinkedList_h*/

Here is the main.cpp file:

#include <algorithm>
#include <cassert>
#include <iostream>
#include <ostream>
#include <iosfwd>
#include "SingleLinkedList.h"


int main(int argc, const char * argv[]) {


    ///////////////////////////////////////////////////////////////////////
    ///////////////////////////// Single Linked List //////////////////////
    ///////////////////////////////////////////////////////////////////////
    SingleLinkedList<int> obj;
    obj.push(2);
    obj.push(4);
    obj.push(6);
    obj.push(8);
    obj.push(10);
    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"---------------displaying all nodes---------------";
    std::cout<<"\n--------------------------------------------------\n";
    std::cout << obj << std::endl;


    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"-----------------Inserting At End-----------------";
    std::cout<<"\n--------------------------------------------------\n";
    obj.insertTail(20);
    std::cout << obj << std::endl;

    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"----------------Inserting At Start----------------";
    std::cout<<"\n--------------------------------------------------\n";
    obj.insertHead(50);
    std::cout << obj << std::endl;

    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"-------------inserting at particular--------------";
    std::cout<<"\n--------------------------------------------------\n";
    obj.insertPosition(5,60);
    std::cout << obj << std::endl;

    std::cout << "\n--------------------------------------------------\n";
    std::cout << "-------------Get current size ---=--------------------";
    std::cout << "\n--------------------------------------------------\n";
    std::cout << obj.getSize() << std::endl;

    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"----------------deleting at start-----------------";
    std::cout<<"\n--------------------------------------------------\n";
    obj.deleteHead();
    std::cout << obj << std::endl;

    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"----------------deleting at end-----------------------";
    std::cout<<"\n--------------------------------------------------\n";
    obj.deleteTail();
    std::cout << obj << std::endl;


    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"--------------Deleting At Particular--------------";
    std::cout<<"\n--------------------------------------------------\n";
    obj.deleteSpecific(4);
    std::cout << obj << std::endl;
    std::cout << std::endl;

     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 << std::endl;


     //std::cout << "\n-------------------------------------------------------------------------\n";
     //std::cout << "--------------Testing to insert in an empty list----------------------------";
     //std::cout << "\n-------------------------------------------------------------------------\n";
     //SingleLinkedList<int> obj2;
     //obj2.insertPosition(5, 60);
     //std::cout << obj2 << std::endl;

    std::cin.get();
}
\$\endgroup\$
7
\$\begingroup\$
  1. You are including too little. std::unique_ptr needs <memory>, std::swap needs <utility>, std::invalid_argument needs <stdexcept>.

  2. Defining and using a ctor for your Node instead of using aggregate-initialization forces you to make unnecessary, maybe costly or even impossible, copies. Considering your interface, that's very surprising for your clients.

    Remove all ctors from Node, and use aggregate-initialization instead.

  3. I honestly have no idea why you defined the private .display(std::ostream&). Just put it back into friend std::ostream& operator<<(std::ostream&, SingleLinkedList const&).

  4. Defining .display() needlessly chains your code to std::cout. Otherwise, you could include <ostream> instead of <iostream> and avoid initializing all the C++ streams.

  5. If you want to stream a single character, don't stream a string. Needless inefficiency is bad.

  6. Users expect an iterator-interface, and it would make copying, printing, as well as inserting and deleting at specific points easier and/or more efficient. Enabling use of standard algorithms is also nice.

    You should implement ForwardIterators.

  7. Your names are outlandish (.getSize() => .size(), .push() / insertTail() => .push_back(), .insertHead() => .push_front(), .deleteHead() => .pop_front(), .deleteTail() => .pop_back()). That means no standard algorithms to you, and it's much harder to work with.

  8. I would expect .search() to return an iterator. As you don't have any, maybe a pointer. But certainly not a bool, that's what .contains() would be for.

  9. You don't allow construction from std::initializer_list<T>, nor an Iterator-pair. That's disappointing.

  10. You know pointer != nullptr is the same as pointer in a boolean context? The same for pointer == nullptr and !pointer.

  11. Avoid mixing iostreams and stdio without good reason. Also, only use std::endl if you need an explicit flush. But, maybe you do...

  12. You know you can fuse two string-literals simply by not separating them with anything but whitespace, including newlines?

\$\endgroup\$
  • \$\begingroup\$ Could you explain more for number 2 on what I should do to use aggregate initialization for my Node? \$\endgroup\$ – Snorrlaxxx Aug 4 '18 at 21:10
  • \$\begingroup\$ For point number 4, should I just remove the .display() function entirely? \$\endgroup\$ – Snorrlaxxx Aug 4 '18 at 21:13
  • \$\begingroup\$ Also, how would I go about applying your point number 6? Do you have any suggestions or something I can refer to? \$\endgroup\$ – Snorrlaxxx Aug 4 '18 at 21:14
  • \$\begingroup\$ @Snorrlaxxx: 2. Elaborated. 4. Yes. 6. Linked to the Iterator-type you should write. \$\endgroup\$ – Deduplicator Aug 5 '18 at 10:38
  • \$\begingroup\$ I am sorry I still do not understand what I need to do for number 2. Also, I have no idea how to implement number 6. \$\endgroup\$ – Snorrlaxxx Aug 5 '18 at 16:52
5
\$\begingroup\$

Your header file shouldn't require other headers to be included first. You are missing includes of <memory> and <utility> for it to be usable. You can help yourself spot such omissions by including your own headers first, before the standard library headers, in your main.cpp.

It helps to be consistent with standard collections - this consistency is useful, as it allows your collection to be used in a generic (template) function. For this reason, I suggest size_t size() const instead of int getSize() const.

Instead of search(), it might be better to implement iterators for your collection. Then we have the full range of <algorithm> functions, including find_if() and so on. We'd be able to replace deleteSpecific() with an erase() method that accepts an iterator or two iterators, more like the standard collections. (This erase() would then usefully provide you with a clear() method, and you could use that in the destructor to avoid unlimited recursion in the cleanup).

What is the purpose of the no-argument display()? It seems to just duplicate the streaming operator, but constrained to standard output, rather than being usable with std::clog or to a file stream, for example. And the other, private display() is used only in one place, so perhaps it should be inlined within the streaming operator.

\$\endgroup\$
  • \$\begingroup\$ Could you go into more detail how I would improve this class with the use of iterators and such? I am a bit unfamiliar with their implementation. \$\endgroup\$ – Snorrlaxxx Aug 4 '18 at 21:20
  • 1
    \$\begingroup\$ How to create iterators is an entire answer in itself! \$\endgroup\$ – Toby Speight Aug 6 '18 at 8:32
3
\$\begingroup\$
#ifndef SingleLinkedList_h
#define SingleLinkedList_h

Most naming conventions reserve UPPERCASE to differentiate between preprocessor (Macro) variables from C++ language constructs/variables.

The name of your include guard should aim to minimize the chance of clashes with names from other code. Use differentiators like project name, physical path, logical path, author name, date, and/or GUIDs.

// Exposition-only
#ifndef SNORLAXXX_CONTAINERS_SINGLE_LINKED_LIST_H_080418_INCLUDED
#define SNORLAXXX_CONTAINERS_SINGLE_LINKED_LIST_H_080418_INCLUDED

#include <iostream>

Do not include <iostream> in header files. Most C++ implementations will inject static constructors into every translation unit that includes your header, whether or not IO facilities are needed.


    struct Node {
        T data;
        std::unique_ptr<Node> next = nullptr;
        Node(T x) : data(x), next(nullptr) {}
    };

std::unique_ptr<> requires <memory>.

Constructors with a single non-default parameter should be declared with the function specifier explicit to avoid unintended implicit conversions.

A constructor should create a fully initialized object. If I have both the data and the next pointer, I should be able to create an object without requiring the extra step of assignment to next. What if I want to construct data in place? Is T guaranteed to be cheap to copy?

Update

    // Exposition-only
    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)) {}
    };

    void display(std::ostream &str) const {
        for (Node* loop = head.get(); loop != nullptr; loop = loop->next.get()) {
            str << loop->data << "\t";
        }
        str << "\n";
    }

This is one of your dependents on <iostream> that isn't necessary. A better approach is to create an interface to your data. In the standard library, that is done through iterators. You can also apply a visitor function to each element.

// Exposition-only
public:
    template <typename UnaryOp>
    void for_each_element(UnaryOp f) const {
        for (auto current = head.get(); head; head = head->next.get()) {
            std::invoke(f, std::as_const(current->data));
        }
    }

display, display(str), and operator<< can now be standalone functions. They can be placed in their own header and the user can selectively include it into their project if they really want output facilities.


    bool empty() const { return head.get() == nullptr; }

std::unique_ptr<>::operator bool() exists. You neither have to call get() or compare to nullptr.


template <class T>
SingleLinkedList<T>::SingleLinkedList(SingleLinkedList<T> const &source) {
    for(Node* loop = source.head.get(); loop != nullptr; loop = loop->next.get()) {
        push(loop->data);
    }
}

Seems like a good use case for a visitor traverser.

Update

// Exposition-only
template <class T>
SingleLinkedList<T>::SingleLinkedList(SingleLinkedList<T> const &source) {
    source.for_each_element([&](auto&& value) { push(value); });
}

    template <class T>
    SingleLinkedList<T>::~SingleLinkedList() {
        while (head != nullptr) {
            deleteHead();
        }
    }

The body of your destructor would be useful to the user if they ever wanted to clear() their list.

Think semantically, not just syntactically. You check to see if the list is empty here, but you also check again in deleteHead().

    // Exposition-only
private:
    template <class T>
    SingleLinkedList<T>::do_pop_front() {
        head = std::move(head->next);
    }

public:
    template <class T>
    SingleLinkedList<T>::~SingleLinkedList() {
        clear();
    }

    template <class T>
    void SingleLinkedList<T>::clear() {
        while (head) {
            do_pop_front();
        }
    }

    template <class T>
    void SingleLinkedList<T>::deleteHead() {
        if (empty()) { throw ... }
        do_pop_front();
    }

     using std::swap;

Requires <utility>.


template <class T>
int SingleLinkedList<T>::getSize() const {
    int size = 0;
    for (auto current = head.get(); current != nullptr; current = current->next.get()) {
        size++;
    }
    return size;
}

If you want your container to be usable with existing standard interfaces, follow the naming conventions (size). You can read about the Container requirements.

Consider caching the size as a data member. It's simple\$^{1}\$ for your class to keep count as operations on your list happen. Note - Splicing would become an \$O(n)\$ operation as it has to recalculate the size on splice.

Should int represent your size type?

\$^{1}\$"There are 2 hard problems in computer science: cache invalidation, naming things, and off-by-1 errors." -- Leon Bambrick


template <class T>
void SingleLinkedList<T>::push(const T &theData) {
    std::unique_ptr<Node> newNode = std::make_unique<Node>(theData);

    if (head == nullptr) {
        head = std::move(newNode);
        tail = head.get();
    }

    else {
        tail->next = std::move(newNode);
        tail = tail->next.get();
    }
}

std::move requires <utility>. The logic can be simplified.

// Exposition-only.
template <class T>
void SingleLinkedList<T>::push(const T &theData) {
    std::unique_ptr<Node> newNode = std::make_unique<Node>(theData);
    newNode->next = std::move(head); // new node takes ownership of existing nodes
    head = std::move(newNode);       // new node is now head
}

template <class T>
void SingleLinkedList<T>::insertTail(const T &theData) {
    std::unique_ptr<Node> newNode = std::make_unique<Node>(theData);
    tail->next = std::move(newNode);
    tail = tail->next.get(); 
}

Singly-linked lists typically operate from one-end. This leads to unusual behavior where insertion at the front or back is constant, but deletion at the front is constant while the back is linear (as tail needs to be updated).


template <class T>
void SingleLinkedList<T>::insertPosition(int pos, const T &theData) {
    if (pos > getSize() || pos < 0) {
        throw std::out_of_range("The insert location is invalid.");
    }

std::out_of_range requires <stdexcept>. Is pos == getSize() a valid state?

    auto node = head.get();
    int i = 0;

    for (; node && node->next && i < pos; node = node->next.get(), i++);

This could be a helper function that advances a node by \$pos\$ elements.

    if (i != pos) {
       throw std::out_of_range("Parameter 'pos' is out of range.");
   }

Why would this ever be true if we know pos is in \$[0, getSize())\$?

    auto newNode = std::make_unique<Node>(theData);

    if (node) {
        newNode->next = std::move(node->next);
        node->next = std::move(newNode);
    }
    else {
        head = std::move(newNode);
    }

So we're not inserting at the position but after the position. Perhaps the function should be named insert_after?


template <class T>
void SingleLinkedList<T>::deleteTail() {
    ...
    auto current = head.get();
    Node* previous = nullptr;

    while (current->next != nullptr) {
        previous = current;
        current = current->next.get();
    }

Abstracting this into an adjacent find helper could be useful for this function, and deleteSpecific().

    tail = previous;
    previous->next = nullptr;

If you decide to allow operating on both ends of the list, I would simply this function. deleteHead was simplified in the comment on the destructor.

// Exposition-only
template <class T>
void SingleLinkedList<T>::deleteTail() {
    tail.reset();
    tail = node_adjacent_find(/* start@ */ head, next_points_to(nullptr));
}

template <class T>
void SingleLinkedList<T>::deleteSpecific(int delValue) {
    /* throw on empty... */
    auto current = head.get();
    while (true) {
        current = node_adjacent_find(current, next_value(delValue));
        if (!current) {
            return; // Why throw?
        }
        current->next = std::move(current->next->next);
        current = current->next.get();
    }
}

#include <algorithm>
#include <cassert>
#include <iostream>
#include <ostream>
#include <iosfwd>
#include "SingleLinkedList.h"

Organize your headers. If you order them in logical groups - from implementation level to language level to system level - you can catch latent usage errors in your own code as soon as possible.

  1. Prototype/Interface headers - matching .hpp that corresponds to a .cpp
  2. Project headers - my_utils.hpp
  3. Non-standard non-system headers - boost, eigen
  4. Standard headers - iostream, cstdint, vector
  5. System headers - May require configuration and out of order use because of dependencies.

Order each of those logical subgroups by name (if possible) to allow readers to quickly parse through longer lists.

You don't need <algorithm>, <cassert>, <ostream>, or <iosfwd>.


int main(int argc, const char * argv[]) {

If you are not accepting command-line arguments, you can omit the parameters for main. (int main() {).


    SingleLinkedList<int> obj;
    obj.push(2);
    obj.push(4);
    obj.push(6);
    obj.push(8);
    obj.push(10);
    std::cout<<"---------------displaying all nodes---------------";
    std::cout << obj << std::endl;

Rather than memorizing the 25 or so operations, in-order, and how the internal state flows, just use a testing framework (Catch2). Reduce your cognitive load, test more, and process useful information (what failed?).

// Exposition-only
#define CATCH_CONFIG_MAIN

#include "SingleLinkedList.h"
#include "catch2/catch.hpp"

TEST_CASE( "single linked list operations", "[slist]" ) {
    SingleLinkedList<int> obj;
    for (int i = 2; i < 11; i += 2) {
        obj.push(i);
    }

    SECTION( "get current size" ) {
        REQUIRE(obj.getSize() == 5);
    }
    ...
    SECTION( "inserting at end" ) {
        obj.insertTail(20);
        REQUIRE( obj.size() == 6 );
        // REQUIRE( obj.back() == 20 );
    }
    ...
    SECTION( "empty list throws on delete head" ) {
        obj.clear();
        REQUIRE( obj.empty() );
        REQUIRE_THROWS( obj.deleteHead() );
        REQUIRE_THROWS_AS( obj.deleteHead(), std::out_of_range );
    }
    ...
}
\$\endgroup\$
  • \$\begingroup\$ Thank you for the comments. I am still having trouble implementing all of what you suggested. Could you provide a solution to what you intend for me to change using my code? \$\endgroup\$ – Snorrlaxxx Aug 5 '18 at 17:14
  • \$\begingroup\$ Look at your implementation's <forward_list>. \$\endgroup\$ – Snowhawk Aug 5 '18 at 21:09
  • \$\begingroup\$ what do you mean my implementation's <forward_list> I do not understand? \$\endgroup\$ – Snorrlaxxx Aug 5 '18 at 21:36
  • \$\begingroup\$ What exactly are you having problems implementing? \$\endgroup\$ – Snowhawk Aug 5 '18 at 21:39
  • \$\begingroup\$ Well, iterators and some of the other suggestions you had involving the constructor. \$\endgroup\$ – Snorrlaxxx Aug 5 '18 at 21:41
2
\$\begingroup\$

Create iterators over the elements in the list

Here's how to go about creating iterators for this collection. They will naturally be forward iterators, as we can't traverse the singly-linked list backwards.

First, let's declare the iterator class, and begin() and end() methods to create them:

public:
    class iterator;
    iterator begin();
    iterator end();

The state within an iterator is obviously its current Node:

template<class T>
class SingleLinkedList<T>::iterator
{
    Node* node;
}

For a forward iterator, we need to be able to dereference and to increment it; also we need to be able to compare iterators for equality, and to construct (including default-construct) instances:

template<class T>
class SingleLinkedList<T>::iterator
{
    Node* node = nullptr;

public:
    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>
typename SingleLinkedList<T>::iterator SingleLinkedList<T>::begin()
{
    return head.get();
}

template<class T>
typename SingleLinkedList<T>::iterator SingleLinkedList<T>::end()
{
    return {};
}

To use with standard algorithms, we need to provide some type names that can be found by std::iterator_traits:

#include <iterator>

template<class T>
class SingleLinkedList<T>::iterator
{
public:
    using iterator_category = std::forward_iterator_tag;
    using value_type = T;
    using difference_type = std::ptrdiff_t;
    using pointer = T*;
    using reference = T&;

Then we can use iterators to simplify our code:

template <class T>
bool SingleLinkedList<T>::search(const T &x) {
    return std::find(begin(), end(), x) != end();
}

Exercise

Implement a const iterator for the list. You'll start with these methods in SingleLinkedList:

class const_iterator;
const_iterator cbegin() const;
const_iterator cend() const;
const_iterator begin() const;
const_iterator end() const;

and the iterator traits will refer to const T in place of T.

\$\endgroup\$
  • 1
    \$\begingroup\$ You might find it easier to user your iterators for erase() and such if you make the state be a pointer to the smart pointer that points to the node. I.e. class iterator { std::unique_ptr<Node>* current; }. Experiment with both, and see what their relative advantages are! \$\endgroup\$ – Toby Speight Aug 6 '18 at 8:35
  • \$\begingroup\$ Thank you, I am going to implement what you suggested, appreciate the help immensely. \$\endgroup\$ – Snorrlaxxx Aug 7 '18 at 0:00
  • \$\begingroup\$ Will I also include the using iterator_category, etc in the const_iterator class as well? \$\endgroup\$ – Snorrlaxxx Aug 7 '18 at 0:15
  • \$\begingroup\$ Yes, you'll need that. You'll find a lot of duplication between the mutable and const iterators. That can be reduced using templates, but I recommend you focus on understanding the iterators and working out how to use them in your methods before getting aggressive with the DRY principle. Oh, and do come back for a review of your iterators when you think it's ready! \$\endgroup\$ – Toby Speight Aug 7 '18 at 8:05
  • \$\begingroup\$ Hi Toby, thank you. I will come back for sure. That being said, I was thinking of once I believe I am done with single linked list I would start on re-writing double linked list and incorporate what I learned in the single linked list. That way if there are still things I am getting wrong or not doing then I will know I need to change some of those in my single linked list code as well, does that sense? \$\endgroup\$ – Snorrlaxxx Aug 8 '18 at 0:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.