0

Consider a standard implementation of class Link of LinkedList in c++. I want to know if its a good idea to overload the operator ++ in this class (I noticed that I repeat the line link = link->next; a lot when dealing with linked lists, so I thought it would be easier if I overload this operator). Here's my implementation:

#ifndef LINK_H
#define LINK_H
#include <iostream>
#include "typeinfo.h"
#include "LinkedList.h"

template <class T> class LinkedList;                                //|Forward declaration of the generic LinkedList.

template <class T>
class Link
{
    public:
    //|-------------------- Constructors --------------------
        Link(T data): m_data(data), next(NULL){}
    //|-------------------- Methods --------------------
         T getData(){
            return m_data;
         }

         T& getNext(){
            return next;
         }

         void setNext(Link* newLink){
            next = newLink;
         }

         void setData(T data){
            m_data = data;
         }
    //|-------------------- Operator overload --------------------
        bool operator==(Link& other){
            if(this->m_data == other.m_data)
                return true;
            return false;
        }

        void operator++(){                           //Is this okay?
            this = this->next;
        }

    //|-------------------- Friend functions --------------------

    friend std::ostream& operator<<(std::ostream& out,const Link<T>& link){

        out<<link.m_data;
        return out;
    }

    //|-------------------- Destructor --------------------
        virtual ~Link(){}

    protected:

    public:
    //|-------------------- Private fields --------------------
        T m_data;
        Link<T>* next;

    friend class LinkedList<T>;
};

#endif // LINK_H

I guess the way that I tried to do it is not good (it does work as I expected). I tried to use this because I want it to work on pointer that is pointing to a certain link.

So, is it a good idea? if it is, what is the right way to implement it?

Thanks.

10
  • 5
    No, you want your linked list to have an iterator class associated with it. Overload the ++ operator on that. Commented Jan 27, 2022 at 23:43
  • 3
    @DirichletIsaPartyPooper It is not pointless, there are whole libraries dedicated to performing tasks on different kinds of containers in a consistent manner by using iterators. But, maybe for your particular situation, it is probably pointless to use iterators. Hard to say, since you didn't show how you are using your LinkedList. But to answer your main question, no, you can't implement operator++ the way you are trying to. Commented Jan 27, 2022 at 23:51
  • 1
    Check out the section on operator++ here for more wisdom on implementing a ++ operator. For one thing, it should return a reference to either the value before the increment or the value after, depending on which side of the variable the ++ is on. Commented Jan 28, 2022 at 0:12
  • 1
    Tactical note: In C++ Linked lists are more robust if the user of the linked list never gets to see the links.. If you return a pointer to a link to the user some fool could delete it, mangle the pointers in it that handle the linkages, or do something equally stupid. Never return a link to the user and you'll never have this problem, but that leads to the question of what do you return? The answer is an iterator. Commented Jan 28, 2022 at 0:57
  • 2
    Assining to this shouldn't even compile Commented Jan 28, 2022 at 6:32

1 Answer 1

1

Maybe you should refactor your design and the code.

The link, or better said the Node, is normally implemented as an own class. An this class is embedded in the LinkedList class. And that Node class should be completely encapsulated and not shown to the outside world.

The user of the class will just deal with the data value. All the pointer stuff should be hidden.

And to be able to iterate over your class, which is similar to a std::forward_list, you can add ultra simple iterator functionality. Most functions can be implemented using a one liner.

I will show you below an ultra simple implementation example. This may be extended easily according to your needs.

From that you may take over some ideas to improve your design.

With the added iterator functionality, you may use range based for loops and std:: algorithms and all the like.

Please have a look and ask questions, if there should be something unclear.

#include <iostream>
#include <iterator>
#include <initializer_list>
#include <algorithm>

// Very simple implementation of a forward list
template <class T>
class SinglyLinkedList {

    // The node
    struct Node {
        T data{};     // Data. Would normally be a templated argument
        Node* next{};   // And the pointer to the next node

        Node(const T& i, Node* n = nullptr) : data(i), next(n) {}; // Simple constructor to set a value and next pointer
    };

    Node* head{};       // This is the start of the list
    // It would be advisable to have a tail pointer. We use the more inefficient approach here
    Node* getLast() const { Node* n{ head }; while (n and n->next) n = n->next; return n; }

public:
    // Constructor / Destructor --------------------------------------------------------------------------------------------------------
    ~SinglyLinkedList() { clear(); }

    // Default constuctor
    SinglyLinkedList() {}   // Default

    // From an initialization list
    SinglyLinkedList(const std::initializer_list<T>& il) { clear();  for (const T& i : il) push_back(i); } // From initializer list

    // Copy constructor
    SinglyLinkedList(const SinglyLinkedList& other) { clear(); for (const T &i : other) push_back(i); }

    // Move constructor. Will steal the elements from the other 
    SinglyLinkedList(SinglyLinkedList&& other) noexcept { head = other.head; other.head = nullptr; }

    // Assignment operator
    SinglyLinkedList& operator = (const SinglyLinkedList& other) { clear(); for (const T &i : other) push_back(i); }

    // Move assignment operator 
    SinglyLinkedList& operator = (SinglyLinkedList&& other) { head = other.head; other.head = nullptr; }

    // Housekeeping --------------------------------------------------------------------------------------------------------------
    void clear() { Node* tmp{ head }; while (tmp) { Node* toDelete{ tmp }; tmp = tmp->next; delete toDelete; } head = nullptr; }
    int empty() const { return head == nullptr; }
    int size() const { int k{}; Node* n{ head }; while (n) { ++k; n = n->next; } return k; }

    // Modify content --------------------------------------------------------------------------------------------------------------
    void push_front(const T& i) { Node* n = new Node(i); n->next = head; head = n; };
    void push_back(const T& i) { Node* n = new Node(i); Node* l = getLast(); if (l) l->next = n; else head = n; }
    void pop_front() { if (head) { Node* tmp = head->next; delete head; head = tmp; } }
    void pop_back() { // This is a little bit more difficult in a singly linked list
        if (head) {
            Node* n{ head }, * previous{};
            while (n and n->next) {
                previous = n;
                n = n->next;
            }
            delete n;
            if (previous)
                previous->next = nullptr;
            else
                head->next = nullptr;
        }
    }

    // Access elements --------------------------------------------------------------------------------
    T front() const { return head ? head->data : 0; };
    T back() const { Node* n = getLast(); return n ? n->data : 0; }

    // Add iterator properties to class ---------------------------------------------------------------
    struct iterator {                           // Local class for iterator
        Node* iter{};                           // Iterator is basically a pointer to the node

        // Define alias names necessary for the iterator functionality
        using iterator_category = std::forward_iterator_tag;
        using difference_type = std::ptrdiff_t;
        using value_type = T;
        using pointer = T*;
        using reference = T&;

        // Constructor
        iterator() {}
        iterator(Node* n) : iter(n) {}

        // Dereferencing
        reference operator *() const { return iter->data; }
        pointer operator ->() const { return &iter->data; }

        // Aithmetic operations
        iterator& operator ++() { if (iter) iter = iter->next; return *this; }
        iterator operator ++(int) { iterator temp{ *this }; ++* this; return temp; }
        iterator operator +(const difference_type& n) const { iterator temp{ *this };  difference_type k{ n }; while (k--)++temp; return temp; }
        iterator& operator +=(const difference_type& n) { difference_type k{ n }; while (k--)++* this; return *this; };

        // Comparison
        bool operator != (const iterator& other) const { return iter != other.iter; }
        bool operator == (const iterator& other) const { return iter == other.iter; }
        bool operator < (const iterator& other) const { return iter < other.iter; }
        bool operator > (const iterator& other) const { return iter > other.iter; }
        bool operator <= (const iterator& other) const { return iter <= other.iter; }
        bool operator >= (const iterator& other) const { return iter >= other.iter; }

        // Difference. Also complicated, because no random access
        difference_type operator-(const iterator& other) const {
            difference_type result{};
            Node* n{ iter };
            while (n and n != other.iter) {
                ++result;
                n = n->next;
            }
            return result;
        }
    };

    // Begin and end function to initialize an iterator
    iterator begin() const { return iterator(head); }
    iterator end() const { return iterator(); }

    // Functions typcical for forward lists ----------------------------------------------------------------------
    // Easy, becuase we can operate form the current iterator and do not need the "previous" element
    iterator insertAfter(iterator& pos, const T& i) {
        iterator result{};
        if (pos.iter and pos.iter->next) {
            Node* n = new Node(i, pos.iter->next);
            pos.iter->next = n;
            result = n;
        }
        return result;
    }
    iterator eraseAfter(iterator& pos) {
        iterator result{};
        if (pos.iter and pos.iter->next) {
            Node* tmp = pos.iter->next->next;
            delete pos.iter->next;
            pos.iter->next = tmp;
            result = pos.iter->next;
        }
        return result;
    }
};
// Test/Driver Code
int main() {

    // Example for initilizer list
    SinglyLinkedList<int> sllbase{ 5,6,7,8,9,10,11,12,13,14,15 };
    // Show move constructor
    SinglyLinkedList<int> sll(std::move(sllbase));

    // Add some values in the front
    sll.push_front(4);
    sll.push_front(3);
    sll.push_front(2);
    sll.push_front(1);

    // Delete 1st element (Number 1)
    sll.pop_front();
    // Delete last element
    sll.pop_back();

    // Use a std::algorithm on our custom linked list. Works because we have an interator
    SinglyLinkedList<int>::iterator iter = std::find(sll.begin(), sll.end(), 8);

    // Now add an element after 8
    iter = sll.insertAfter(iter, 88);
    // End delete the 9
    iter = sll.eraseAfter(iter);

    // Use range based for loop. Works because, we have iterators
    for (int i : sll)
        std::cout << i << ' ';
}
Sign up to request clarification or add additional context in comments.

4 Comments

Thanks for this comment. I do have a few questions. First, why would you want to implement the Node structure inside the LinkedList class? in this way we cannot use the Node structure to other classes that may use link. Also - why do you implement it as a structure and not as a class? The last question - why do you pass parameters to your function by reference and not by value (and for example front() and back() function do not return a reference)
The Node should be hidden to others. It is an implementation detail. We are just interested in the data, but never in the pointers. So, Node should be encapsulated. This is a standard design decision. But if you see a use can then you can also expose it. Struct and Class are nearly the same in C++. The only major difference is that in struct everything is public per default. I pass parameters per reference because T could also be a complex data type and copying could be expensive. Pass by value is copying. Front and back can also return references, but then should not be const. Hope this helps
Const function cannot return reference?
It can. But with references you can change the data in the list. Without the reference, we just get the copy. With the reference we can change the data. But also here would could promise to not do so with const. It is a design decision.

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.