7
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Actually struct and class are both the same things, except that accessibility in structs is public by default, whereas in classes it is private. \$\endgroup\$ – Incomputable May 22 '16 at 16:40
  • \$\begingroup\$ Why do you use a procedural style to implement an abstract data structure in an object-oriented programming language? Your code is pretty much C with C++ style I/O and new instead of malloc both of which aren't (tightly) coupled to the management of the data structure. \$\endgroup\$ – David Foerster May 23 '16 at 20:12
  • \$\begingroup\$ @DavidFoerster I'm just working on a coding exercise. It's not meant to be used in production \$\endgroup\$ – nachocab May 23 '16 at 20:27
5
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Excellent! Thanks a lot. A couple follow-ups: 1) Should I use std::make_unique instead of new? 2) Could I do if (!list) instead of if (list == nullptr)? \$\endgroup\$ – nachocab May 22 '16 at 16:58
  • 1
    \$\begingroup\$ @nachocab: IMO, no. At one time I advocated using a smart pointer for a linked list (or tree), but then I tried to actually implement it, and it mostly turned out to be a disaster. A unique_ptr represents ownership, and a node in a linked list doesn't really own its successor, so a unique_ptr doesn't really make sense. Essentially the only time a linked list makes sense is if you need insertion deletion in the middle of the list, and those don't really fit well with most smart pointers. \$\endgroup\$ – Jerry Coffin May 22 '16 at 17:03
  • \$\begingroup\$ @nachocab: As an aside, you might want to wait a while before accepting this answer. An accepted answer can tend to discourage others from posting their observations, even though they might be more insightful and useful than mine. \$\endgroup\$ – Jerry Coffin May 22 '16 at 17:05
  • \$\begingroup\$ Yes, as far as the compiler cares,!ptr is equivalent to ptr == nullptr, but many people find it less readable. \$\endgroup\$ – Jerry Coffin May 22 '16 at 17:05
  • \$\begingroup\$ Got it. Would make_shared make more sense in this case? \$\endgroup\$ – nachocab May 22 '16 at 19:06
4
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.