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;
    }
  }
};
share|improve this question
    
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. – Brythan Nov 21 '14 at 11:55
up vote 4 down vote accepted

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.

share|improve this answer
    
Thanks for the answer, the public size parameter could be indeed a problem. And I'll also have a read about extended initializer lists. – gg.kaspersky Nov 22 '14 at 22:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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