6
\$\begingroup\$

I wrote my implementation to Linked List. And I tried to implement all the functions in the standard library list in CPP! I need a review for it to improve it and improve my coding skill. I also will put this implementation on my GitHub account. Thanks in advance.

//======================================================
// Author      : Omar_Hafez
// Created     : 31 July 2022 (Sunday)  5:19:10 AM
//======================================================

#include <iostream>
#include <memory>
#include <vector>
#include <algorithm>

template <typename T>
class List {
    
    public:
        struct Node {
            T value;
            std::shared_ptr<Node> front, back;
            Node (T data, std::shared_ptr<Node> ptr, std::shared_ptr<Node> ptr2) 
                : value(data), front(ptr), back(ptr2) {}
        };

    private:
        int elementsCount = 0;
        std::shared_ptr<Node> begin_ptr, end_ptr, itr, tmp_ptr, header, teller;
    
    public:
        List() :
            header(std::make_shared<Node>((T)NULL, nullptr, nullptr)),
            teller(std::make_shared<Node>((T)NULL, nullptr, nullptr)) {}

        struct Iterator {
            std::shared_ptr<Node> operator*() const { return m_ptr; }

            Iterator operator++(int) { 
                if(!m_ptr) return *this;
                if(!(m_ptr->front) || indxOfPtr < 0) {
                    indxOfPtr++;
                    return *this;
                }
                Iterator tmp = *this; 
                (*this) = m_ptr->front; 
                return tmp; 
            }

            Iterator operator--(int) { 
                if(!m_ptr) return *this;
                if(!(m_ptr->back) || indxOfPtr > 0) {
                    indxOfPtr--;
                    return *this;
                }
                Iterator tmp = *this; 
                (*this) = m_ptr->back; 
                return tmp; 
            }

            friend bool operator== (const Iterator& a, const Iterator& b) { return a.m_ptr == b.m_ptr; };
            friend bool operator!= (const Iterator& a, const Iterator& b) { return a.m_ptr != b.m_ptr; };     

            std::shared_ptr<Node> m_ptr;
            int indxOfPtr;
            Iterator(std::shared_ptr<Node> ptr) : m_ptr(ptr), indxOfPtr(0) {}
        };

        struct RIterator {
            std::shared_ptr<Node> operator*() const { return m_ptr; }

            RIterator operator++(int) { 
                if(!m_ptr) return *this;
                if(!(m_ptr->back) || indxOfPtr > 0) {
                    indxOfPtr--;
                    return *this;
                }
                RIterator tmp = *this; 
                (*this) = m_ptr->back; 
                return tmp; 
            }

            RIterator operator--(int) { 
                if(!m_ptr) return *this;
                if(!(m_ptr->front) || indxOfPtr < 0) {
                    indxOfPtr++;
                    return *this;
                }
                RIterator tmp = *this; 
                (*this) = m_ptr->front; 
                return tmp; 
            }

            Iterator to_Iterator() {
                return Iterator(m_ptr->front);
            }

            friend bool operator== (const RIterator& a, const RIterator& b) { return a.m_ptr == b.m_ptr; };
            friend bool operator!= (const RIterator& a, const RIterator& b) { return a.m_ptr != b.m_ptr; };     

            std::shared_ptr<Node> m_ptr;
            int indxOfPtr;
            RIterator(std::shared_ptr<Node> ptr) : m_ptr(ptr), indxOfPtr(0) {}
        };

        void advance(List<T>::Iterator &it, int val) {
            while(*it && it != end() && val > 0) {
                it++;
                val--;
            }
        }

        void createFirstNode(T t) {
            begin_ptr = std::make_shared<Node>(t, nullptr, nullptr);
            end_ptr = begin_ptr;
            
            header->front = begin_ptr;
            begin_ptr->back = header;

            teller->back = end_ptr;
            end_ptr->front = teller;

            elementsCount++;
        }

        Iterator begin() { return Iterator(begin_ptr); }

        Iterator end()   { 
            if(!end_ptr) return Iterator(end_ptr);
            return Iterator(end_ptr->front); 
        } 

        RIterator rbegin() { 
            return RIterator(end_ptr); 
        }

        RIterator rend() { 
            if(!begin_ptr) return RIterator(begin_ptr);
            return RIterator(begin_ptr->back); 
        } 

        enum ListOpStatus { FailedListEmpty = -1, FailedListFull = -2, FailedInvalidIterator = -3, OK = 1 };

        ListOpStatus assign(T t, int count) {
            if(count == 0) return OK;
            begin_ptr = std::make_shared<Node>(t, nullptr, nullptr);

            header->front = begin_ptr;
            begin_ptr->back = header;

            itr = begin_ptr;
            for(int i = 1; i < count; i++) {
                itr->front = std::make_shared<Node>(t, nullptr, nullptr);
                tmp_ptr = itr;
                itr = itr->front;
                itr->back = tmp_ptr;
            }

            end_ptr = itr;
            teller->back = end_ptr;
            end_ptr->front = teller;

            elementsCount = count;
            end_ptr = itr;
            return OK;
        }

        // assigning from another list
        ListOpStatus assign(List<T>::Iterator it1, List<T>::Iterator it2) {
            if(!(*it1) || !(*it2)) return FailedInvalidIterator;
            begin_ptr = std::make_shared<Node> ((*it1)->value, nullptr, nullptr);

            header->front = begin_ptr;
            begin_ptr->back = header;

            elementsCount = 1;
            itr = begin_ptr;
            it1++;
            while(it1 != it2) {
                itr->front = std::make_shared<Node>((*it1)->value, nullptr, nullptr);
                tmp_ptr = itr;
                itr = itr->front;
                itr->back = tmp_ptr;
                it1++;
                elementsCount++;
            }
            end_ptr = itr;
            teller->back = end_ptr;
            end_ptr->front = teller;
            return OK;
        }

        // assigning from another reversed list
        ListOpStatus assign(List<T>::RIterator it1, List<T>::RIterator it2) {
            if(!(*it1) || !(*it2)) return FailedInvalidIterator;
            begin_ptr = std::make_shared<Node> ((*it1)->value, nullptr, nullptr);

            header->front = begin_ptr;
            begin_ptr->back = header;

            elementsCount = 1;
            itr = begin_ptr;
            it1++;
            while(it1 != it2) {
                itr->front = std::make_shared<Node>((*it1)->value, nullptr, nullptr);
                tmp_ptr = itr;
                itr = itr->front;
                itr->back = tmp_ptr;
                it1++;
                elementsCount++;
            }
            end_ptr = itr;
            teller->back = end_ptr;
            end_ptr->front = teller;
            return OK;
        }

        // assigning from vector
        ListOpStatus assign(typename std::vector<T>::iterator it1, typename std::vector<T>::iterator it2) {
            if(!(*it1) || !(*it2)) return FailedInvalidIterator;
            begin_ptr = std::make_shared<Node> (*it1, nullptr, nullptr);

            header->front = begin_ptr;
            begin_ptr->back = header;

            elementsCount = 1;
            itr = begin_ptr;
            it1++;
            while(it1 != it2) {
                itr->front = std::make_shared<Node>(*it1, nullptr, nullptr);
                tmp_ptr = itr;
                itr = itr->front;
                itr->back = tmp_ptr;
                it1++;
                elementsCount++;
            }
            end_ptr = itr;
            teller->back = end_ptr;
            end_ptr->front = teller;
            return OK;
        }

        // assigning from reversed vector
        ListOpStatus assign(typename std::vector<T>::reverse_iterator it1, typename std::vector<T>::reverse_iterator it2) {
            if(!(*it1) || !(*it2)) return FailedInvalidIterator;
            begin_ptr = std::make_shared<Node> (*it1, nullptr, nullptr);

            header->front = begin_ptr;
            begin_ptr->back = header;

            elementsCount = 1;
            itr = begin_ptr;
            it1++;
            while(it1 != it2) {
                itr->front = std::make_shared<Node>(*it1, nullptr, nullptr);
                tmp_ptr = itr;
                itr = itr->front;
                itr->back = tmp_ptr;
                it1++;
                elementsCount++;
            }
            end_ptr = itr;
            teller->back = end_ptr;
            end_ptr->front = teller;
            return OK;
        }

        ListOpStatus push_back(T t) {
            if(empty()) {
                createFirstNode(t);
                return OK;
            } 
            tmp_ptr = end_ptr;
            end_ptr->front = std::make_shared<Node>(t, nullptr, nullptr);
            end_ptr = end_ptr->front;
            end_ptr->back = tmp_ptr;

            teller->back = end_ptr;
            end_ptr->front = teller;

            elementsCount++;
            return OK;
        }

        ListOpStatus push_front(T t) {
            if(empty()) {
                createFirstNode(t);
                return OK;
            } 
            tmp_ptr = begin_ptr;
            begin_ptr->back = std::make_shared<Node>(t, nullptr, nullptr);
            begin_ptr = begin_ptr->back;
            begin_ptr->front = tmp_ptr;

            header->front = begin_ptr;
            begin_ptr->back = header;

            elementsCount++;
            return OK;
        }

        ListOpStatus pop_back() {
            if(elementsCount == 1) {
                clear();
                return OK;
            }
            if(empty()) {
                return FailedListEmpty;
            }
            end_ptr = end_ptr->back;
            end_ptr->front = nullptr;

            teller->back = end_ptr;
            end_ptr->front = teller;

            elementsCount--;
            return OK;
        }

        ListOpStatus pop_front() {
            if(elementsCount == 1) {
                clear();
                return OK;
            }
            if(empty()) {
                return FailedListEmpty;
            }
            begin_ptr = begin_ptr->front;
            begin_ptr->back = nullptr;
            
            header->front = begin_ptr;
            begin_ptr->back = header;

            elementsCount--;
            return OK;
        }

        ListOpStatus swap(List<T>::Iterator it1, List<T>::Iterator it2) {
            if(!(*it1) || !(*it2)) return FailedInvalidIterator;
            T tmp = (*it1)->value;
            (*it1)->value = (*it2)->value;
            (*it2)->value = tmp;
            return OK;
        }

        ListOpStatus swap(List<T>::RIterator it1, List<T>::RIterator it2) {
            if(!(*it1) || !(*it2)) return FailedInvalidIterator;
            return swap(it1.to_Iterator(), it2.to_Iterator());
        }

        ListOpStatus insert(List<T>::Iterator it, T t) {
            if(empty()) {
                createFirstNode(t);
                return OK;;
            }

            if(*it == begin_ptr) {
                push_front(t);
                return OK;
            }

            if(*it == end()) {
                push_back(t);
                return OK;
            }

            if(!(*it)) return FailedInvalidIterator;

            tmp_ptr = std::make_shared<Node>(t, (*it), (*it)->back);
            tmp_ptr->back->front = tmp_ptr;
            (*it)->back = tmp_ptr;
            elementsCount++;
            return OK;
        }

        ListOpStatus insert(List<T>::RIterator it, T t) {
            return insert(it.to_Iterator(), t);
        }

        ListOpStatus sort() {
            T a[elementsCount];
            int ind = 0;
            for(auto it = begin(); it != end(); it++) {
                a[ind++] = (*it)->value;
            }
            std::sort(a, a+elementsCount);
            clear();
            for(int x : a) {
                push_back(x);
            }
            return OK;
        }

        ListOpStatus unique() {
            if(empty()) return OK;
            T a[elementsCount];
            int ind = 0;
            for(auto it = begin(); it != end(); it++) {
                a[ind++] = (*it)->value;
            }
            std::sort(a, a+elementsCount);
            int sz = elementsCount;
            clear();
            push_back(a[0]);
            for(int i = 1; i < sz; i++) {
                if(a[i] == a[i-1]) continue;
                push_back(a[i]);
            }
            return OK;
        }

        ListOpStatus erase(List<T>::Iterator it) {
            if(!(*it) || it == end()) return FailedInvalidIterator;
            if(empty()) return OK;
            if(*it == header || *it == teller) return FailedInvalidIterator;
            if(elementsCount == 1) {
                clear();
                return OK;
            }
            itr = *it;
            if(itr == begin_ptr) {
                pop_front();
                return OK;
            }
            if(itr == end_ptr) {
                pop_back();
                return OK;
            }
            tmp_ptr = itr->front;
            auto tmp = itr->back;
            tmp->front = tmp_ptr;
            tmp_ptr->back = tmp; 
            elementsCount--;
            return OK;
        }

        ListOpStatus erase(List<T>::RIterator it) {
            return erase(List<T>::Iterator((*it)->front));
        }

        ListOpStatus erase(List<T>::Iterator it1, List<T>::Iterator it2) {
            while(it1 != it2) {
                erase(it1);
                it1++;
            }
            return OK;
        }

        ListOpStatus erase(List<T>::RIterator it1, List<T>::RIterator it2) {
            return(erase(it2.to_Iterator(), it1.to_Iterator()));
        }

        ListOpStatus remove_if(bool (*function) (T& t)) {
            for(itr = begin_ptr; itr; itr = itr->front) {
                if((*function) (itr->value)) {
                    erase(List<T>::Iterator(itr));
                    if(empty()) return OK;
                }
            }
            return OK;
        }

        ListOpStatus remove(T t) {
            for(itr = begin_ptr; itr; itr = itr->front) {
                if(itr->value == t) {
                    erase(List<T>::Iterator(itr));
                    if(empty()) return OK;
                }
            }
            return OK;
        }

        void clear() {
            begin_ptr = nullptr;
            end_ptr = nullptr;
            itr = nullptr;
            tmp_ptr = nullptr;
            teller->back = nullptr;
            header->front = nullptr;
            elementsCount = 0;
        }

        bool empty() const {
            return elementsCount == 0;
        } 

        bool full() const {
            return 0;
        }

        int size() const {
            return elementsCount;
        }

        void traverseList(void (*function) (T& t)) {
            for(itr = begin_ptr; itr; itr = itr->front) {
                (*function)(itr->value);
            }
        }
};
\$\endgroup\$
1

2 Answers 2

12
\$\begingroup\$
  1. Using std::shared_ptr to manage your nodes is very heavyweight.
    I would expect a container to look for efficiency, or provide seriously extended service.

  2. std::size_t is the designated index-type. int can be too small.

  3. De-referencing an iterator is expected to result in an element-reference, at worst a proxy-object. A pointer to the element, or even worse the containing node, defies all expectations.

  4. If you change your nodes and list to have a single member containing both links, you can remove many irregularities from your code.

  5. Consider whether you really want to write your own reverse-iterator, instead of just adapting a normal iterator with std::make_reverse_iterator(). The semantics are slightly but significantly different.

  6. You don't support emplacing, nor move-semantics. That makes your list very inefficient or unusable for many element-types.

  7. Dropping the start- and end-pointers, as you do in .clear() and the implicit .~List() leaves all nodes still interconnected with shared pointers. Thus, you have a memory-leak.

  8. I'm not a fan of your error-codes. They mostly seem to cover operator failure, which should really either abort the program or be full UB. Thus I expect code using it will mostly fail to check.
    Also, allocation/construction can still throw anyway.

Handling those points leads to a major rewrite, so I end it here.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Can you elaborate on 1)? \$\endgroup\$ Aug 1 at 9:14
  • \$\begingroup\$ @infinitezero shared_ptr does reference counting for every scope, using it for node-based containers is a definitive way to kill performance. Usually it makes the traversal 3~10 times slower. Using shared_ptr when there aren't multiple threads accessing it with indeterminate order is a good sign to redesign \$\endgroup\$
    – frozenca
    Aug 1 at 11:29
  • \$\begingroup\$ for linked lists, shared_ptr isn't needed even if there are such multiple threads, because atomic<T*> could do the job \$\endgroup\$
    – frozenca
    Aug 1 at 11:36
  • \$\begingroup\$ @frozenca according to my test, they clock in at the same speed: online benchmark. You have to compile with -O3 though. \$\endgroup\$ Aug 1 at 13:03
  • \$\begingroup\$ @infinitezero Curious. std::shared_ptr is twice as big as a raw pointer, and there is additional space for bookkeeping for each node... maybe the actual bookkeeping-work was somehow optimized out...?! \$\endgroup\$ Aug 1 at 13:15
0
\$\begingroup\$

Your implementation is a very heavy-weight linked list. It contains 6 std::shared_ptr<> objects. std::shared_ptr<> comes with cost.

Even if your linked list is empty, still its 2 std::shared_ptr<> hold 2 live objects for dummy purpose.

Return status from functions is not user-friendly. One needs to learn this additionally to use your linked list.

I don't find any valid reason for complicated implementation of push_back(), push_front(), pop_back() and pop_front().

I can see memory leakage.

New contributor
Daya Shanker Prasad is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$

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.