Transformation of Linked list from Raw pointers to Smart pointers

Question

How can I implement my linked list code from raw pointers to smart pointers? Any guidelines will be helpful. Here is my code.

I'm more confused about the type of smart pointer. Shared or unique and what will be the head? And how am I gonna delete this whole list in destructor?

#include <iostream>

class List {

private:

    struct Node {
        int datum;
        Node* next;

        Node(int d, Node* n):datum(d),next(n){std::cout<<"Constructor: "<<datum<<"\n";}
        ~Node(){std::cout<<"Destructor: "<<datum<<"\n";}
    };
    Node* head=nullptr;

public:
    
    ~List() {
        while (head) {
            Node *temp = head->next;
            delete head;
            head = temp;
        }
    }

    void append(int d) {
        Node* t = getLastNode(head);
        (t ? t->next : head) = new Node(d, nullptr);    
    }
    
    Node *getLastNode(Node *n) const {
        for (Node *it = n; it; it = it->next)
            if (!it->next)
                return it;
        return nullptr;
    }    
};

int main() { 
    List l1;
    l1.append(1);
    l1.append(2);
}

Answer 1

The List class can be re-implemented with the std::unique_ptr smart pointer in the following way.

Interface

template <typename T>
class List
{
private:
  struct Node
  {
    T                      value;
    std::unique_ptr<Node>  next;
  };

public:
  using value_type            = T;
  using pointer               = T*;
  using const_pointer         = const T*;
  using reference             = T&;
  using const_reference       = const T&;
  using size_type             = std::size_t;
  using difference_type       = std::ptrdiff_t;

  List();
  List(const List&);
  List(List&&);
  ~List();

  List& operator=(const List&);
  List& operator=(List&&);

  void push_front(const value_type&);
  void push_front(value_type&&);
  void pop_front();

private:
  std::unique_ptr<Node>  _head;
};

Design choices

1. unique_ptr vs shared_ptr

The C++ Standard provides two smart pointers, std::unique_ptr and std::shared_ptr.

The std::unique_ptr class is a thin wrapper around a raw pointer and the deleter, which, if empty, is compressed in order that it do not to cause any memory overhead. Its main feature is exclusive ownership: the object can and must be owned by only one instance of the smart pointer. For example, when a construct or assign operation is performed, the object owned by the source pointer is passed directly to the target one and, if the latter owned an object in turn, it is released.

The std::shared_ptr class is generally implemented as a wrapper around two pointers, one that points to the object and the other that points to a control block. The latter contains a reference counter, which is the mechanism that allows shared ownership: multiple instances of the smart pointer can share the same object at the same time. The only disadvantage is a higher heap memory and runtime overhead.

To choose which of the two pointers is more suitable in the case of the List class, it is necessary to understand whether it requires exclusive or shared ownership for the nodes. In this case, it is clear that the class, which is not implemented to allow sharing of its elements between two or more instances, is oriented towards exclusive ownership, making the choice of std::unique_ptr the most meaningful.

2. Destructor

The destructor that is automatically generated by the compiler is sufficient. Indeed, it requires only to invoke the destructor of the only member attribute of the class, _head, which will proceed to drop all elements in the sequence.

~List() = default;

The execution can be summarized as follows. Once the destructor of the head pointer has been called, it will call the destructor of the owned object, which corresponds to the first node. Since the latter contains a smart pointer as a member attribute, the destructor will in turn invoke that of the pointer. This chain reaction, where the destruction of a node is determined by the next pointer of the previous node, propagates throughout the sequence. Only at the last node, whose next pointer owns no object, the destruction can be completed without having to perform any other operations, allowing destruction and deallocation of the same object (destroy-deallocate). Then, the chain reaction propagates backward, as the destruction of one node allows the destruction of the previous next pointer and its node.

3. pop_front()

In the case of raw pointers, the pop_front() member function requires to perform two operations: adjust the pointers in order that the head pointer point to the second node; destroy and deallocate the first node. As in the previous case, the latter part is performed implicitly by the smart pointer, and therefore the only operation required remains linkage.

void pop_front() noexcept
{ this->_head = this->_head->next; }

This assignment forces the head pointer to take the value of the next pointer of the first node. In this way, the head pointer loses ownership of the first node, leading to its destruction.

4. push_front()

The push_front() member function requires an implementation that is essentially identical to the case of raw pointers. Indeed, it is necessary to allocate and construct the new node, which stores a copy/move of the input value, and adjust the pointers in order that it be inserted at the beginning of the sequence.

Otherwise, it is possible to summary the process in just one step with the std::make_unique() function.

void push_front(const value_type& v)
{ this->_head = std::make_unique<Node>(v, std::move(this->_head)); }

void push_front(value_type&& v)
{ this->_head = std::make_unique<Node>(std::move(v), std::move(this->_head)); }