Pointing to the first object in a linked list, inside or outside class?

Question

Which of these is a more correct way to store the first object in a linked list? Or could someone please point out the advantages/disadvantages of each. Thanks.

class Node
{
    int var;
    Node *next;

    static Node *first;

    Node()
    {
        if (first == NULL)
        {
            first = this;
            next = NULL;
        }
        else
            //next code here
        }
    }
}

Node* Node::first = NULL;
new Node();

-- OR --

class Node
{
    int var;
    Node *next;

    Node()
    {
        //next code here
    }
}

Node* first = new Node();

Answer 1

The latter is definitely preferable. By making the first node pointer a static class member, you are basically saying that there will only be a single linked list in your whole program.

The second example lets you create several lists.

Answer 2

Presumably you may have more than one list? In which case, the static option is a non-starter.

Answer 3

The first example has the definite drawback of only being able to create a single linked list in your entire program, so I wouldn't do that.

The second works fine, but doesn't shield the user of the class from how the linked list works. It would be better to add a second class, for example named LinkedList, that stores the 'first' pointer and performs list management.

Even better, you could use std::list instead.

Answer 4

It's most usual to have a separate List class and a separate Node class. Node is usually very simple. List holds a pointer to the first Node and implements the various list operations (add, remove, find and so on).

Something like the following

class List
{
public:
  List() 
  {
    first = new Node();
  }

  void insert(int val);
  void remove(int val);
  // ... and so on

  ~List() 
  {
     // ... clean up
  }

private:
  struct Node
  {
    int val;
    Node* next; 

    Node(int val_ = 0, Node* next_ = 0) 
      : val(val_), next(next_) 
    {}
  };

  Node* first;
};

Note that you can place Node outside List if you want to, but this usually doesn't make much sense.

Answer 5

You definitely don't want the "first" to be a static. This implies there's only one linked list in your entire program. static means that every Node in every linked list in your entire program has the same beginning.

That being said you want your Node to have the fewest responsibilities-- It make sense for it to store its value and be able to get to the next Node. It adds complexity to add the job of1 maintaining the "first" pointer. For example what happens when you insert a new element at the beginning? Then you'd have to update everyone's "first" pointer. Given the two choices above I'd chose the second choice.

I would furthermore add a third choice. Add a "linked list" wrapper that gave you easy access to "first", "last" and allow you to easily insert into and iterate through the list. Something like:

 class LinkedList
 {
     Node* First;
     Node* Last;

 public:
     Node* GetFirst() {return First;}
     Node* GetLast() {return Last;}

     // insert after "where"
     void Insert(Node* where, Node* newNode); 
     ...
 }

Answer 6

Not uselessly limiting your code to a single list instance is one very good argument for code variant 2.

However, just from superficially looking at the two examples, the sheer number of lines of code also gives a good indication that variant 2 has merits over variant 1 by being significantly shorter.