2
\$\begingroup\$

I have written a simple singly linked list in C++. I have previously had a data structure in an interview criticised for being too C-like (no iterators and using new/delete) instead of smart pointers. For the iterator, I'm not quite sure what I should do for operator->. Should its behaviour change depending on whether T is a primitive type or not? Also, what should be done so that this iterator would be compatible with stl algorithms such as sort etc?

For the question of using smart pointers or not, IMO the handling of the allocation/freeing of memory in the constructors is sufficient and is better than each ListNode having a shared pointer to the next node. Is this logic correct?

Thanks!

template<typename T>
class List{
    public:
        struct ListNode{
            T val_;
            ListNode *next_;

            ListNode() : val_(T()), next_(nullptr){}
            ListNode(const T& val) : val_(val), next_(nullptr){}
            ListNode(const T& val, ListNode *next) : val_(val), next_(next){}
            ListNode(ListNode *next) : val_(T()), next_(next){}
        };
        class iterator{
        public:
            using value_type = ListNode;
            using reference = ListNode&;
            using pointer = ListNode*;
            using difference_type = std::ptrdiff_t;
            using iterator_category = std::forward_iterator_tag;
            iterator(pointer ptr) : ptr_(ptr){}
            bool operator==(const iterator &other){return other.ptr_ == ptr_;}
            bool operator!=(const iterator &other){return other.ptr_ != ptr_;}
            iterator& operator++(){
                ptr_ = ptr_->next_;
                return *this;
            }
            iterator operator++(int arg){
                iterator tmp = *this;
                ptr_ = ptr_->next_;
                return tmp;
            }
            pointer operator->(){
                return ptr_;
            }
            reference operator*(){
                return *ptr_;
            }
        private:
            pointer ptr_;
        };
        ListNode *tail_, *before_begin_;
        List() : tail_(new ListNode), before_begin_(new ListNode(tail_)){ }
        ~List(){
            ListNode *current = before_begin_;
            while(current != tail_){
                ListNode *next = current->next_;
                delete current;
                current = next;
            }
            delete tail_;
        }
        List& operator=(const List &other){
            if(before_begin_ != nullptr){
                delete before_begin_;
            }
            if(tail_ != nullptr){
                delete tail_;
            }
            return *this = List(other);
        }
        List(List &&other) noexcept{
            before_begin_ = other.before_begin_;
            tail_ = other.tail_;
            other.before_begin_ = nullptr;
            other.tail_ = nullptr;
        }
        List& operator=(List &&other) noexcept{
            before_begin_ = other.before_begin_;
            other.before_begin_ = nullptr;
            tail_ = other.tail_;
            other.tail_ = nullptr;
            return *this;
        }
        List(const List &other) {
            tail_ = new ListNode(other.tail_);
            before_begin_ = new ListNode(other.before_begin_->val_, tail_);
            ListNode *other_current = other.before_begin_;
            ListNode *other_tail = other.tail_;
            ListNode *current = before_begin_;
            while(other_current != other_tail){
                current->next_ = new ListNode(other_current->val_);
                current = current->next_;
                other_current = other_current->next_;
            }
            current->next_ = tail_;
        }
        T& front(){
            return before_begin_->next_->val_;
        }
        void pop_front(){
            ListNode *tmp = before_begin_->next_;
            before_begin_->next_ = tmp->next_;
            delete tmp;
        }
        iterator push_front(const T& val){
            ListNode *tmp = before_begin_->next_;
            before_begin_->next_ = new ListNode(val, tmp);
            return iterator(before_begin_->next_);
        }
        iterator insert_after(iterator position, const T& val){
            ListNode *tmp = position->next_;
            position->next_ = new ListNode(val, tmp);
            return iterator(position->next_);
        }
        iterator erase_after(iterator position){
            ListNode *tmp = position->next_;
            position->next_ = tmp->next_;
            delete tmp;
            return iterator(position->next_);
        }
        iterator begin(){
            return iterator(before_begin_->next_);
        }
        iterator end(){
            return iterator(tail_);
        }
};
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

I don't see why not using smart pointers in such a basic data structure is bad. You may use std::unique_ptr for allocation and de-allocation of your ListNodes, but in the end you'll just introduce a new header and STL dependency, so in this case I'd think it's fine doing without. For primitive types, what should operator-> return in your opinion? To get compatibility with standard algorithms, see on how STL containers implement common functions.

  • Do you need access to ListNode from the outside of the class? Consider making it private. Same goes for tail_ and before_begin_.
  • In iterator operator++(int arg) you can remove the arg it is not needed and compilers may complain about unused variables with the right warning settings.
  • Why before_begin_? Isn't a ListNode* first; better?
  • In your constructors you're initializing before_begin_ and tail_, but in your move-constructors you're leaving the members with nullptrs. Consider having the move functions leaving the functions in a default constructed state (though having nullptrs is better IMO).
  • Regarding operator= and copy construction, please read about the copy-and-swap idiom.
  • using erase_after and insert_after is not very common. Check the STL documentation on how STL containers support erasing or inserting data.
  • In operator= you'll leak memory if the list is filled. Maybe provide a clear method and use it in ~List() and operator=().
\$\endgroup\$

Your Answer

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

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