Linked List using templates and smart pointers

Question

I have an implementation of Linked List with push, pop, size, print and search functionalities. This is also an attempt to learn smart pointers. I have only used shared_pointers in this implementation.

#include <iostream>
#include <memory>
#include <cstddef>
// Class for individual nodes in the list
template<typename T>
class Node
{
 T val;
 std::shared_ptr<Node<T>> next = nullptr;
public:
 Node(T value)
 {
 val = value;
 }
 T get_val() const;
 void set_next(std::shared_ptr<Node<T>>);
 std::shared_ptr<Node<T>> get_next() const;
};
template<typename T>
T Node<T>::get_val() const
{
 return val;
}
template<typename T>
void Node<T>::set_next(std::shared_ptr<Node<T>> node)
{
 next = node;
}
template<typename T>
std::shared_ptr<Node<T>> Node<T>::get_next() const
{
 return next;
}
// Class for the Linked List
template<typename T>
class LinkedList
{
 /*std::shared_ptr<Node<T>> head = std::make_shared<Node<T>>(nullptr);
 std::shared_ptr<Node<T>> tail = std::make_shared<Node<T>>(nullptr);*/
 std::shared_ptr<Node<T>> head;
 std::shared_ptr<Node<T>> tail;
 std::size_t size_var = 0;
public:
 LinkedList()
 {
 }
 void push(T);
 T pop();
 int search(T) const;
 void print() const;
 std::size_t size() const;
};
// Insert node at head
template<typename T>
void LinkedList<T>::push(T value)
{
 auto new_node = std::make_shared<Node<T>>(value);
 // Check if the list already has values and push values at the head accordingly
 if(head == nullptr)
 {
 head = new_node;
 tail = new_node;
 }
 else
 {
 auto temp = head;
 head = new_node;
 new_node -> set_next(temp);
 }
 size_var++;
}
// Remove node at tail
template<typename T>
T LinkedList<T>::pop()
{
 T value = tail -> get_val();
 auto node = head;
 std::shared_ptr<Node<T>> prev;
 // Set the tail to second last value and set its next to nullptr.
 while(node)
 {
 if(node -> get_next() == nullptr)
 {
 //std::cout << "Tail count first: " << node.use_count() << "\n";
 tail = prev;
 //std::cout << "Tail count second: " << node.use_count() << "\n";
 tail -> set_next(nullptr);
 //std::cout << "Tail count third: " << node.use_count() << "\n";
 break;
 }
 prev = node;
 node = node -> get_next();
 }
 size_var--;
 return value;
}
//Returns the index of the value if found, else returns zero.
template<typename T>
int LinkedList<T>::search(T value) const
{
 auto node = head;
 int index = 0;
 while(node)
 {
 if(node -> get_val() == value)
 {
 return index;
 }
 node = node -> get_next();
 index++;
 }
 return -1;
}
// Print the list
template<typename T>
void LinkedList<T>::print() const
{
 auto node = head;
 std::cout << "Printing List: \n";
 while(node)
 {
 std::cout << node -> get_val() << "\t";
 node = node -> get_next();
 }
 std::cout << "\n";
}
// Return the size of the list
template<typename T>
std::size_t LinkedList<T>::size() const
{
 return size_var;
}
int main()
{
 LinkedList<int> ll{};
 for(int i = 8; i >= 0; i--)
 {
 ll.push(i);
 }
 ll.print();
 std::cout << "Size: " << ll.size() << "\n";
 std::cout << "Pop: " << ll.pop() << "\n";
 std::cout << "Size: " << ll.size() << "\n";
 std::cout << "Pop: " << ll.pop() << "\n";
 std::cout << "Size: " << ll.size() << "\n";
 ll.push(9);
 ll.print();
 std::cout << "Size: " << ll.size() << "\n";
 std::cout << "Search: " << ll.search(10) << "\n";
 std::cout << "Search: " << ll.search(5) << "\n";
 return 0;
}

The push inserts a new node or item at the head of the list while pop removes an item from the tail. The search returns an index or position of the item if value being searched for is found.

1. Is the usage of smart pointers correct? Are there any leaks, especially in pop?

2. Are there any place in this code where I should be using std::unique_ptr? I felt that there is always a possibility of more than one pointer being pointed to any node; hence I avoided std::unique_ptr.

3. What should be the return type of search, bool or int or std::size_t? If it is std::size_t, is std::optional the best way to indicate search failure?

Answer 1

1. I'd recommend avoiding returning the value from pop. If T's copy constructor throws, you lose the data. So I would introduce T top() const and use it along with non-returning void pop(). This approach is used in STL containers which have a pop method. Also calling pop on empty list leads to UB.

2. In my opinion, a linked list based on std::unique_ptr looks more natural. But if you switch to that you will lose some functionality used in your approach based on std::shared_ptr, like head and tail point to one node, and the lack of copy-constructor and assignment operator.

3. Having a search method is nice, but more generic would be having compatibility with forward iterators that makes it possible to use STL algorithms with your container.

4. You didn't define copy-constructor and assignment operator. Is that done intentionally because shared pointers were used? Try to make test returning local copy of a LinkedList object from the function; I wonder what the result would be. From my point of view, it would be nice to have more STL-like behavior for the container.

• skr: Thank you for the review. I didn't consider copy constructor and assignment operator because I was more focused on using smart pointers correctly and providing required functionality.