Implemented Singly Linked List in C++

Question

I have re-implemented Singly Linked List based on previous review on this website. I have added iterators and remove mistakes. I did not use template classes because I have not learned about them yet.

SinglyList.hpp

#ifndef SINGLYLIST_HPP
#define SINGLYLIST_HPP
class Iterator;
class SinglyList
{
private:
 struct Node { int data; Node *next; };
 Node *head;
public:
 SinglyList(); //constructor
 ~SinglyList(); //distructor
 SinglyList(const SinglyList& rhs); //copy constructor
 SinglyList& operator=(const SinglyList& rhs); //assignment overload
 bool empty(); //check if list is empty
 int& front(); //return refrence to first element
 void pop_back(); //pop last element
 void pop_front(); //pop first element
 unsigned int size(); //return size of list
 void remove(int value); //remove passed value from list 
 bool search(int value); //return true if passed value found and vice versa
 void push_back(int value); //add an element at the end of list
 void push_front(int value); //add an element at the start of list
 Iterator begin() const; //begin iterator
 Iterator end() const; //end iterator
 friend class Iterator; //This class is friend of Iterator class
};
class Iterator 
{
private:
 SinglyList::Node *curr;
public:
 Iterator(); //constructor
 Iterator(SinglyList::Node *rhs); //parameterized constructor 
 int& operator *() const; //reference operator overload
 Iterator operator++ (int); //post increment operator overload 
 bool operator!=(const Iterator& rhs); //not equal operator overload 
 Iterator& operator=(const Iterator& rhs); //assignment overload
 friend class SinglyList; //This class is friend of SinglyList class
};
#endif // SINGLYLIST_HPP

SinglyList.cpp

#include "SinglyList.hpp"
SinglyList::SinglyList()
{
 head = nullptr;
}
SinglyList::SinglyList(const SinglyList& rhs)
{
 Node *temp = rhs.head, *newer = new Node;
 head = newer;
 while (temp != nullptr)
 {
 newer->data = temp->data;
 temp = temp->next;
 if (temp != nullptr)
 {
 newer->next = new Node;
 newer = newer->next;
 }
 else
 newer->next = nullptr;
 }
}
SinglyList& SinglyList::operator=(const SinglyList& rhs)
{
 if(head != nullptr)
 {
 Node *prev = nullptr;
 while(head != nullptr)
 {
 prev = head;
 head = head->next;
 delete prev;
 }
 }
 Node *temp = rhs.head, *newer = new Node;
 head = newer;
 while (temp != nullptr)
 {
 newer->data = temp->data;
 temp = temp->next;
 if (temp != nullptr)
 {
 newer->next = new Node;
 newer = newer->next;
 }
 else
 newer->next = nullptr;
 }
 return *this;
}
SinglyList::~SinglyList()
{
 Node* prev = nullptr;
 while (head != nullptr)
 {
 prev = head;
 head = head->next;
 delete prev;
 }
}
bool SinglyList::empty()
{
 return head == nullptr;
}
int& SinglyList::front() 
{
 return head->data;
}
unsigned int SinglyList::size()
{
 Node* temp = head;
 unsigned int count = 0;
 while (temp != nullptr)
 {
 temp = temp->next;
 count++;
 }
 return count;
}
void SinglyList::push_front(int value)
{
 Node* newer = new Node;
 newer->data = value;
 if (empty())
 {
 head = newer;
 newer->next = nullptr;
 }
 else
 {
 newer->next = head;
 head = newer;
 }
}
void SinglyList::push_back(int value)
{
 Node* newer = new Node;
 newer->data = value;
 if (empty())
 {
 newer->next = nullptr;
 head = newer;
 }
 else
 {
 Node* temp = head;
 while (temp->next != nullptr)
 {
 temp = temp->next;
 }
 newer->next = nullptr;
 temp->next = newer;
 }
}
void SinglyList::remove(int value)
{
 if(!empty()) 
 {
 Node *temp = head, *prev = nullptr;
 if (temp->data == value)
 head = temp->next;
 else
 {
 while (temp->next != nullptr && temp->data != value)
 {
 prev = temp;
 temp = temp->next;
 }
 if (temp->data == value)
 prev->next = temp->next;
 }
 delete temp;
 }
}
bool SinglyList::search(int value)
{
 if (empty())
 return false;
 else
 {
 bool check = false;
 Node* temp = head;
 while (temp != nullptr)
 {
 if (temp->data == value)
 {
 check = true;
 break;
 }
 else
 temp = temp->next;
 }
 return check;
 }
}
void SinglyList::pop_front()
{
 Node* temp = head;
 head = temp->next;
 delete temp;
}
void SinglyList::pop_back()
{
 if(!empty())
 {
 Node *temp = head, *prev = nullptr;
 if (head->next == nullptr)
 head = temp->next;
 else
 {
 while (temp->next != nullptr)
 {
 prev = temp;
 temp = temp->next;
 }
 prev->next = nullptr;
 }
 delete temp;
 }
}
Iterator SinglyList::begin() const
{
 return Iterator(head);
}
Iterator SinglyList::end() const
{
 Node *temp = head;
 while(temp != nullptr)
 {
 temp=temp->next;
 }
 return Iterator(temp);
}
Iterator::Iterator() 
{
 curr = nullptr;
}
Iterator::Iterator(SinglyList::Node *rhs) 
{
 curr = rhs;
}
Iterator& Iterator::operator=(const Iterator& rhs) 
{
 curr = rhs.curr;
 return *this;
}
bool Iterator::operator !=(const Iterator& rhs) 
{
 return curr != rhs.curr;
}
int& Iterator::operator *() const
{
 return curr->data;
}
Iterator Iterator::operator ++(int)
{
 curr = curr->next;
 return *this;
}

main.cpp

#include "SinglyList.hpp"
#include <iostream>
int main() 
{
 SinglyList l1;
 l1.push_back(11);
 l1.push_front(10);
 l1.push_front(9);
 l1.push_front(8);
 Iterator it;
 for(it = l1.begin(); it != l1.end(); it++) 
 {
 std::cout << *it << " ";
 }
 std::cout << '\n';
}

• Daniel: Note that it's 'destructor', not 'distructor'.
• Cris Luengo: Not worth a full answer, but I would put the more trivial functions inside the definition of your class, in the header file. That will allow the compiler to inline that code. For example, your constructor is a single statement. Writing it inline would make that function relatively much less work to type (2 lines of code in 1 file rather than 3 lines in 2 files) and on top of that potentially speeds up execution.

Answer 1

A few thoughts:

Class naming

It's more important to know what an object does than to know the details of its implementation. Knowing that SinglyList is a type of "list" and that it can only be traversed easily in one direction are sometimes interesting to know, but IntegerList would be better (because it says what this is a list of). If you wanted to be more specific about the way the list works, you could call it ForwardIntegerList or IntegerForwardList; "Singly" is only an indirect way of implying "traversed more easily in one direction," whereas "Forward" describes that property more directly and also reminds us which direction is easier.

But I see you also have a class named Iterator--not SinglyList::Iterator, not SinglyListIterator, but just Iterator. Do you never intend to put this in any program with any other class that might need to be iterated over? This class should have a more specific name.

const functions

You should declare your functions const where you can. In particular empty, size, and search would typically be declared bool empty() const, unsigned int size() const, and bool search(int value) const. Not only is this a good reminder to you about whether it is safe to call a particular function when you don't want to modify the data structure, you can pass a const SinglyList& parameter to a function which can then call these functions of SinglyList.

It can be useful to have a const version of the front function too, but it should be declared const int& front() const or int front() const so that it doesn't provide a way to modify the contents of the list.

For the same reasons, it's good to have const versions of the begin and end functions (in fact, given how few ways one can access the interior of this list type, not having const versions of these functions would cripple any object passed as a const SinglyList&), but the functions you have return an iterator that can modify the contents of the list. That is not good: it makes the difference between a SinglyList& and a const SinglyList& practically meaningless. A typical way to fix this is to have a "const iterator" class in addition to your Iterator, where the "const iterator" has read-only access to the list: the * operator in the "const iterator" class would be const int& operator *() const or int operator *() const. (Compare iterator vs. const_iterator in STL; or maybe better still, look up the classes of the same names in the Qt documentation, which I find a little easier to navigate).

In any case, when begin and end return iterators that allow you to modify the list, those functions should not be const.

Don't declare variables before you need to

Consider this piece of code from SinglyList::operator =, for example:

 if(head != nullptr)
 {
 Node *prev = nullptr;
 while(head != nullptr)
 {
 prev = head;
 head = head->next;
 delete prev;
 }
 }

Instead, you could write

 if(head != nullptr)
 {
 while(head != nullptr)
 {
 Node *prev = head;
 head = head->next;
 delete prev;
 }
 }

There is no advantage whatsoever to declaring prev earlier than that; the first version of the code is more complicated and will not run any faster than the second version.

An empty list is not as special as you think

In several of your functions you treat an empty list as a special case that has to be checked before the code for the more general case can begin. In most places where you do this, it is not needed. For example, consider this piece of code in SinglyList::operator = again:

 if(head != nullptr)
 {
 Node *prev = nullptr;
 while(head != nullptr)
 {
 prev = head;
 head = head->next;
 delete prev;
 }
 }

You could replace this entire block of code with this:

 while(head != nullptr)
 {
 Node *prev = head;
 head = head->next;
 delete prev;
 }

What happens if you happen to pass an empty list into this function? Then head will be equal to nullptr when this block of code executes; the while condition will be false before the very first iteration, and the entire block of code will do nothing to the list--exactly the same as the more complicated if block would have. The only thing that is accomplished by putting the while inside an if is to hint to the compiler that it should compare the head of the list to nullptr twice. (I say "hint" because an optimizing compiler could very well decide to compile the two examples exactly the same; it can ignore your hint.)

Similarly, you could rewrite push_front like this:

void SinglyList::push_front(int value)
{
 Node* newer = new Node;
 newer->data = value;
 newer->next = head;
 head = newer;
}

What happens if you pass an empty list to this function? Then head will be equal to nullptr when the function is called, and newer->next = head; will set newer->next to nullptr, exactly as your version of this function does.

You can simplify push_back and search in similar ways.

Avoid duplication of code

There are two places in the definition of SinglyList where you have to remove all nodes from a list: operator = and the destructor. There are two places where you have to copy all the nodes from one list to another: operator = and the copy constructor. You could write a function for each of those tasks, and call those functions instead of making copies of their implementations. The function for removing all nodes would be like the clear function of STL containers, and might be useful to make public; but I would recommend that you make the copying function private, since calling it on an object that is not empty would cause a memory leak.