C++ Pointers / Lists Implementation

Question

Write a class ListNode which has the following properties:

• int value;
• ListNode *next;

Provide the following functions:

• ListNode(int v, ListNode *l)
• int getValue();
• ListNode* getNext();
• void insert(int i);
• bool listcontains(int j);

Write a program which asks the user to enter some integers and stores them as ListNodes, and then asks for a number which it should seek in the list.

Here is my code:

#include <iostream>
using namespace std;

class ListNode
{
    private:
        struct Node
        {
            int value;
            Node *next;
        } *lnFirst;

    public:
        ListNode();
        int Length();       
        void DisplayList();     
        void Insert( int num );
        bool Contains( int num );       
        int GetValue( int num );        
};

ListNode::ListNode()
{
    lnFirst = NULL;
}

int ListNode::Length()
{
    Node *lnTemp;
    int intCount = 0;
    for( lnTemp=lnFirst ; lnTemp != NULL ; lnTemp = lnTemp->next )
    {
        intCount++;
    }
    return intCount;
}

void ListNode::DisplayList()
{
    Node *lnTemp;
    for( lnTemp = lnFirst ; lnTemp != NULL ; lnTemp = lnTemp->next )
        cout<<endl<<lnTemp->value;
}

void ListNode::Insert(int num)
{
    Node *lnCurrent, *lnNew;

    if( lnFirst == NULL )
    {
        lnFirst = new Node;
        lnFirst->value = num;
        lnFirst->next = NULL;
    }
    else
    {
        lnCurrent = lnFirst;
        while( lnCurrent->next != NULL )
            lnCurrent = lnCurrent->next;

        lnNew = new Node;
        lnNew->value = num;
        lnNew->next = NULL;
        lnCurrent->next = lnNew;
    }
}

bool ListNode::Contains(int num)
{
    bool boolDoesContain = false;
    Node *lnTemp,*lnCurrent;
    lnCurrent = lnFirst;
    lnTemp = lnCurrent;
    while( lnCurrent!=NULL )
    {
        if( lnCurrent->value == num )
        {
            boolDoesContain = true;
            return boolDoesContain;
        }
        lnTemp = lnCurrent;
        lnCurrent = lnCurrent->next;
    }
    return boolDoesContain;
}

int ListNode::GetValue(int num)
{
    Node *lnTemp;
    int intCount = 1;
    for( lnTemp=lnFirst; lnTemp != NULL; lnTemp = lnTemp->next )
    {
        if (intCount == num)
        {
            return lnTemp->value;
        }
        intCount++;
    }    
}

int main()
{   
    cout << "Input integers below. Input the integer -1 to stop inputting.\n\n";
    
    ListNode lnList;
    int intNode = 1, intInput = 0;
    while (intInput != -1) {
        cout << "Please input integer number " << intNode << ": "; cin >> intInput;
        intNode++;
        if (intInput != -1) { lnList.Insert(intInput); }
    }   
    
    lnList.DisplayList();
    cout << "\n\n";
    
    int intListLength = lnList.Length();    
    cout << "Which value do you wish to recall? (Between 1 and " << intListLength << "): "; cin >> intNode;    
    if ( intNode >= 1 && intNode <= intListLength ) {
        cout << "Value at position " << intNode << " is " << lnList.GetValue(intNode) << ".";                
    } else {
        cout << "No such position in the list. Positions run from 1 to " << intListLength << ". You asked for " << intNode << ".";
    }
    
    cout << "\n\nCheck if the following value is in the list: "; cin >> intNode;
    bool IsThere = lnList.Contains(intNode);
    if (IsThere) {
        cout << intNode << " is in the list.";
    } else {
        cout << intNode << " is not in the list.";
    }
    
    cout << "\n\n";
    system("pause");
    return 0;  
}

Where can we improve this?

Answer 1

More detailed feedback at the bottom of this post, but to begin with, just some inline comments and changes in the code:

struct Node // Why doesn't this have a constructor initializing the members?
{
        int value;
        Node *next;
} *lnFirst; 


ListNode::ListNode() : lnFirst(NULL) {} // Use initializer lists instead of initializing members in the ctor body. It's cleaner, more efficient and may avoid some nasty bugs (because otherwise the member gets default-initialized *first*, and then assigned to in the body)

int ListNode::Length()
{
    int intCount = 0;
    for( Node* lnTemp=lnFirst ; lnTemp != NULL ; lnTemp = lnTemp->next ) // Create the loop iteration variable lnTemp here, in the loop, not at the start of the function
    {
        intCount++;
    }
    return intCount;
}

void ListNode::DisplayList()
{
    for(Node* lnTemp = lnFirst ; lnTemp != NULL ; lnTemp = lnTemp->next ) // And again, initialize the loop variable in the loop
        cout<<endl<<lnTemp->value; // Not a huge deal, but endl flushes the stream as well as inserting a newline. That can be needlessly slow. So you might want to just use "\n" in cases where you don't need the flushing behavior.
}

void ListNode::Insert(int num)
{
//    Node *lnCurrent, *lnNew; // Very subjective, but I prefer not declaring multiple variables on the same line, because the syntax if they're pointers can be surprising (You got it right, but a lot of people would write Node* lnCurrent, lnView, which would make lnView not a pointer. I find it clearer to just give ecah variable a separate line:
    if( lnFirst == NULL )
    {
//        lnFirst = new Node;
//        lnFirst->value = num;
//        lnFirst->next = NULL;
        lnFirst = new Node(num); // Make a constructor which initializes next to NULL, and sets value = num. Just like you would in other languages. ;)
    }
    else
    {
        Node* lnCurrent = lnFirst; // Don't declare variables until you need them. Both to improve readability, and because C++ distinguishes between initialization and assignment, so in some cases, default-initialization followed by assigment may not be the same as just initializing with the desired value.
        while( lnCurrent->next != NULL )
                lnCurrent = lnCurrent->next;

        Node* lnNew = new Node(num); // Again, let a constructor do the work.
        lnCurrent->next = lnNew;
    }
}

bool ListNode::Contains(int num)
{
    bool boolDoesContain = false;
//    Node *lnTemp,*lnCurrent; // Again, don't initialize variables at the start of the function if they're not needed
    Node* lnCurrent = lnFirst;
//    lnTemp = lnCurrent;
    while( lnCurrent!=NULL )
    {
        if( lnCurrent->value == num )
        {
//                boolDoesContain = true;
//                return boolDoesContain;
                  return true; // Just return directly, and remove the boolDoesContain variable. Alternatively, set boolDoesContain to true, and then break out of the loop without returning, so you have a single exit point from the function. Both approaches have their merits, but setting a variable you don't need, and then returning is silly. ;)
        }
//        Node* lnTemp = lnCurrent; // you don't actually use lnTemp for anything, it seems
        lnCurrent = lnCurrent->next;
    }
//    return boolDoesContain;
      return false; // just return false. If you get this far, it must be because you haven't found a match, so boolDoesContain can only be false anyway.
}

int ListNode::GetValue(int num)
{
//    Node *lnTemp;
    int intCount = 1; // Wouldn't most people expect this indexing to be zero-based?
    for( Node* lnTemp=lnFirst; lnTemp != NULL; lnTemp = lnTemp->next )
    {
        if (intCount == num)
        {
            return lnTemp->value;
        }
        intCount++;
    }    
}

Now, a couple of general comments. (I'm going to ignore whether or not you misunderstood the assignment, and focus on the code you posted) First, hungarian notation: Don't. Call your node pointers first, temp and whatever else, without the 'ln' prefix. Call your bool variable doesContain without a needless 'bool' prefix. Second, as I've tried to do in the edited code, only create variables when you need them. C used to require variables to be declared at the top of a block, but C++ never did. Third, you don't need the 'return 0' at the end of the main function. Main is a special case where, if it reaches the end of the function, it automatically returns 0.

Fourth, we have the big nasty issue: Memory management. You allocate memory which is never freed. Since you don't have a RemoveNode function, this might seem like a moot point, but what happens when the entire list itself goes out of scope, and gets deleted? None of its nodes are deleted, because all the list has is a bunch of pointers, and it doesn't automatically call delete on those. So at the very least, you need a destructor on the list class itself, so that when the list is deleted, it makes sure to delete all its child nodes.

That should handle the simple default case where you create a list, add nodes to it, and delete the list.

Next big problem, what if I copy the list?

int main(){
ListNode list;
list.Insert(1);
list.Insert(2);
list.Insert(3);
}
ListNode list2 = list;

Your code explodes. Both lists now point to the same nodes, instead of making copies of the nodes. Adding a node to one list will also make it show up in the other. And before you claim "that's a feature, not a bug" ;), consider what happens when one of the lists are deleted now.

Assume list2 gets deleted first. With the destructor we just defined, it deletes the three nodes, and returns. Now list points to nodes that have been deleted. Accessing them is undefined behavior, and quite likely to crash. So let's say we don't access them, instead we just quickly delete this list as well.

Whoops, that means we're trying to delete child nodes that have already been deleted. That definitely sounds like a crash.

So to fix this, your ListNode class has to implement two additional functions, the copy constructor and the assigment operator:

ListNode(const ListNode& other);
ListNode& operator==(const ListNode& other);

These two must ensure that when all data is copied from 'other'. For every node in 'other', you must allocate a new node in the current list rather than just making both lists point to the same node. (Which means the node class most likely also needs a copy constructor at the very least).

That's the basic way to handle memory management, and it is important to understand because otherwise you will screw up. ;)

Answer 2

Another improvement, in the list code, you shouldn't traverse the whole list to get the length, you can keep a counter about the amount of elements updating it on insertions/deletions and return it.

Answer 3

On a more general style note, declare pointers closer to where you'll define them, and keep their scope as small as possible.
While nothing can technically go wrong with your code, always doing this avoids bugs in much larger/ older codebases in my experience.

e.g. instead of

Node *lnTemp;
int intCount = 0;
for( lnTemp=lnFirst ; lnTemp != NULL ; lnTemp = lnTemp->next )
{
}

write

int intCount = 0;
for(Node* lnTemp=lnFirst ; lnTemp != NULL ; lnTemp = lnTemp->next )
{
}

or, similar, instead of

Node *lnTemp,*lnCurrent;
lnCurrent = lnFirst;
lnTemp = lnCurrent;

write

Node* lnCurrent = lnFirst;
Node* lnTemp = lnCurrent;

Answer 4

What unwind and ckarmann say. Here is a hint, i implement listcontains for you to give you the idea how the assignment could be meant:

class ListNode {
private:
    int value;
    ListNode * next;

public:
    bool listcontains(int v) { 
        // does this node contain the value?
        if(value == v) return true; 

        // was this the last node?
        if(next == 0) return false;

        // return whether nodes after us contain the value 
        return next->listcontains(v);
    }
};

So, you only have the head of the list, which links to the next node in turn. The tail will have next == 0;

Answer 5

Part of the assignment read:

Provide the following functions:

• ListNode(int v, ListNode *l)
• int getValue();
• ListNode* getNext();
• void insert(int i);
• bool listcontains(int j);

You did not provide any of those functions.

As several others have pointer out, you implemented a List instead of a ListNode, which is why the signatures of your functions are different.

But you should also not thoughtlessly violate the coding-conventions of the assignment. Do you have a C#-background? In C++ coding conventions will usually mandate lower-case method-names.

Answer 6

I think you misunderstood the requested design. The ListNode class is supposed to be a node, not a list containing nodes.

I would advise you not to put several commands on a single ligne, like this:

cout << "Please input integer number " << intNode << ": "; cin >> intInput;

This is simply confusing.

Answer 7

I think you're over-engineering the list node modelling. The class ListNode IS A list node, that is evident from its name. It should then not need a nested structure to keep list inormation, that is very confusing.