Make LinkedList in C++ more clean

Question

I have been working on a linked list for some while now and started out with this.

Is my code clean? Or is there some way to make it better and more readable?

The reason for this question is for me to be a better programmer. I would love to get one step further for making more clean code.

my class:

using namespace std;

class Node
{

public:
    int nX; 
    Node *next;
    //constructor
    Node(){ head = NULL; }          //Initialising head to NULL
    void addValueLeft(int nVal);
    void addValueRight(int nVal);
    void deleteValueLeft();
    void deleteValueRight();
    void printList();
private:
    Node *head;   //a pointer to the first Node
};

my main:

int _tmain(int argc, _TCHAR* argv[])
{
    using namespace std;
    //creating a new object
    Node list;

    list.addValueLeft(5);
    list.addValueLeft(6);
    list.addVaueRight(8);
    list.deleteValueRight();
    list.printList();

    return 0;
}    

my functions:

    void Node::addValueLeft(int nVal)
    {
        Node *newNode = new Node;
        if(!head)
        {
            newNode->nX = nVal;
            newNode->next = NULL;
            head = newNode;
        }
        else
        {
            newNode->nX = nVal;
            newNode->next = head;
            head = newNode;
        }
    }

    void Node::printList()
    {
        if(!head)       //list is empty - nothing to print
        {
            //cout << "nothing to print - list empty " << endl;
        }
        else
        {
            Node *tempNode = new Node;
            tempNode = head;
            while(tempNode)
            {
                cout << tempNode-> nX << endl;
                tempNode = tempNode->next;
            }
        }
    }

    void Node::addValueRight(int nVal)
    {
        Node *tempNode1 = new Node;

        if(!head)                   //List is empty
        {
            tempNode1 -> nX   = nVal;
            tempNode1 -> next = head;
            head = tempNode1;
        }
        else
        {
            tempNode1 = head;
            while(tempNode1 -> next != NULL)        //Go to last Node
            {
                tempNode1 = tempNode1->next;

            }
            Node *tempNode2 = new Node;         //create temp node
            tempNode2 -> nX = nVal;
            tempNode2 -> next = NULL;
            tempNode1 -> next = tempNode2;   //tempNode1 will be last Node    
    }
    }


    void Node::deleteValueLeft()
    {
        if(!head)       //list is empty - Nothing to Delete
        {
            //cout << " deleteValueLeft:  Nothing to delete" << endl;
        }
        else
        {
            head = head->next;
        }
    }

    void Node::deleteValueRight()
    {
        if(head == NULL)    //Nothing to delete
        {
            //cout << "Nothing to delete " << endl;
        }
        else
        {
            Node *tempNode1 = new Node;
            Node *oldNode = new Node;
            tempNode1 = head;
            if(tempNode1->next == NULL) //only one element
            {
                head = NULL;
            }
            else
            {
                while(tempNode1->next!=NULL)        //Go to last Node
                {
                    oldNode = tempNode1;
                    tempNode1 = tempNode1->next;

                }
                oldNode->next = NULL;
            }
        }

    }

Answer 1

Here's some feedback (not an exhaustive list).

using namespace std;

Please stop doing this. when you add using namespace directives in header files, any file including that header will have potential namespace clashes (which is the problem namespaces are trying to prevent).

class Node
{
public:
    int nX; // (1)
    Node *next; // (2)
    Node(){ head = NULL; }  // (3)

Notes:

The only ways lines (1) and (2) are acceptable, are:

• if instances of your class are valid regardless what you place in nX and next.

Client code example:

Node n;
n.nX = 1001; // is this valid?
n.next = n; // is this valid?

• if Node class is moved from the global namespace to the private section of another class. That way, the outer class will protect the node's data.

Otherwise, nX and next should be private data, with getters to read the values and setters to validate and set the values.

Line (3) is a bad implementation for a constructor, because it leaves a new instance in a partially-initialized state (it should initialize nX, next and head, explicitly and in this specific order).

Better implementation:

explicit Node(int value = 0): nX(value), next(nullptr), head(nullptr) {}

Note regarding class API design:

You are implementing both a node (for an element of the list) and a list of nodes. You should have two classes instead of one, and the head pointer should be a member of the list, not a node:

class Node {
    int nX; Node* next;
public:
    // ... rest of node interface here
};

class List {
    Node *head;
public:
    List() {}
    const std::size_t size() const;
    void add_value_end(int value);
    // ... rest of interface here
};

Eventually, you should consider using node as an internal structure of the list:

class List {
    class Node { /* same as above */ };
    Node *head;
public:
    // same as above
};

Answer 2

I agree with @utnapistim answer, that you should have two classes: a List class with a head element, and a Node class with a next element.

As well:

• The if in your addValueLeft is unecessary: you do the same thing (i.e. you assign the same value to nX, next, and head) no matter what the if value is.
• In addValueRight you should not have two new Node; statements: you are leaking the first new node.
• You should have a List destructor which deletes all the nodes on the list

• Your deleteValue methods should delete the node before forgetting about it; for example:

  void Node::deleteValueLeft()
  {
      if(!head)
          return; //list is empty - Nothing to Delete
      Node* firstNode = head;
      head = head->next;
      // you weren't doing the following;
      // note that I get/dereference head->next before I delete this old head
      delete firstNode; 
  }
  

• Perhaps your Node should have a non-default constructor; because a Node is only created when there's a value to store in it:

Answer 3

Well, there are many problems in the code. Does this compile and run correctly? Some things I have noticed:

• Make the member variables in Node private as they are not needed outside. And if they were, you should probably provide getter and setter methods.

• The member variable Node::head should be static because the head is ALWAYS the same. The way you are doing it now each instance of Node (so each Node) has its own head. This is not only waste of memory but also wrong. With static there is only one instance of Node *head in the memory. (Of course in that case you must not set head to NULL). Notice that this solution has the disadvantage that you can only have one list at a time. But to solve this there are only two possibilities:

  1. Leave it non static. But then you have to adjust the member variable in each node once the head changes (very costly). Moreover (as mentioned above) you waste memory.
  2. As suggested by the other answers: make two classes. A class for the List and a (nested) class for the node. The head pointer is then a member of the List (not the Node anymore). This way you can instantiate many Lists with different heads.

The latter is obviously the better solution an is the common way to solve that problem.

So Node should/could be changed to be like that:(here head is static)

class Node
{
public:
     Node();              //Do NOT initialize to NULL
private:
    int nX; 
    Node *next;
    static Node *head = NULL;// initialize to NULL
};

Another thing that is seen as better practice is to use initialization lists (read about it). In short: An initialization list initializes (as the name suggests) variables on construction.

And many other things. Including but not limited to the following:

  void Node::addValueLeft(int nVal)
{
    Node *newNode = new Node;

    newNode->nX = nVal;
    newNode->next = head;  // set to old head. If head is NULL, it is OK, too.
    if(!head)              // if list is empty, make head pointing at the new node
        head = newNode;
}

void Node::printList()
{
    // if is unnecessary here. If list is empty the while loop
    // is skipped anyway.

    Node *tempNode = head; // no new Node here
    while(tempNode)
    {
        cout << tempNode-> nX << endl;
        tempNode = tempNode->next;
    }
}

void Node::addValueRight(int nVal)
{
    Node *tempNode1; // no good naming and no need for new Node

    Node *tempNode2 = new Node; //create temp node
    tempNode2 -> nX = nVal;
    tempNode2 -> next = NULL;

    if(head == NULL){           // if list is empty, the new Node is the first Node
        head = tempNode2;
    }else{                      // if there are Nodes in the list ...
        tempNode1 = head;
        while(tempNode1 -> next != NULL)  // ... Go to last Node
        {
            tempNode1 = tempNode1->next;
        }
        tempNode1 -> next = tempNode2;    //tempNode2 will be last Node
    }
}

I would really like to help more but I think you have to read more about the basics. Most important: read much much much about pointers. Moreover read about new and delete. If you have more (specific) questions feel free to ask.

Answer 4

Aside from the problems with the code itself as pointed out in the other answers, I would like to comment on your interface naming. There are a few common names for linked list operations that any experienced programmer will expect:

• push / pop for stacks (first in, last out): Add an element to the end of the list, or remove the last added element from the end of the list
• queue/ dequeue for queues (first in, first out lists): Add an element to the start of the list and remove one from the end of the list.
• shift / unshift - I am not sure how common these terms are, but for example PHP uses this as the analog to push and pop for operations on the start of the list.