Example of a singly linked list in C++

Some advices that you should follow to avoid further bugs:

• You should verify preconditions, especially in the methods front, back, pop_front, pop_back and throw an std::out_of_range or a std::logic_error if the list is empty before the call.

• You should add the operator= method. The implicit generated one will generate segmentation faults since the list cells will be shared (and destroyed) by two different lists.

• You should add a method verifyInvariant (class invariant) that verifies that size_ is the size of the chain starting from first_.

You also can improve the usage of your class with new methods like:

• You can add a swap method and a copy constructor with xvalue argument to avoid some copies that are not useful.

Inside your methods:

• You can use auto each time the name of the local variable implicitly gives its type.

• If you use new Link<T>{} instead of new Link<T>(), all fields of the cells will be 0-initialized, avoiding some undefined behaviors in case of missing code.

• Think that an exception could be launched on every function/method call, so avoid allocations far from their integration into the list (see push_back) to avoid memory leaks in case of exceptions. Also keep in mind that the class invariant should be preserved in case of exceptions.

• You could choose better names than index1 and index2 in the copy constructor. We don't know on which list they iterate.

• The method reverse should not allocate any cell.

Here are the main modifications of the previous remarks on your code. Hope it helps.

For copy, assignment methods:

//Copy constructor
SLinkedList(SLinkedList<T>&& other) { swap(other); }
SLinkedList(const SLinkedList<T>& other) { copy(other); }
SLinkedList& operator=(const SLinkedList<T>& other)
  {  if (this != &other)
         copy(other);
     return *this;
  }
SLinkedList& operator=(SLinkedList<T>&& other)
  {  swap(other);
     return *this;
  }

For access methods:

//Index operator
T& operator[](int i) {
    if(first_) {     
        if(i < 0 || i >= size_)
            throw std::out_of_range("index out of range!!!");
        // more evident to verify that i >=0 and i < size
        if(i == 0) return first_->val;

        auto* index = first_;
        for(int it=0; it<i; it++) index = index->next;
        return index->val;
    }
    else throw std::out_of_range("empty list!!!");
}

//Access first element 
T& front() {
    if (!first_) // verify preconditions
      throw std::logic_error("empty list");
    return first_->val;
}

//Access last element
T& back() {
    if (!first_) // verify preconditions
      throw std::logic_error("empty list");
    return end()->val;
}

For the insertion methods:

//Add an element at the begining
void push_front(const T& value) {
    Link<T>* temp = new Link<T>{};
    temp->val = value;
    temp->next = first_;
    first_ = temp;
    size_++;
}

//Add an element at the end
void push_back(const T& value) {
    Link<T>** insertionPoint = &first_;
    while (*insertionPoint)
        insertionPoint = &((*insertionPoint)->next);

    // allocate it at the last time: this avoids memory leaks
    // in case of exception in the end() method for example.
    Link<T>* temp = new Link<T>{};
    temp->val = value;
    temp->next = nullptr;
    (*insertionPoint) = temp;
    size_++;
}

For the remove methods:

//Delete first element
void pop_front() {
    if(first_) {
        Link<T>* first = first_->next;
        delete first_;
        first_ = first;
        size_--;
    }
    else
      throw std::logic_error("empty list");
}

//Delete last element
void pop_back() {
    if(first_) {
        Link<T>* index = first_;
        Link<T>* previousIndex = nullptr;
        while(index->next) {
            previousIndex = index;
            index = index->next;
        }
        if (first_ == index)
          first_ = index->next;
        delete index;
        previousIndex->next = nullptr;
        size_--;
    }
    else
      throw std::logic_error("empty list");
}

Two implementation for the reverse method:

void reverse() {
    if(first_ && first_->next) {
        // memory leaks in case of exceptions
        auto* previousIndex = nullptr;
        auto* index = first_;
        auto* nextIndex = index->next;
        do {
            index->next = previousIndex;
            previousIndex = index;
            index = nextIndex;
            nextIndex = index->next;
        } while (nextIndex);
        first_ = index;
    };
}

or more exception-safe

void reverse() {
    if(first_ && first_->next) {
        Link<T> temp;
        temp.swap(*this);
        do {
            auto* cell = temp.first_;
            temp.first_ = temp.first_.next;
            --temp.size;
            cell->next = first_;
            first_ = cell;
            ++size_;
        } while (temp.first_);
    };
}

Additional methods:

void swap(Link<T>& other) {
    auto* tempFirst = first_;
    auto* tempSize = size_;
    first_ = other.first_;
    size_ = other.size_;
    other.first_ = tempFirst;
    other.size_ = tempSize;
}

bool verifyInvariant() const {
    int remainingCells = size_;
    auto* index = first_;
    while (--remainingCells >= 0) {
        if (!index)
            return false;
        index = index->next;
    };
    return index == nullptr;
}

private:
void copy(const SLinkedList<T>& other) {
    if (this != &other) {
        clear();
        if(other.first_) {
            first_ = new Link<T>();
            size_ = other.size_;
            auto* indexThis = first_; /* indexThis, indexOther instead of index1, index2 */
            auto* indexOther = other.first_;
            indexThis->val = indexOther->val;

            while(indexOther->next) {
                indexThis->next = new Link<T>{}; /* avoid accidental undefined behavior */
                indexThis = indexOther->next;
                indexOther = indexOther->next;
                indexThis->val = indexOther->val;
            }
        }
        else first_ = other.first_;
    }
}