Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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;
            }
        }

    }
share|improve this question
    
If you use a Sentinal it makes the creation of a linked list a lot easier to write and the code a lot cleaner. codereview.stackexchange.com/a/9399/507 –  Loki Astari Mar 6 at 16:57

4 Answers 4

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
};
share|improve this answer
    
Implementing a linked list without a dummy head node should be very, very high on the list of "do nots" in my opinion. Just means the code needs tons of special cases for no good reason. –  Voo Mar 6 at 15:38
    
@Voo, can you please be more specific? My proposed implementation doesn't require (or impose) a dummy head, nor special cases in processing (as far as I can tell). Maybe I am missing something? –  utnapistim Mar 6 at 15:50
1  
I just tried writing an append method for the list and saw what you mean: an implementation with a dummy head, will ensure that in the situations where you implement iteration (Node *p = head; while(p->next) ...) you don't need to check the validity of the iterator before accessing 'next'. –  utnapistim Mar 6 at 15:59
1  
If you're going to do Node(int value=0)... you really must make it an explicit constructor - explicit Node(int value=0) - or you will create an implicit casting between your list node and its payload and you do not want that. In fact, in general, you should get in the habit of always putting explicit in front of single parameter constructors unless you really, really want casting. –  Jack Aidley Mar 6 at 17:11
1  
Thanks @JackAidley, I updated the post. –  utnapistim Mar 6 at 17:53

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:

share|improve this answer

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.

share|improve this answer
1  
+1; but head cannot be static if there is more than one List in the program. –  ChrisW Mar 6 at 14:27
2  
A static head member in the Node class is so wrong that you should edit it out of your answer entirely. –  Peter Mar 6 at 15:05
    
@Peter on the one hand you are right. But on the other hand it is much better than the solution from the OP. But I will think about it and edit my answer to something more secure. –  exilit Mar 6 at 15:28
    
@exilit The OPs code may not be great but at least correct (ok, there's at least a chance it may be correct at least). Making the head node static on the other hand is a bug in any way you think about it. –  Voo Mar 6 at 15:41
1  
Putting a pointer to the head in a node is just plain bad design (since it prevents many of the operations that make lists worthwhile speedily). Doing it statically is even worse (since it limits you to one list in your whole program!). –  Jack Aidley Mar 6 at 17:13

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.
share|improve this answer

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.