1
\$\begingroup\$

Okay, this will most likely be the last post I make for Singe Linked List unless significant revision is needed. This post following from here.

Shout out to @hoffmale for showing me the ways of the force.

Here is the header file:

#ifndef SINGLELINKEDLIST_h
#define SINGLELINKEDLIST_h



template <class T>
class SingleLinkedList {
private:

    struct Node {
        T data;
        std::unique_ptr<Node> next = nullptr;

        template<typename... Args, typename = std::enable_if_t<std::is_constructible<T, Args&&...>::value>>
        explicit Node(std::unique_ptr<Node>&& next, Args&&... args) noexcept(std::is_nothrow_constructible<T, Args&&...>::value)
            : data{ std::forward<Args>(args)... }, next{ std::move(next) } {}

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

    // Create an iterator class
    class iterator;
    iterator begin();
    iterator end();
    iterator before_begin();

    // Create const iterator class
    class const_iterator;
    const_iterator cbegin() const;
    const_iterator cend() const;
    const_iterator begin() const;
    const_iterator end() const;
    const_iterator before_begin() const;
    const_iterator cbefore_begin() const;

    // Memeber functions
    void swap(SingleLinkedList &other) noexcept;
    bool empty() const { return head.get() == nullptr; }
    int size() const;

    template<typename... Args>
    void emplace_back(Args&&... args);

    template<typename... Args>
    void emplace_front(Args&&... args);

    template<typename... Args>
    iterator emplace(const_iterator pos, Args&&... args);

    void push_front(const T &theData);
    void push_front(T &&theData);
    iterator insert_after(const_iterator pos, const T& theData);
    iterator insert_after(const_iterator pos, T&& theData);
    void clear();
    void pop_front();
    void pop_back();
    iterator erase_after(const_iterator pos);
    bool search(const T &x);



};

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

public:
    friend class SingleLinkedList<T>;

    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, bool before = false) : node{ node }, before_begin{ before } {}

    bool operator!=(iterator other) const noexcept;
    bool operator==(iterator other) const noexcept;

    T& operator*() const { return node->data; }
    T& operator->() const { return &node->data; }

    iterator& operator++();
    iterator operator++(int);
};

template <class T>
class SingleLinkedList<T>::const_iterator {
    Node* node = nullptr;
    bool before_begin = false;

public:
    friend class SingleLinkedList<T>;

    using iterator_category = std::forward_iterator_tag;
    using value_type = T;
    using difference_type = std::ptrdiff_t;
    using pointer = const T * ;
    using reference = const T & ;

    const_iterator() = default;
    const_iterator(Node* node, bool before = false) : node{ node }, before_begin{ before } {}

    operator const_iterator() const noexcept { return const_iterator{ node }; }
    bool operator!=(const_iterator other) const noexcept;
    bool operator==(const_iterator other) const noexcept;

    const T& operator*() const { return node->data; }
    const T& operator->() const { return &node->data; }

    const_iterator& operator++();
    const_iterator operator++(int);
};


template <class T>
SingleLinkedList<T>::SingleLinkedList(SingleLinkedList<T> const &source) {
    for (Node* loop = source.head.get(); loop != nullptr; loop = loop->next.get()) {
        emplace_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>
template <typename... Args>
void SingleLinkedList<T>::emplace_back(Args&&... args) {
    std::unique_ptr<Node> newnode = std::make_unique<Node>(std::forward<Args>(args)...);

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

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

template <class T>
template <typename... Args>
typename SingleLinkedList<T>::iterator SingleLinkedList<T>::emplace(const_iterator pos, Args&&... args) {
    if (pos.before_begin) {
        emplace_front(std::forward<Args>(args)...);
        return begin();
    }

    if (pos.node->next) {
        pos.node->next = std::make_unique<Node>(std::move(pos.node->next), std::forward<Args>(args)...);  // Creating a new node that has the old next pointer with the new value and assign it to the next pointer of the current node 
        return { pos.node->next.get() };
    }
}


template <class T>
template <typename... Args>
void SingleLinkedList<T>::emplace_front(Args&&... args) {
    head = std::make_unique<Node>(std::move(head), std::forward<Args>(args)...);
    if (!tail) tail = head.get(); // update tail if list was empty before
}


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>
typename SingleLinkedList<T>::iterator SingleLinkedList<T>::insert_after(const_iterator pos, const T& theData) {
    return emplace(pos, theData);
}

template <class T>
typename  SingleLinkedList<T>::iterator SingleLinkedList<T>::insert_after(const_iterator pos, T&& theData)
{
    return emplace(pos, std::move(theData));
}

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>
typename SingleLinkedList<T>::iterator SingleLinkedList<T>::erase_after(const_iterator pos) {
    if (pos.before_begin) {
        pop_front();
        return begin();
    }

    if (pos.node && pos.node->next) {
        pos.node->next = std::move(pos.node->next->next);
        return { pos.node->next.get() };
    }

    return end();
}

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

template <class T>
std::ostream& operator<<(std::ostream &str, SingleLinkedList<T>& list) {
    for (auto const& item : list) {
        str << item << "\t";
    }
    return str;
}

// Iterator Implementaion////////////////////////////////////////////////
template <class T>
typename SingleLinkedList<T>::iterator& SingleLinkedList<T>::iterator::operator++() {
    if (before_begin) before_begin = false;
    else node = node->next.get();

    return *this;
}

template<typename T>
typename SingleLinkedList<T>::iterator SingleLinkedList<T>::iterator::operator++(int) {
    auto copy = *this;
    ++*this;
    return copy;
}

template<typename T>
bool SingleLinkedList<T>::iterator::operator==(iterator other) const noexcept {
    return node == other.node && before_begin == other.before_begin;
}

template<typename T>
bool SingleLinkedList<T>::iterator::operator!=(iterator other) const noexcept {
    return !(*this == other);
}



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>::iterator SingleLinkedList<T>::before_begin() {
    return { head.get(), true };
}

// Const Iterator Implementaion////////////////////////////////////////////////
template <class T>
typename SingleLinkedList<T>::const_iterator& SingleLinkedList<T>::const_iterator::operator++() {
    if (before_begin) before_begin = false;
    else node = node->next.get();

    return *this;
}

template<typename T>
typename SingleLinkedList<T>::const_iterator SingleLinkedList<T>::const_iterator::operator++(int) {
    auto copy = *this;
    ++*this;
    return copy;
}

template<typename T>
bool SingleLinkedList<T>::const_iterator::operator==(const_iterator other) const noexcept {
    return node == other.node && before_begin == other.before_begin;
}

template<typename T>
bool SingleLinkedList<T>::const_iterator::operator!=(const_iterator other) const noexcept {
    return !(*this == other);
}


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

template <class T>
typename SingleLinkedList<T>::const_iterator SingleLinkedList<T>::cend() const {
    return end();
}

template <class T>
typename SingleLinkedList<T>::const_iterator SingleLinkedList<T>::before_begin() const {
    return { head.get(), true };
}

template <class T>
typename SingleLinkedList<T>::const_iterator SingleLinkedList<T>::cbefore_begin() const {
    return before_begin();
}

#endif /* SingleLinkedList_h*/

Here is the main.cpp file:

#include <iostream>
#include <iterator>
#include <memory>
#include <utility>
#include <random>
#include <stdexcept>
#include <iosfwd>
#include <stdexcept>
#include <type_traits>
#include <ostream>
#include "SingleLinkedList.h"
#include "DoubleLinkedList.h"

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


    ///////////////////////////////////////////////////////////////////////
    ///////////////////////////// Single Linked List //////////////////////
    ///////////////////////////////////////////////////////////////////////
    SingleLinkedList<int> obj;
    obj.emplace_back(2);
    obj.emplace_back(4);
    obj.emplace_back(6);
    obj.emplace_back(8);
    obj.emplace_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_after(obj.cbegin(),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 after particular position--------------";
    std::cout<<"\n-----------------------------------------------------------\n";
    obj.erase_after(obj.cend());
    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();
}
\$\endgroup\$
2
  • \$\begingroup\$ Nit: You've got your operator const_iterator() on the wrong class! I'm rather amazed that the compiler didn't warn about this. ...Ah, it's because the class is a template, so a lot of Clang's diagnostics (including this one) get suppressed. \$\endgroup\$ Aug 14 '18 at 2:23
  • 1
    \$\begingroup\$ @Quuxplusone Atually, clang does warn about it (and emplace). \$\endgroup\$
    – hoffmale
    Aug 14 '18 at 2:27
4
\$\begingroup\$

Some nitpicks:

  • Comments are still confusing/distracting

  • const_iterator::operator const_iterator() should be moved to iterator instead (it doesn't make sense to convert a const_iterator to a const_iterator). Also, it should pass before_begin to the const_iterator constructor as well.

  • Ther return types of iterator::operator->() should be T* instead of T&.

  • Similarly, the return type of const_iterator::operator->() should be const T*.

  • The destructor should be noexcept.

  • While technically allowed, it might surprise users that the move assignment operator extends the lifetime of the elements originally contained in *this.

  • clear() still doesn't update tail.

  • emplace doesn't update tail.

  • emplace has no value to return if both if conditions evaluate to false. Maybe throw an error message?

  • There's code duplication in push_front and emplace_front. This could be fixed by having push_front call emplace_front internally.

  • Inconsistent handling of an empty list in pop_front and pop_back: The former throws an exception, whereas the latter silently does nothing.

  • I'm still not sure if SingleLinkedList<T>::operator<< needs to be part of SingleLinkedList. Since different users will have different opinions on the output format, they'll likely will write their own print functions anyways.

\$\endgroup\$
1
  • \$\begingroup\$ IIRC destructors are noexcept by default, since C++11 \$\endgroup\$ Aug 14 '18 at 19:24

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.