Implementing a single linked list using smart pointers (replace std::shared_ptr with std::unique_ptr)

Question

As an example code I've given here, I have the feeling the use of std::shared_ptr is wrong and should be replaced using a std::unique_ptr because there's no real shared ownership semantics, besides of temporary needs.

How could that code be refactored correctly, e.g. using std::unique_ptr instead?

#include <memory>
#include <iostream>
template<typename T>
class LinkedList {
private:
 template<typename U = T>
 struct Node {
 U data;
 std::shared_ptr<Node<U>> next;
 };
 std::shared_ptr<Node<T>> head;
public:
 Node<T> const* insert(int position, T data) {
 if(position < 0) {
 throw std::invalid_argument("Parameter 'position' must be greater or equal to 0.");
 }
 std::shared_ptr<Node<T>> node = head;
 int i = 0;
 for(;node && node->next && i < position; node = node->next, ++i);
 if(i != position) { // position is a value beyond the list positions
 throw std::out_of_range("Parameter 'position' is out of range of the linked list.");
 }
 std::shared_ptr<Node<T>> newNode = std::make_shared<Node<T>>();
 newNode->data = data;
 newNode->next = node ? node->next : nullptr;
 if(node) {
 node->next = newNode;
 }
 else {
 head = newNode;
 }
 return newNode.get();
 }
 // Other linked list operations ...
};
int main() {
 LinkedList<int> ll;
 auto newNode = ll.insert(0,5);
 std::cout << newNode->data << std::endl;
}

I thought the move constructor of std::unique_ptr should cover all assignments of std::unique_ptr<Node<T>> variables well, but obviously it doesn't out of the box.

---

See the working code to play with here please.

---

I well know this question is kind of borderline here, since I'm asking how to rewrite that code properly regarding the constraints I'm setting up.

Though I don't get in which direction I have to go with that, as all my attempts are failing so far. I think there must be an appropriate solution just using a std::unique_ptr.

Answer 1

Yes, you can and should use unique_ptr. Several places will need to change of course:

Iterating through the nodes can use raw pointers:

 auto node = head.get();
 int i = 0;
 for(;node && node->next && i < position; node = node->next.get(), ++i);
 if(i != position) { // position is a value beyond the list positions
 throw std::out_of_range("Parameter 'position' is out of range of the linked list.");
 }

Use unique_ptr instead of shared_ptr:

 auto newNode = std::make_unique<Node<T>>();
 newNode->data = data;
 if(node) {

unique_ptr can't be copied, only moved:

 newNode->next = std::move(node->next);
 node->next = std::move(newNode);
 return node->next.get();
 }
 else {
 head = std::move(newNode);
 return head.get();
 }

Note that at the end, newNode has been moved from and is an empty state. You can no longer return newNode.get(). What was in newNode either ended up in some node's next or head by the end of the function.

• πάντα ῥεῖ: That looks promising, I just avoided to use get() to refer to the raw pointers currently.
• David: @πάνταῥεῖ raw pointers shouldn't be avoided as long as they don't own anything. Only unique_ptr and shared_ptr should own memory, but raw pointers can safely be used to access them.
• πάντα ῥεῖ: std::weak_ptr's to clarify semantics may be?
• David: @πάνταῥεῖ weak_ptr only relates to shared_ptr. The sort-of-equivalent of weak_ptr to unique_ptr is a raw pointer.
• πάντα ῥεῖ: Well, I see. THX for your answer.