3
\$\begingroup\$

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

Improve this question
\$\endgroup\$

2 Answers 2

Reset to default
5
\$\begingroup\$

Design issues

  • An overload of insert that accepts T&& is missing.

  • Now that there are iterators, I'd expect insert to take a const_iterator as parameter instead of int pos.

    This allows the insert operation itself to run in \$\mathcal{O}(1)\$ by delegating the iteration work to the caller (who might be iterating the list already, e.g. to find where the node should be inserted in the first place).

    Also, it would be nice if an iterator pointing to the newly inserted node would be returned (as this allows for easy chaining of insertions).

    • If insertion at a specific ordinal position is needed, this could still be easily achieved by calling list.insert(list.begin() + pos, value).

    • The easiest way to let the SingleLinkedList have access to iterator::node or const_iterator::node is to declare it as a friend class SingleLinkedList inside iterator and const_iterator.

  • Clarity issue: What does the delValue parameter of delete_specific actually represent? And while I'm at it, what is the actual purpose of delete_specific?

    My first guesses based on its definition would be that delValue is the position to be removed (like int pos in insert), or the value of which all copies should be removed (which then should be of type const T&, not int).

    • In the first case, I'd suggest rewriting void delete_specific(int) into iterator erase_after(const_iterator), to keep the naming from the standard library's std::forward_list.

    • In the latter case, I'd suggest rewriting void delete_specific(int) into void remove(const T&), again adhering to the standard library's choice of name.

    Granted, there are some inconsistencies in the standard library itself, as the operations std::forward_list::remove and std::list::remove (removing all elements with a specific value) correspond to erase member functions on other containers. Still, it might be easier to adopt usage of SingleLinkedList if the names are similar to the std::forward_list ones.

    However, that actual implementation of delete_specific does neither of those, instead it only removes the first element that is equal to delValue (not all of them), and throws if none was found (which again would surprise me).

Implementation issues

  • Copy-constructing a SingleLinkedList has runtime complexity \$\mathcal{O}(n^2)\$. This could be reduced to \$\mathcal{O}(n)\$.

    There are multiple ways to achieve this, the easiest would be (assuming the above mentioned changes to insert have been made):

    SingleLinkedList(const SingleLinkedList& other) {
    auto insert_pos = begin();
    for(auto&& obj : other) {
        // keep the position of the newly inserted node, as the next one will be inserted after it
        insert_pos = insert(insert_pos, obj);
    }
}

  • Move assignment might extend the lifetime of the elements originally contained in this far longer than expected by swapping them into move. (Also, it might be unexpected that move isn't empty after the move-assignment.)

  • clear() doesn't update tail (should be nullptr afterwards).

  • pop_front() doesn't update tail in case the last node was removed.

Iterator issues

  • The iterator classes need a post-increment operator to be fully adhering to the ForwardIterator requirements.

  • const_iterator::pointer should be const T* and const_iterator::reference should be const T&, as the expectations of a const_iterator is that it doesn't allow modification (by anyone but the container) of the data it's refering to.

    Simple memorization help: operator* should return a reference and operator-> should return a pointer.

  • iterator::operator-> and const_iterator::operator-> should return a pointer, i.e. return &node->data; (also needs adjustment of the return type).

  • Consider adding an constructor to const_iterator that allows implicit conversion from a normal iterator. This would allow using iterators in places where a const_iterator would be expected (e.g. in the insert member function).

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ I need some help if you are not too busy. \$\endgroup\$
    – Snorrlaxxx
    Aug 11, 2018 at 18:11
  • \$\begingroup\$ would the insert function be a void or an iterator type? \$\endgroup\$
    – Snorrlaxxx
    Aug 14, 2018 at 0:22
4
\$\begingroup\$

Make SingleLinkedList.h self-sufficient

The file can be made self-sufficient by #includeing the following header files:

  1. <memory> for std::unique_ptr and std::make_unique.
  2. <algorithm> for std::find.
  3. <utility> for std::move.
  4. <stdexcept> for std::out_of_range and std::invalid_argument.
  5. <iterator> for std::forward_iterator_tag.
  6. <cstddef> for std::ptrdiff_t.

One trick to detect such issues is to make it the first #include file in main.cpp.

Improve this answer
\$\endgroup\$
2
  • 2
    \$\begingroup\$ <string> isn't explicitly needed, for 2 reasons: 1) those exception types can take a const char* parameter, and only raw string literals are used, and 2) <stdexcept> already has to include <string> to make it self-sufficient. (Also, I'm not sure on <utility>, <memory> might have to include it already.) \$\endgroup\$
    – hoffmale
    Aug 10, 2018 at 6:35
  • 2
    \$\begingroup\$ You are right about (1). Not sure about (2). The constructors use std::string const&, which can be accomplished by forward declaration. <utility> is used by many other standard headers. It is safer to #include it explicitly. \$\endgroup\$
    – R Sahu
    Aug 10, 2018 at 6:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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