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_);
}
};
