##Design
You should look into the concept of "Sentinels". This is a fake node in your list (it has no data of its own). But by using a sentinel you never have an empty list and thus you never have to deal with nullptr this makes the code simpler to write (once you have given it some thought).
For every call to new there should be a call to delete. You don't do this. You need to be very explicit about these calls. In modern code we do away with new/delete by using smart pointers to manage memory.
In my opinion smart pointers solve 99.9% of the problems with pointers and you should not use pointers unless you are building a "Smart Pointer" or a "Container". No a "Liked List" is a container so you are going to have to handle them. But remember the standard library already contains liked list so in normal code you don't need to to build containers or smart pointers that has already been done for you.
You need to learn some basic C++ idioms. Here is some basics you should probably go and read about. I will cover most of this below at a very basic level. Then you should go and read about it.
- Rule of 3
This is the basics around which all C++ is built. It is the most important thing to learn in C++ and basically makes the language the power house that it is.
- Rule of 0
The rule of three is there to make sure that when you do resource management it is done correctly. But if you correctly contain all your resources then the rule of 3 makes writing anything else easy as the Rule of zero applies.
- Rule of 5
With modern move semantics we have given the developer more power to help the compiler optimizing. The move semantics simply allow us to remove some copies that made C++ inefficient. Learning the rule of 5 helps with this.
- Copy and Swap
This is an idiom that helps you implement the rule of three.
##Code Review
###Include Guard
Good start.
#ifndef LinkedList_hpp
#define LinkedList_hpp
But that may not be very unique. You should include your namespace name as part of the guard to give you a better chance of it being unique. Also the name of the class is SingleLinkedList so your guard should reflect that for when you add a DoubleLinkedList.
Note. It is also traditional the macros are all uppercase. I don't mind this but others may complain about it. Personally I make mine all uppercase to be consistent with other standards.
###Namespace
You don't use a namespace! Start practicing using your own namespace for your code. It will save you a lot of headaches one day.
#ifndef SNORRLAXXX_SINGLE_LINKED_LIST_HPP
#define SNORRLAXXX_SINGLE_LINKED_LIST_HPP
namespace Snorrlaxxx {
// STUFF
}
#endif
###Encapsulation
You don't need to expose this:
template<class T>
struct Node {
T data;
Node<T>* next;
};
This is an internal part of the linked list. Just declare it as a private member. Then you will not need to support it when it changes in the future (private parts of the code are implementation details that others can not use).
###Initializer List
Always prefer to use the initializer list.
SingleLinkedList() {
head = nullptr;
tail = nullptr;
}
When you have members that are initialized they will initially be initialized by the initializer list. The code in the constructor then overrides this and can cause extra work.
SingleLinkedList()
: head(nullptr)
, tail(nullptr)
{}
###Destructor
You really need to do the work here. Not just print something.
~SingleLinkedList(){
// TODO delete all the elements from head.
}
###DRY
Don't repeat yourself. A lot of your code involves creating a node and initializing it. You may want to have a specific private member function do this for you.
I see this bit of code a couple of times.
Node<T>* temp = new Node<T>;
temp->data = theData;
temp->next = nullptr;
You code add the code to the constructor of Node or just a private method on SingleLinkedList,
If we also a assume a sentinal (so there is always one node in the list even when empty) we rewrite your three insert methods:
void createNode(const T& theData) {
tail->next = new Node<T>(theData, nullptr);
tail = tail->next;
}
void insert_start(const T& theData) {
head = new Node<T>(theData, head);
}
void insert_position(int pos, const T& theData) {
head = insert_position(head, pos, theData);
}
private:
void insert_position(Node<T>* current, int pos, const T& theData)
{
if (pos == 0 || current == nullptr) {
return new Node<T>(theData, current == nullptr ? nullptr : current->next);
}
current->next = insert_position(current->next, pos - 1, theData);
return current;
}
###Some Leaks
Yikes:
Node<T>* previous = new Node<T>;
Node<T>* current = new Node<T>;
These two nodes are immediately leaked by overwriting them. No need to assign them values here just make them nullptr. You will notice that for both these new there is no equivalent delete.
Here by display() you mean print to std::cout. The one thing I would note is that std::cout is not the only stream. So I would change this to take a stream as a parameter (you can default it to std::cout).
void display() {
Node<T>* temp = head;
while(temp != nullptr) {
std::cout << temp->data << "\t";
temp = temp->next;
}
}
The second thing to note is that the normal way of printing things is to use operator<<.
std::cout << 5 << " Is a number: " << 2 << " Is another number\n";
Would it not be nice to use the same technique for your object. Will you can you just need to define the operator<< for your class.
void display(std::ostream& str = std::cout) {
// As you defined it before.
// just use `str` rather than `std::cout`
}
// Define this inside the class.
// By making it a friend it is just easier to declare and you
// don't need to worry about the template part.
friend std::ostream& operator<<(std::ostream& str, SingleLinkedList const& data) {
data.display(str);
return str;
}
###Copy Semantics
You did not deal with the rule of three.
{
SingleLinkedList<int> a;
a.createNode(5);
SingleLinkedList<int> b(a);
}
You did not define a copy constructor so you were not expecting one to part of your class. But if you don't define one (or delete it) then the compiler will define a default copy constructor for you. Most of the time this works perfectly. But if your class manages a resource (like memory (ie your class contains a RAW pointer)) then it will probably fail.
In the above case both a and b will end up pointing at the same storage. So when they go out of scope the destructor is supposed to delete the pointers. Because they both point at the same object they end up double deleting the memory.
The same rule applies to assignment.
{
SingleLinkedList<int> a;
a.createNode(5);
SingleLinkedList<int> b;
b.createNode(6);
a = b; // What happens here?
}
The same issue as the copy constructor. The compiler has generated an assignment operator for your class. First problem is that it leaked the original node the second problem is that you will get a double delete when the destructor is called.
Solution.
Delete the copy operations.
class SingleLinkedList
{
public:
SingleLinkedList(SingleLinkedList const&) = delete;
SingleLinkedList& operator=(SingleLinkedList const&) = delete;
};
Write your own copy operations.
class SingleLinkedList
{
public:
SingleLinkedList(SingleLinkedList const& value)
head(nullptr)
tail(nullptr)
{
for(Node* loop = value->head; loop != nullptr; loop = loop->next) {
createNode(loop->data);
}
}
// Implement assignment in terms of Copy constructor.
// This is known as the copy and swap idiom.
SingleLinkedList& operator=(SingleLinkedList const& rhs)
{
SingleLinkedList copy(rhs); // Use copy constructor to copy object.
swap(copy); // swap the copy and this.
} // Destructor of copy kicks in and deletes the original list.
void swap(SingleLinkedList& other) noexcept
{
usign std::swap;
swap(head, other.head);
swap(tail, other.tail);
}
};
###Move Semantics
When you deal with simple lists (ie of integer) copying data into the list is cheap and simple. But you have a list of expensive to copy objects then your standard copy is not sufficient,.
Think of createNode() when used with RocketShip.
SingleLinkedList<RocketShip> fleet;
It takes 6 months to create a new RocketShip so we want to minimize copying. You have done a good job by passing by reference (no copy). But the last step when you add it to the node you need to make a copy.
void createNode(const T& theData) {
Node<T>* temp = new Node<T>;
temp->data = theData; // Here you are copying a RocketShip
That's an expensive operation. To prevent this C++ has move semantics.
void createNode(const&& theData) {
Node<T>* temp = new Node<T>;
temp->data = std::move(theData); // Here you are moving a RocketShip
Notice the &&. This binds against objects that are being moved. A move operation moves the existing data out of an object and into another object (this is usually cheaper than copying).
Inside we are using std::move to tell the compiler to use the move assignment operator.
temp->data = std::move(theData);
// This make theData movable
// It will use the move assignment operator.
If your class does not have a move assignment operator then it will copy (so worst case senario it is the same cost as a copy). So integers are always copied. But you can potentially move a RocketShip if the class has a move assignment operator.
RocketShip& operator=(RocketShip&& rhs) noexpcept;