I am trying to use smart pointers (std::unique_ptr) to create a singly linked list. Here is an example of a singly linked list with raw pointer.

struct Node {
  int data;
  Node *next = nullptr;
  Node(int data) : data{data}, next{nullptr} {}
  ~Node() { std::cout << "Destroy node with data: " << data << '\n'; }
};

void print_list(Node *head) {
  while (head != nullptr) {
    cout << head->data << " --> ";
    head = head->next;
  }
  cout << "nullptr" << std::endl;
}

void insert(Node *&head, int data) {
  Node *new_node = new Node{data};
  new_node->next = head;
  head = new_node;
}

int main(int argc, char *argv[]) {
  Node *head = nullptr;
  for (int i = 0; i < 5;   i) {
    insert(head, i);
  }
  print_list(head);
  return 0;
}

The output is:

4 --> 3 --> 2 --> 1 --> 0 --> nullptr

Apparently there is memory leak in the above code (destructor is not called). Now I want to use smart pointer to achieve the same thing:

struct Node {
  int data = 0;
  std::unique_ptr<Node> next;
  Node(int data) : data{data}, next{nullptr} {}
  ~Node() { std::cout << "Destroy node with data: " << data << '\n'; }
};

void print_list(std::unique_ptr<Node> head) {
  while (head != nullptr) {
    std::cout << head->data << " --> ";
    head = std::move(head->next);
  }
  std::cout << "nullptr" << std::endl;
}

void insert(std::unique_ptr<Node> &&head, int data) {
  std::unique_ptr<Node> new_node{std::make_unique<Node>(data)};
  new_node->next = std::move(head);
  head = std::move(new_node);
}

// g   -std=c  17 -Wall 2_1.cpp && ./a.out
int main(int argc, char *argv[]) {
  std::unique_ptr<Node> head{nullptr};
  for (int i = 0; i < 5;   i) {
    insert(std::move(head), i);
  }
  print_list(std::move(head));
  return 0;
}

The output is:

4 --> Destroy node with data: 4
3 --> Destroy node with data: 3
2 --> Destroy node with data: 2
1 --> Destroy node with data: 1
0 --> Destroy node with data: 0
nullptr

We can observe that the life time of new_node ends when insert() returns. I would like to know if it's possible to use smart pointers to achieve singly linked list and retains the functions interface as above.

CodePudding user response：

First thing, there is a problem with your print_list implementation(for both version for unique_ptr only). With your print_list, every time you assign head with a different uniq_ptr, you are actually deallocating the only Node in head, which is not desired. Instead, in your print_list, you should first create a temporary pointer pointing to head, then only iterate on the temporary pointer.

Now onto your unique_ptr version, you don't have to pass a unique_ptr as rvalue reference, you can also pass it as lvalue reference. Instead, your function signature would probably look like:

void print_list(const std::unique_ptr<Node>& head);
void insert(std::unique_ptr<Node> &head, int data);

This allow you to call them without using std::move in your main.

Now on to definitions. For your insertion, what you have is you first create a new Node with the given value, then you assign the old head to new node's next, and make the new node as the new head:

void insert(std::unique_ptr<Node> &head, int data)
{
    // Use `auto` to avoid typing `....<Node>` twice
    auto new_node = std::make_unique<Node>(data);
    new_node->next = std::move(head);
    head = std::move(new_node);
}

Alternatively, you can also add one more parameter to Node's constructor:

Node(int data, std::unique_ptr<Node>&& next = nullptr) 
: data{data}, next{std::move(next)}
{}

Now you can simply create new_node like:

void insert(std::unique_ptr<Node> &head, int data)
{
    // No need to assign `Node::next` separately
    auto new_node = std::make_unique<Node>(data, std::move(head));
    head = std::move(new_node);
}

Or even assign the new node to head directly:

void insert(std::unique_ptr<Node> &head, int data)
{
    head = std::make_unique<Node>(data, std::move(head));
}

For print_list, we should first create a temporary pointer that points to the underlying object of head, then iterate the list by assigning the temporary pointer to its next object's underlying object:

void print_list(const std::unique_ptr<Node>& head)
{
    // Create a pointing to the underlying object
    // You can use `.get()` to get the underlying pointer
    auto current = head.get();

    // No need to explicit compare pointer types to `nullptr`
    while (current) {
        std::cout << current->data << " --> ";
        // Make `current` point to the next underlying object
        current = current->next.get();
    }
    std::cout << "nullptr" << std::endl;
}

Now your main would look like:

int main(int, char *[]) {
    std::unique_ptr<Node> head;
    for (int i = 0; i < 5;   i) {
        insert(head, i);
    }
    print_list(head);
    return 0;
}

Demo