2
\$\begingroup\$

I wonder if the code below is a good (quality and correctness) implementation of a single linked list in C++, in regard of data structure (not the exposed interface).

class List
{
  class Node
  {
    friend class List;
    int value;
    Node *next;
  };
  Node *head, *last;

  public:
  int size;
  List()
  {
    head = new Node;
    head->next = 0;
    last = head;
    size = 0;
  }
  ~List()
  {
    Node *it = head, *next;
    while (it)
    {
      next = it->next;
      delete it;
      it = next;
    }
  }
};
\$\endgroup\$
1
  • \$\begingroup\$ I added the beginner tag based on your description. If you are aware that C++ provides a linked-list type for you, you should also add the reinventing-the-wheel tag. \$\endgroup\$
    – Brythan
    Nov 21, 2014 at 11:55

1 Answer 1

4
\$\begingroup\$

There are a few issues with this code (problem of style):

  • Node is a class with all members public to List. Instead of putting everything private, and List as a friend, you should do this:

    class List
    {
      struct Node // struct has everything public
      {
        int value;
        Node *next;
      };
      Node *head, *last;
    

    This is less code, and everything in Node is invisible outside of List anyway, because List::Node is private.

  • You should use initializer lists for data members, and add a constructor for Node:

    struct Node // has everything public
    {
      int value;
      Node *next;
    
      Node(int x) : value{ x }, next{ nullptr } {} // <---- here
    };
    

    This will allow you to write client code like this:

    List()
    : head{ new Node(0) }, last{ head }, size{ 0 }
    {
    }
    
  • I know you said the interface of the classes is not the issue, but this is a big problem:

    class List
    {
    // ...
      public:    // <---
      int size;  // <---
    

    The only way this code is acceptable, is if this client code is valid:

    List mylist;
    mylist.size = -5; // is this valid? what should it do?
    

    If client code is not allowed to alter this value freely, it should not be a public, non-const member of the class.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks for the answer, the public size parameter could be indeed a problem. And I'll also have a read about extended initializer lists. \$\endgroup\$
    – kaspersky
    Nov 22, 2014 at 22:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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