Singly Linkedlist implementation in C++

Question

I'm implementing a linkedlist in C++ with the essential functionalities.

I would like to know what is good in this code and what is bad. In terms of everything (memory usage, functions implementations and optimization, naming conventions, etc...)

I also would like to know how to apply the modern c++ concepts to such code. (Smart pointers, constexpr, lambda expressions, etc...)

Header file:

#ifndef BLINKEDLIST_H
#define BLINKEDLIST_H
#include <memory>
struct Node
{
 int key;
 Node* next;
};
class BLinkedlist
{
public:
 BLinkedlist();
 void push_back(int value);
 void push_front(int value);
 void insert(int idx, int value);
 int pop_front();
 int pop_back();
 void erase(int idx);
 int remove_value(int value); //removes the first item in the list with this value
 void display();
 bool empty();
 int value_at(int idx);
 int value_n_from_end(int idx);
 int front();
 int back();
 void reverse();
private:
 int size;
 Node* head;
 Node* tail;
};
#endif // BLINKEDLIST_H

Source file:

#include "blinkedlist.h"
#include <stdexcept>
#include <iostream>
BLinkedlist::BLinkedlist():size(0), head(nullptr), tail(nullptr)
{
}
void BLinkedlist::push_back(int value)
{
 Node* newNode = new Node();
 newNode->key = value;
 if(head != nullptr)
 {
 tail->next = newNode;
 }
 else
 {
 head = newNode;
 }
 tail = newNode;
 newNode->next = nullptr;
 ++size;
}
void BLinkedlist::push_front(int value)
{
 Node* newNode = new Node();
 newNode->key = value;
 if(head != nullptr)
 {
 newNode->next = head;
 }
 else
 {
 newNode->next = nullptr;
 tail = newNode;
 }
 head = newNode;
 ++size;
}
void BLinkedlist::insert(int idx, int value)
{
 if(idx < 0 || idx > size)
 {
 throw std::out_of_range("Index is out of range!");
 }
 else
 {
 Node* newNode = new Node();
 newNode->key = value;
 if(idx == 0)
 {
 push_front(value);
 }
 else if(idx == size)
 {
 push_back(value);
 }
 else
 {
 Node* curr = head;
 int i = idx-1;
 while(i > 0)
 {
 curr = curr->next;
 --i;
 }
 newNode->next = curr->next;
 curr->next = newNode;
 ++size;
 }
 }
}
int BLinkedlist::pop_front()
{
 if(head != nullptr && size >= 2)
 {
 int val = head->key;
 head = head->next;
 --size;
 return val;
 }
 else if(head != nullptr && size == 1)
 {
 int val = head->key;
 head = nullptr;
 tail = nullptr;
 --size;
 return val;
 }
 else
 {
 throw std::logic_error("List is already empty!");
 }
}
int BLinkedlist::pop_back()
{
 if(head != nullptr && size > 2)
 {
 int val;
 Node* curr = head;
 while(curr->next->next != nullptr)
 {
 curr = curr->next;
 }
 val = curr->next->key;
 curr->next = nullptr;
 tail = curr;
 --size;
 return val;
 }
 else if(head != nullptr && size == 2)
 {
 int val = head->next->key;
 tail = head;
 --size;
 return val;
 }
 else if(head != nullptr && size == 1)
 {
 int val = head->key;
 head = nullptr;
 tail = nullptr;
 --size;
 return val;
 }
 else
 {
 throw std::logic_error("List is already empty!");
 }
}
void BLinkedlist::erase(int idx)
{
 if(idx < 0 || idx > size)
 {
 throw std::out_of_range("Index is out of range!");
 }
 else
 {
 if(idx == 0)
 {
 pop_front();
 }
 else if(idx == size)
 {
 pop_back();
 }
 else
 {
 Node* curr = head;
 int i = idx-1;
 while(i > 0)
 {
 curr = curr->next;
 --i;
 }
 curr->next = curr->next->next;
 --size;
 }
 }
}
int BLinkedlist::remove_value(int value)
{
 Node* curr = head;
 int i = 0;
 while(curr != nullptr)
 {
 if(curr->key == value)
 {
 erase(i);
 return i;
 }
 curr = curr->next;
 ++i;
 }
 return -1;
}
void BLinkedlist::display()
{
 Node* curr = head;
 while(curr != nullptr)
 {
 std::cout << curr->key << std::endl;
 curr = curr->next;
 }
}
bool BLinkedlist::empty()
{
 return size == 0;
}
int BLinkedlist::value_at(int idx)
{
 Node* temp = head;
 if(idx < 0 || idx > size)
 {
 throw std::out_of_range("Index is out of range!");
 }
 else
 {
 int i = idx;
 while(i != 0 && temp != nullptr)
 {
 temp = temp->next;
 --i;
 }
 return temp->key;
 }
}
int BLinkedlist::value_n_from_end(int idx)
{
 if(idx < 0 || idx > size)
 {
 throw std::out_of_range("Index is out of range!");
 }
 else
 {
 int forwardIdx = size - idx;
 if(idx == 0)
 return tail->key;
 Node* curr = head;
 while(forwardIdx > 0)
 {
 curr = curr->next;
 --forwardIdx;
 }
 return curr->key;
 }
}
int BLinkedlist::front()
{
 return head->key;
}
int BLinkedlist::back()
{
 return tail->key;
}
void BLinkedlist::reverse()
{
 Node* next = nullptr;
 Node* prev = nullptr;
 Node* curr = head;
 while(curr != nullptr)
 {
 next = curr->next;
 curr->next = prev;
 prev = curr;
 curr = next;
 }
 head = prev;
}

And usage:

#include <iostream>
#include "blinkedlist.h"
int main()
{
 BLinkedlist list;
 list.push_back(1);
 list.push_back(2);
 list.push_back(3);
 list.push_back(4);
 list.push_back(5);
 list.push_back(6);
 list.display();
 std::cout << "----------------------" << std::endl;
 list.reverse();
 list.display();
 return 0;
}

Any notes and suggestions are much appreciated.

• 1201ProgramAlarm: Your code leaks memory like a sieve, because you call new to allocate Nodes but never delete any, which (arguably) makes the question borderline off topic. Edit your question to address this problem.
• Michael Karcher: The unique_ptrized version I created on Compiler Explorer actually fixes all the leaks.

Answer 1

Design

Please use a namespace for your classes. Polluting the global namespace is bad practice.

You implemented a singly linked list. With just a tiny bit more effort you could have implemented a doubly linked list which is arguably much easier to add all the functionality you would expect.

You use head/tail with nullptr. This means your code is full of tests for a nullptr. If you use a "Sentinel" then this will simplify the code tremendously and remove the need to check for nulls at all. Thus making it much easier to validate that you have done the code correctly.

Pop and guarantees. OK your pop_XX() work for you because you only support integer inside your list. But in the general case you can not support a pop that returns a value modifies the list and implements the strong exception guarantee. So what is the strong exception guarantee? Its a promise that your function either works correctly or throws an exception and does not change the state of the class. To solve this problem the standard containers do not return a value for pop_XX() instead they simple remove the item and return nothing (but provide a way of looking at the top thing that would be poped (back() front()). You may want to implement them the same way.

You have not made your object const correct. Any function that does not mutate the state of the object should be marked const.

The container is not templatized?

Implementations.

You have not implemented any memory management.

So your list leaks memory everywhere.

{
 BLinkedlist list;
 list.push_back(1);
}
// You just leaked a Node.
 

Also you have not implemented the rule of three. So your class has serious errors when it comes to copying and would blow up if you added the delete you require. Currently it will just behave oddly and/or leak when you copy it.

{
 BLinkedlist list1;
 list1.push_back(1);
 BLinkedlist list2(list1);
 list2.push_back(8);
 list1.display(); // Why does this list have an 8 in it?
}

You have not added any MOVE semantics. This means that in situations where the list could be moved your code actually would have to copy (but does not since you did not implement the rule of three). This would mean that it is ineffecient to move your list around.

BLinkedlist createList()
{
 ... STUFF
}
{
 BLinkedlist data = createList(); // We have a copy here
 // When it could have been moved
}

You use index's to refer to positions in the list.
If you look at the standard library you will see we have abstracted away the concept of indexes (and pointers) to use iterators. I would take a look at the standard library to see how you can implement iterators for your class.

Also iterators are the interface between containers and algorithms. If your container does not support iterators then you can not use the standard algorithms on your container (these can be very useful).

Examples:

Please have a look at this example.

https://codereview.stackexchange.com/a/126007/507

It shows (at the end) how to implement a doubly linked list with a sentinel. You will see that the code is much simplified as a result.

Code Review

What does memory provide that you need in the header?

#ifndef BLINKEDLIST_H
#define BLINKEDLIST_H
#include <memory>

---

Why is the node publicly available?

struct Node
{
 int key;
 Node* next;
};

I would make this a private member of BLinkedlist.

---

class BLinkedlist
{
public:
 BLinkedlist();
 // No destructor. Would expect this for anything the managed resources.
 ~BLinkedlist();
 // No copy operations.
 // Would expect this for anything with a destructor (ie had resources).
 BLinkedlist(BLinkedlist const&);
 BLinkedlist& operator=(BLinkedlist const&);
 // No move operators:
 // Anything with expensive copy should look at having a move
 BLinkedlist(BLinkedlist&&) noexcept;
 BLinkedlist& operator=(BLinkedlist&&) noexcept;
 // No swap function
 void swap(BLinkedlist&) noexcept;

---

Like normal variables I would iniutialize one member per line.

BLinkedlist::BLinkedlist():size(0), head(nullptr), tail(nullptr)
{
}
// Like this:
BLinkedlist::BLinkedlist()
 : size(0)
 , head(nullptr)
 , tail(nullptr)
{}

---

You can make your code a lot simpler by creating and initializing the value in a single line:

void BLinkedlist::push_back(int value)
...
void BLinkedlist::push_front(int value)
...
/// Like this:
void BLinkedlist::push_back(int value)
{
 Node* newTail = new Node{value, nullptr};
 if (tail == nullptr)
 {
 head = newNode;
 }
 else
 {
 tail->next = newTail;
 }
 tail = newNode;
 ++size;
}
void BLinkedlist::push_front(int value)
{
 head = new Node{value, head};
 if(tail == nullptr)
 {
 tail = head;
 }
 ++size;
}

---

Using an iterator would have really simplified this function:

void BLinkedlist::insert(int idx, int value)

This is because your internal representation of the iterator can can accesses the nodes in the list directly and simply allow you to directly manipulate them. Also it would remove the need to check that you are inside the list as valid iterators are always inside the list.

---

I don't see the need to check for the size in this function.

int BLinkedlist::pop_front()
{
 if(head != nullptr && size >= 2)
 {
 int val = head->key;
 head = head->next;
 --size;
 return val;
 }
 else if(head != nullptr && size == 1)
 {
 int val = head->key;
 head = nullptr;
 tail = nullptr;
 --size;
 return val;
 }

I would simplify to:

 Node* old = head;
 head = old->next;
 if (head == nullptr) { 
 tail = nullptr;
 }
 --size;
 return old->value; // Yes yes I am still ignoring the delete.

Note: if the size is 1. Then head->next will also be nullptr

But if you take the suggestion above and make the pop_XX() function not return anything then deleting the head becomes much simpler.

---

OK. See lots of people do this.

void BLinkedlist::display()
{
 Node* curr = head;
 while(curr != nullptr)
 {
 std::cout << curr->key << std::endl;
 curr = curr->next;
 }
}

First thing is that std::cout is not the only stream. So you should allow the user to pass the actual stream as a parameter. It can of course default to std::cout.

Next. Why are you using a while loop here. for() is much more concise (and most people would expect for here).

Next: This function does not mutate the object so we should mark it const.

Last: Prefer '\n' to std::endl. The difference is that \n will not flush the stream. Manually flushing the stream like this is the source of nearly all performance issues of the C++ streams. The stream will flush itself at the appropriate time so you usually don't need to force it.

void BLinkedlist::display(std::ostream& str = std::cout) const
{
 for(Node* curr = head; curr != nullptr; curr = curr->next)
 {
 str << curr->key << "\n";
 }
}

OK. Now that we can pass any stream in here you can add the standard way to stream output by defineing the output operator.

std::ostream& operator<<(std::ostream& str, BLinkedlist const& data)
{
 data.display(str);
 return str;
}

Now you can do this:

int main()
{
 BLinkedlist list;
 // Add Items.
 std::cout << "Add list to output: " << list << "\n";
}

---

Should be const

bool BLinkedlist::empty()
int BLinkedlist::value_at(int idx)
int BLinkedlist::value_n_from_end(int idx)
int BLinkedlist::front()
int BLinkedlist::back()

---

Note: When you templatize the class you will want to return by reference.

int BLinkedlist::front()
{
 return head->key;
}

Which will also make you want to write two versions (a const and non const version)

• Michael Karcher: Well, technically the OP obeyed the "rule of three". It says that if a class has one of destructor, copy ctor or copy assignment, it needs all of them. As the OP missed the need to implement the destructor, the rule did not kick in at all. Of course the problems arising from copying a BLinkedlist with the implicitly generated operators still need to be fixed, though.
• Loki Astari: @MichaelKarcher Your understanding of the rule of three is not complete. The rule of three is that if you **need** any of the three then you need to implement all of them. As you noted the destructor is needed.
• jmarkmurphy: @MartinYork But as far as the OP knew (since he didn't realize the importance of the destructor) he did follow the rule of three, if in fact he was aware of it, and considered it! Otherwise it would state: "just add the other two whether you think you need the destructor or not".
• Loki Astari: @jmarkmurphy Did he. The copy constructor compiles but does not work as expected. because he did not follow the rule of three. See the section "Implementations" above.

Answer 2

What do I like?

1. You use an initializer list in the constructor of Blinkedlist, and you are initializing all the primitive-type members in the correct order.
2. You are using the more safe nullptr keyword instead of plain old NULL.
3. You try to resemble the STL container interface that is well-known by C++ programmers.
4. Mimicking the interface even extends to using the C++ standard exception classes.
5. insert contains a useful optimization by detecting the push_back case.
6. There is a comment explaining the behaviour of remove_value in the case of repeated values.

What do I dislike?

1. The code you wrote allocates memory with new, but it never deletes anything.
2. While pop_back and pop_front return the value of the deleted note, erase does not. This feels inconsistent.
3. The tests for head != nullptr in pop_front and pop_back are unnecessary. If size != 0, we can be sure that head != nullptr.
4. The special casing of pop_back for size == 2 is unneeded. It actually contains a bug: You forget to clear the next pointer in that case. The case for size > 2 actually works (without that bug) for size > 1.
5. remove_value iterates the list twice: Once to find the value and a second time to re-find the node in erase. You should either duplicate the erasure into this function, or provide an internal function that allows erasure of a Node given as a pointer to that node.
6. You do provide pop_back, although it is a very slow operation (on big lists).
7. value_n_from_end could be the one-liner return value_at(size-idx);. The reimplementation of value_at doesn't make sense. Maybe you want a check that size-idx does not overflow, though.
8. Behaviour on the empty list is inconsistent: pop_front and pop_back throw an exception, while front and back dereference nullptr without checking. I would have expected that either all nor none of these functions contain a throw statement for the empty list.
9. Node should be a private nested type inside Blinkedlist
10. It might be helpful to exercise all the functions in the usage example, so it doubles as unit test.

Let's get started with the most important question in my oppinion: Can we improve the code using smart pointers. And the answer is: Yes, a lot. Most importantly, my first dislike.

If your data structures and algorithms that need dynamic allocations (and yes, a singly linked list does not allocations) can be made to work with unique_ptr, the compiler will insert the delete statements automatically where appropriate. A unique_ptr only works if it is the one-and-only owner of an object.

You can not just make head and tail both std::unique_ptr<Node>, because (as an example) in a single-element list, both head and tail would point to the same Node, which obviously breaks uniqueness. Looking more in depth shows that each node is pointed to by its previous node, except for the first node, which is pointed to by head. On the other hand, the tail pointer does not point to anything "new" compared to that. So I would make Blinkedlist::head and Node::next unique pointers.

This means you also need to be more stringent where you transfer ownership, and be careful to not use a unique_ptr after transferring ownership.

Complete unique_ptr-ized example

• Loki Astari: What do I like? You put the good news first. What do I dislike? I don't agree on your assessment of using unique_ptr to implement the class. Sure you can. But if you look at C++ memory management there are two types of structures that manage memory. Smart pointers to manage single instances and containers to manage multiple objects. Both do memory management. This is a container so I would expect it to perform its own memory management. BUT for a beginner using unique_ptr can simplify the problem and get them going and concentrating on other issues so I suppose I can live with the advice.
• Michael Karcher: For me, the main thing we can learn by reviewing the code from the OP is that in cases where a clear unique ownership model can be expressed, unique_ptr should be the first choice. Only if there are compelling reasons that unique_ptr is unfit, alternatives should be considered. The only reason I see here is that unique_ptr needs all run-time context for the destruction acessible from within the unique_ptr object, so it does not mix well with a container-local stateful allocator. I consider pool allocators to be a premature optimization in this review.
• Loki Astari: I consider std::unique_ptr a premature optimization here that actually makes implementing the list using "Sentinels" harder. Sentinels are a better overall algorithm for this problem as it simplifies the code greatly.
• Michael Karcher: unique_ptr is intended to have the compiler automatically write the delete statements that are needed to avoid memory leaks. The overhead of unique_ptr is supposed to be neglegible in optimized build, because the abstraction layer gets optimized away. On the other hand shared_ptr is counting references at runtime, which can have noticable performance impacts. Furthermore, with unique_ptr, you have one clearly defined owner of an object and documented that owner. This is great! On the other hand, shared_ptr comes with the danger that you prematurely stop thinking about ownership.
• Michael Karcher: @BilalAhmed So my oppinion is: Whenever unique_ptr fits your application, there is no excuse to not use it. It helps deleting your objects exactly at the right time, even if exceptions are thrown. With C++14 and make_unique, you can get pointer semantics right without ever using new or delete manually. On the other hand, if you feel tempted to use shared_ptr, think again whether there really is no well-defined owner. When you decide that shared ownership indeed is what you need, do use shared_ptr instead of re-inventing the wheel.