Building a simple singly-linked list in C++11

Question

The implementation below works, but I'm wondering if there's a modern C++ alternative.

For example:

• Should I replace the raw new with a braced initializer?
• Should I replace the Node* with a shared_ptr?

Let me know if you see any other things I could improve. I know I could also use a class, but I'd like to understand how to do this with struct.

#include <iostream>

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

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

void print_list(Node* list) {
  Node* p {list};
  std::cout << "Printing list: " << std::endl;
  if (p) {
    std::cout << p->data;
    p = p->next;
    while(p) {
      std::cout << " -> " << p->data;
      p = p->next;
    }
    std::cout << std::endl;
  }
}

int main(int argc, char* argv[]) {
  Node* my_list {};
  insert(my_list, 10);
  insert(my_list, 20);
  print_list(my_list);
}
// Printing list: 
// 20 -> 10

Answer 1

First, note that the only real difference between a struct and a class is the default accessibility: in a class everything is private by default, and in a struct everything is public by default. That's literally the only difference between the two.

In any case, some of your code can be simplified somewhat. For example, your insert can be reduced to just this:

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

It's usually better to initialize rather than construct something uninitialized, and then assign a value anyway, so this is sort of a double-win.

I'd also prefer to use a for loop to print the list, and just a new-line where you want to print a new-line:

void print_list(Node* list) {
  Node* p {list};
  std::cout << "Printing list:\n";
  if (p)
  {
    std::cout << p->data;
    for (p=p->next; p != nullptr; p=p->next)
      std::cout << " -> " << p->data;
  }
  std::cout << "\n";
}

In this case, I'd restructure the code a bit to treat the list being non-null as a pre-condition to print_list and enforce that up-front:

void print_list(Node* list) {
  if (list == nullptr)
      return;
  std::cout << "Printing list:\n";
  std::cout << list->data;
  for (Node *p{list->next}; p != nullptr; p=p->next)
    std::cout << " -> " << p->data;
  std::cout << "\n";
}

The next steps I can see would involve the sort of re-vamping you don't seem to want right now--turning the linked list into a full-blown class of its own that supports iterators and such. This does have a tremendous advantage though: right now, your linked list only supports inserting items, then printing an entire linked list. If anybody wants to do anything else, they need to implement it entirely on their own, and know all about the internal details of the linked list to do it.

Along with that, you'd probably want to make it a generic container, so you can use it to store any data type, not just int.

This way, you can immediately support essentially all code that knows how to work with a collection that supports (in this case) forward iterators. You'd probably just eliminate print_list entirely, as it becomes just an application of std::copy from a list to (for example) an infix_iterator.

This is (IMO) much cleaner in general. In particular, it separates concerns much more cleanly: the linked list can concentrate solely on linked-list "things", and not worry about things like I/O as it does now.

Answer 2

Design

I would note you have not made a linked list, but a chain of Node(s). This may seem to be the same thing but I would see this as different as a linked list would encapsulate and hide its internal structure with a class and provide methods to access the data.

So you have:

void insert(Node*& head, int data);
void print_list(Node* list)

I would have done this:

class LinkedList
{
    public:
        insert(int data);
        print();
};


// Usage in main would then be:
int main()
{
  LinkedList my_list;
  my_list.insert(10);
  my_list.insert(20);
  my_list.print();
}

Notice there are no pointers anywhere to be seen for the user. So the user of the class does not need to worry about memory management at all when using the list. Your design on the other hand leaks the list at the end.

Questions:

Should I replace the raw new with a braced initializer?

I would advise it. It avoids a few corner cases where things can go wrong.

Should I replace the Node* with a shared_ptr?

No. Two reasons. One: std::unique_ptr should be your first smart pointer you consider. Two: this is a container.

There are two types of memory management structures.

1. Smart Pointers
2. Containers.

Both have to deal with pointers internally (just not expose them to the client). But implementing a container with a smart pointer is potentially inefficient (it can be done). It is usual to do the memory management internally.

Code Review.

Don't expose implementation details

This should be a private member of your linked list.

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

Allowing users to see the structure allows them to build code around this structure which locks you into maintaining this interface. So you can now no longer improve your linked list.

Also exposing a RAW pointer leads to memory management issues. Is this an owning RAW pointer or not? i.e. who is responsible for calling delete?

Sure you can write it like this:

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

But that seems overly verbose.

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

Your print only prints to std::cout:

void print_list(Node* list) {
  Node* p {list};
  std::cout << "Printing list: " << std::endl;
  if (p) {
    std::cout << p->data;
    p = p->next;
    while(p) {
      std::cout << " -> " << p->data;
      p = p->next;
    }
    std::cout << std::endl;
  }
}

It would be nice if it printed to any stream. Then you can print it to a string or a file. Even if the default is std::cout.

void print_list(Node* list, std::ostream& str = std::cout)

Also, the standard way to print things in C++ is to use operator<<. So it would be nice if you wrote the appropriate operator.

std::ostream& operator<<(std::ostream& s, Node* node)
{
    print_list(node, s);
    return s;
}

Const correctness

A big push in C++ is const correctness. This is marking parameters and members as const if they are not mutated/mutating. In the above code the print is not supposed to mutate the list. So it might be nice to mark the nodes as const.