Please review my exercise about linked lists

Question

I'm learning C++ by myself and therefore I have no direct access to a mentor. This is the reason why I'd love if you guys could take the time to do a peer code review.

I am very much aware, as per the FAQ, that very few people would be willing to go through all my code, but every little bit helps.

The exercise is the bunny linked list exercise; the last beginner exercise from: http://www.cplusplus.com/forum/articles/12974/

I'm looking for feedback on absolutely everything that could make me a better programmer:

• Syntax
• Optimization
• Form
• Functions or variables naming
• Bugs
• Performance
• Code structure

Keep in mind that I haven't completed all aspects of the exercise related to it running in real-time or outputting events to a file.

Thanks for your time! Know that it's very much appreciated.

main.cpp

#include <ctime>
#include <cstdlib>
#include <iostream>
#include <string>

#include "BunnyNode.h"
#include "BunnyList.h"

//BUGS
//Generate at least one female and one male on start

//TO DO
//Replace names with vectors(?) generated from separate .txt file
//Output all turn events, birth, turn mutant, dies
//Output all turns to file

using std::cin;
using std::cout;
using std::endl;

int main()
{
    srand(time(0));

    // Create rabbit LinkedList
    RabbitList * colony = new RabbitList;

    bool terminate = false;
    int turns = 0;

    //Add 5 rabbits to list for the first round
    colony->startCheck(turns);

    while(!terminate)
    {
        colony->printList();
        cout << endl;

        //Increment all rabbits age
        colony->incrementRabbitAge();

        //Add babies
        colony->addBabies();

        //Each mutant will convert one other bunny each turn
        colony->mutantConversion();

        //Check if colony is 0 or 1000
        colony->sizeCheck(terminate);

        cout << "\nThe current mutant count is: " << colony->mutantCount() << endl;
        colony->printSize();

        ++turns;

        if(colony->getColonySize() != 0)
        {
            cout << "\nNext turn? Press any key to continue. (Press k to purge the colony.)" << endl;
            char choice;
            cin >> choice;

            if(choice == 'k')
                colony->purge();
        }
    }

    cout << "\nTOTAL TURNS: " << turns << endl;

    delete colony;

    return 0;
}

BunnyList.cpp

#include <cstdlib>
#include <iostream>
#include <string>

#include "BunnyList.h"
#include "globals.h"

using std::string;
using std::cout;
using std::endl;

RabbitList::RabbitList(): head(NULL),size(0)
{}

RabbitList::~RabbitList()
{}

int RabbitList::randomGeneration(int x)
{
    return rand() % x;
}

void RabbitList::generateRandomFeatures(RabbitNode * newRabbit)
{
    newRabbit->sex = randomGeneration(2);                               //Generate gender first to determine first name
    newRabbit->colour = colourList[randomGeneration(MAX_COLOURS)];      //Generate colour

    int i = randomGeneration(10);

    if(newRabbit->sex)                                                  //Generate name
        newRabbit->firstName = maleFirstName[i];
    else
        newRabbit->firstName = femaleFirstName[i];

    i = randomGeneration(10);
    newRabbit->lastName = lastNames[i];

    i = randomGeneration(100);                                           //Generate mutant

    if(i < BORN_MUTANT_PERCENT_CHANCE)
        newRabbit->radioactive_mutant_vampire_bunny = true;
}

//Turn checks
void RabbitList::startCheck(int turns)
{
    if(turns == 0) // Generate first 5 rabbits
    {
        for(int index = 0; index < 5; ++index)
        {
            addRabbit();
        }
    }
}

void RabbitList::sizeCheck(bool& terminate)
{
    if(getColonySize() == 0)
        terminate = true;
    else if(getColonySize() >= MAX_COLONY_SIZE)
    {
        purge();
    }
}

bool RabbitList::fatherCheck(RabbitNode * rabbit, bool& fatherPresent)
{
    if(rabbit->sex == 1 && rabbit->age >= 2 && rabbit->radioactive_mutant_vampire_bunny == false)
        fatherPresent = true;

    return fatherPresent;
}

bool RabbitList::motherCheck(RabbitNode * rabbit)
{
    if(rabbit->sex == 0 && rabbit->age >= 2 && rabbit->radioactive_mutant_vampire_bunny == false)
        return true;
    else
        return false;
}

//Returns true if rabbit is older than 10, false otherwise
bool RabbitList::ageCheck(RabbitNode * rabbit)
{
    if(head)
    {
        if(rabbit->age >= MAX_AGE && rabbit->radioactive_mutant_vampire_bunny == false)
        {
            return 1;
        }
        else if(rabbit->age >= MAX_MUTANT_AGE && rabbit->radioactive_mutant_vampire_bunny == true)
        {
            return 1;
        }
        else
            return 0;

    }
}

//Add one year to all rabbit every turn,
//Kill the rabbit if he goes over its allowed age, 10 for regular, 50 for mutant
void RabbitList::incrementRabbitAge()
{
    //If there's more than one node
    if(head)
    {
        RabbitNode * temp = head;
        RabbitNode * trail = NULL;

        while(temp != NULL)
        {
            //The rabbit is young enough to age
            if(!ageCheck(temp))
            {
                temp->age += 1;
                trail = temp;
                temp = temp->next;
            }
            //The rabbit is too old
            else
            {
                //If we're on the first head node
                if(head == temp)
                {
                    head = temp->next;
                    cout << "Bunny " << getName(temp) << " died!" << endl;
                    delete temp;
                    temp = head;
                    --size;
                }
                //If we're beyond the head node
                else
                {
                    trail->next = temp->next;
                    cout << "Bunny " << getName(temp) << " died!" << endl;
                    delete temp;
                    temp = trail->next;
                    --size;
                }
            }
        }
    }
}

void RabbitList::addBabies()
{
    if(head)
    {
        //Checks if there is at least one male in the colony
        bool fatherPresent = false;

        RabbitNode* temp = head;
        while(temp != NULL)
        {
            fatherCheck(temp, fatherPresent);
            temp = temp->next;
        }
        //Executes if there's at least one male
        if(fatherPresent == true)
        {
            temp = head;
            RabbitNode * trail = NULL;

            while(temp != NULL)
            {
                if(motherCheck(temp) == true)
                {
                    addRabbit(temp);
                    temp = temp->next;
                }
                else
                {
                    temp = temp->next;
                }
            }
        }
    }
}

void RabbitList::addRabbit()
{
    RabbitNode* newRabbit = new RabbitNode;

    if(!head)
    {
        head = newRabbit;
        generateRandomFeatures(newRabbit);
    }
    else
    {
        RabbitNode* temp = head;
        while(temp->next != NULL)
            temp = temp->next;

        RabbitNode* newRabbit = new RabbitNode;
        generateRandomFeatures(newRabbit);
        temp->next = newRabbit;
    }

    ++size;
}

void RabbitList::addRabbit(RabbitNode * mother)
{
    RabbitNode* newRabbit = new RabbitNode;

    if(!head)
    {
        head = newRabbit;
        generateRandomFeatures(newRabbit);

        if(newRabbit->radioactive_mutant_vampire_bunny == true)
            cout << "Radioactive Mutant Vampire ";
        cout << "Bunny " << getName(newRabbit) << " was born!" << endl;
    }
    else
    {
        RabbitNode* temp = head;
        while(temp->next != NULL)
            temp = temp->next;

        RabbitNode* newRabbit = new RabbitNode;
        generateRandomFeatures(newRabbit); // We'll replace the colour right after
        newRabbit->colour = mother->colour; // Set baby colour to be the same as the mother
        temp->next = newRabbit;

        if(newRabbit->radioactive_mutant_vampire_bunny == true)
            cout << "Radioactive Mutant Vampire ";
        cout << "Bunny " << getName(newRabbit) << " was born!" << endl;
    }

    ++size;
}

int RabbitList::mutantCount()
{
    int mutantTotal = 0;

    if(head)
    {
        RabbitNode * temp = head;

        while(temp != NULL)
        {
            if(temp->radioactive_mutant_vampire_bunny)
                ++mutantTotal;
            temp = temp->next;
        }
    }

    return mutantTotal;
}

//For each mutant rabbit, it will convert another one each turn
void RabbitList::mutantConversion()
{
    //Get the number of mutants in the colony
    int amountToConvert = mutantCount();

    if(amountToConvert > 0 && head != NULL)
    {
        //Executes if there's still bunnies left to convert, or if all the bunnies aren't mutants yet
        while(amountToConvert != 0 && mutantCount() != getColonySize())
        {
            RabbitNode * temp = head;

            //Choose a bunny randomly in the colony to convert
            int bunnyToConvert = randomGeneration(getColonySize());

            //Traverse list to get to the chosen bunny
            for(; bunnyToConvert > 0; --bunnyToConvert)
            {
                temp = temp->next;
            }

            //Check if chosen bunny isn't already a mutant
            if(temp->radioactive_mutant_vampire_bunny == false)
            {
                temp->radioactive_mutant_vampire_bunny = true;
                cout << getName(temp) << " has turned into a mutant!" << endl;
                --amountToConvert;
            }
        }
    }
}

void RabbitList::purge()
{
    if(getColonySize() == 1)
    {
        delete head;
        head = NULL;
        --size;
    }

    if(head)
    {
        //Kill half the colony
        for(int amountToKill = (getColonySize()) / 2; amountToKill != 0;)
        {
            RabbitNode * curr = head;
            RabbitNode * trail = NULL;

            //Choose a bunny randomly in the colony to kill
            int bunnyToKill = randomGeneration(getColonySize());

            //Traverse list to get to the chosen bunny to kill
            for(; bunnyToKill > 0; --bunnyToKill)
            {
                trail = curr;
                curr = curr->next;
            }

            //If we're on the head node
            if(curr == head)
            {
                head = curr->next;
                delete curr;
                --size;
                --amountToKill;
            }
            //If we're beyond the head, but not on last node
            else if(curr->next != NULL)
            {
                trail->next = curr->next;
                delete curr;
                --size;
                --amountToKill;
            }
            //If we're on the last node
            else
            {
                trail->next = NULL; // crash
                delete curr;
                --size;
                --amountToKill;
            }
        }
        cout << "Food shortage! Colony has been purged by half." << endl;
    }
}

//DATA MEMBER ACCESSORS
string RabbitList::getGender(RabbitNode * rabbit)
{
    if(rabbit->sex == 1)
        return "Male";
    else
        return "Female";
}

string RabbitList::getName(RabbitNode * rabbit)
{
    return rabbit->firstName + " " + rabbit->lastName;
}

int RabbitList::getColonySize()
{
    return size;
}

void RabbitList::printList()
{
    RabbitNode* temp = head;

    if(head)
    {
        while(temp != NULL)
        {
            printFeatures(temp);
            temp = temp->next;
        }
    }
}

void RabbitList::printFeatures(RabbitNode * rabbit)
{
    if(head)
    {
        cout << "\nNAME: " << getName(rabbit) << endl
             << "AGE: " << rabbit->age << endl
             << "COLOUR: " << rabbit->colour << endl
             << "GENDER: " << getGender(rabbit) << endl;

        if(rabbit->radioactive_mutant_vampire_bunny)
            cout << "Radioactive mutant vampire bunny!" << endl;

        cout << endl;
    }
}

void RabbitList::printSize()
{
    if(head)
        cout << "The colony's size is currently : " << size << endl;
}

BunnyNode.cpp

#include "BunnyNode.h"

using std::cout;
using std::endl;

RabbitNode::RabbitNode():next(NULL), firstName("none"), lastName("none"), colour("none"), age(0), radioactive_mutant_vampire_bunny(0)
{}

RabbitNode::~RabbitNode()
{}

BunnyList.h

#ifndef GUARD_BUNNYLIST_H
#define GUARD_BUNNYLIST_H

#include <string>
#include "BunnyNode.h"

class RabbitList
{
    public:

        //Constructor
        RabbitList();
        ~RabbitList();

        //Member methods
        int randomGeneration(int x);
        void generateRandomFeatures(RabbitNode * newRabbit);

        void startCheck(int turns);
        void sizeCheck(bool& terminate);
        bool motherCheck(RabbitNode * rabbit);
        bool fatherCheck(RabbitNode * rabbit, bool& fatherPresent);
        bool ageCheck(RabbitNode * rabbit);
        void incrementRabbitAge();

        void addBabies();
        void addRabbit();
        void addRabbit(RabbitNode * mother);
        void purge();
        int mutantCount();
        void mutantConversion();

        std::string getGender(RabbitNode * rabbit);
        std::string getName(RabbitNode * rabbit);
        int getColonySize();

        void printList();
        void printFeatures(RabbitNode * rabbit);
        void printSize();

    private:
        RabbitNode* head;
        int size;
};

#endif // GUARD_BUNNYLIST_H

BunnyNode.h

#ifndef GUARD_BUNNYNODE_H
#define GUARD_BUNNYNODE_H

#include <iostream>
#include <string>

class RabbitNode
{
    friend class RabbitList;

    public:
        RabbitNode();
        ~RabbitNode();

    private:
        std::string firstName, lastName, colour;
        int age;
        bool sex;
        bool radioactive_mutant_vampire_bunny;

        RabbitNode* next;
};

#endif // GUARD_BUNNYNODE_H

globals.h

#ifndef GUARD_GLOBALS_H
#define GUARD_GLOBALS_H

static const int MAX_COLOURS = 4;
static const int MAX_AGE = 10;
static const int MAX_MUTANT_AGE = 50;
static const int MAX_COLONY_SIZE = 1000;
static const int BORN_MUTANT_PERCENT_CHANCE = 2;

//To do: replace with vectors(?) generated from separate .txt file
static std::string maleFirstName[] =
{
    "Bob",
    "Nick",
    "Roger",
    "Tim",
    "Ivan",
    "John",
    "Jack",
    "Vincent",
    "Dave",
    "Donald"
};

static std::string femaleFirstName[] =
{
    "Kate",
    "Jane",
    "Lisa",
    "Kim",
    "Allison",
    "Sophie",
    "Anna",
    "Lillian",
    "Sarah",
    "Alexandra"
};

static std::string lastNames[] =
{
    "Smith",
    "Williams",
    "Brown",
    "von Shaft",
    "Mitchell",
    "O'Connor",
    "Edwards",
    "Harris",
    "Wood",
    "Cooper"
};

static std::string colourList[MAX_COLOURS] =
{
    "White",
    "Brown",
    "Black",
    "Spotted"
};

#endif // GUARD_BUNNYNODE_H

Answer 1

Not a full review, but just some general comments on style and other C++ idioms. Note that I only looked at some of the code and wasn't looking at correctness.

Style

• You should name your files with the same name as the class (eg. class RabbitNode would be in RabbitNode.h and RabbitNode.cpp)
• Always use braces {} on if/else and while blocks. Yes, you don't have to use them if it's a one-liner, but it avoids bugs in the future when you add more lines to the same if block and forget to add the braces

• Put items in the constructor's initialization list on separate lines. This makes for easier reading when there are many member variables, and it makes diffs cleaner when you make changes

  RabbitNode::RabbitNode()
      : next(NULL)
      , firstName("none")
      , lastName("none")
      , colour("none")
      , age(0)
      , radioactive_mutant_vampire_bunny(0)
  {}
  

• Distinguish local variables from member variables in some way. Often people use a leading _ or m_. This makes it easier to read code and know if you're touching locals or members, and it also makes using auto-complete features of your IDE easier. If you're coding and want to see all the members of your class to auto-complete, just start with m_ for example to get the list.

  eg. In BunnyList.h

  private:
      RabbitNode* m_head;
      int m_size;
  

• Avoid globals. There are cases where they should be used, but generally should be avoided. Especially if you're just starting out, you should actively develop the habit to avoid them. In some cases, some of the constants you've defined in your Globals.h file are only used in one file, so just move the constants there. In most other cases, you can avoid globals by passing them in as parameters to functions or class constructors.

Includes / Forward declaration

The general rule is, only use an #include for what you need in that single file, and use forward declaration wherever possible instead of #include.

A few examples:

• In BunnyNode.h, you aren't using anything from <iostream> here, so don't include it
• In BunnyList.h, you don't actually need the definition of RabbitNode since you only have a pointer member and pointer parameters. This means you can forward declare RabbitNode and leave out the #include. After making the above change, in BunnyList.cpp, you need the definition of RabbitNode, so the forward declaration you bring in from BunnyList.h won't be sufficient - you should now #include BunnyNode.h here. Check out this StackOverflow question for info on how/when to use forward declarations.
• I believe you're not using anything from <cstdlib> in BunnyList.cpp, so remove that #include

Const

You are not using const keyword anywhere. Using const can not only prevent bugs, but also it makes the programmers intentions clear about how variables and functions are going to be used.

In general, if a class member function will not change the state its member variables, it should be declared const. Note that this needs to be put in both the header and implementation file.

eg. in BunnyList.h

void printSize() const;

eg. in BunnyList.cpp

void RabbitList::printSize() const
{
    if(head)
        cout << "The colony's size is currently : " << size << endl;
}

In general, variables (including member variables) should be declared const if they will never change value. This goes for parameters too.

eg. in BunnyList.h

// rabbit will not be altered in this function, so make it const
// while we're at it, make the function const since this function will not alter any member variables
bool ageCheck(const RabbitNode * rabbit) const;

Answer 2

A few more bits of advice:

Usage of New

In main.cpp you new an instance of RabbitList, only to delete it at the end of the function. If a variable doesn't need to outlive the scope of the function it is defined in, there is no reason to new it. Instead, you should stack-allocate it, that is:

RabbitList colony;

This guarantees it will be cleaned up in case of an unhandled exception being thrown.

Memory Leaks

Your RabbitList destructor is empty, however, in your addRabbit methods, you do:

 RabbitNode* newRabbit = new RabbitNode;

This memory is never freed through delete, hence you have what is called a memory leak - memory that has been allocated that can never be deallocated. To fix this, you'll need to make sure that you walk through each node in your destructor, freeing as you go:

RabbitList::~RabbitList()
{
    RabbitNode* tmp = NULL;
    while(head != NULL) {
        tmp = head->next; //Make sure we hold a pointer to the next node
        delete head;
        head = tmp;
    }
}

The other option is to use a unique_ptr, however, this may be too confusing for the moment, and is only available through boost or as part of C++11.

Lack of Copy Constructor/Assignment Operator

Suppose you wanted to copy an already-initialized RabbitList, either by:

RabbitList colony;
//Some actions on colony
RabbitList next_colony(colony); //copy construction
RabbitList another_colony = colony; //copy assignment

These two functions correspond to:

RabbitList::RabbitList(const RabbitList& rhs); //Copy constructor
RabbitList& RabbitList::operator=(const RabbitList& rhs); //Copy assignment

There are two ways to fix this: either declare them both private, which will throw up a compiler error if anyone tries to perform either of these copies, or implement them. These functions can actually be a little bit tricky to implement, but I'd suggest reading this StackOverflow post about what is called the "Rule of Three" if you do decide to.

Answer 3

Like MahlerFive, I haven't checked your code for correctness. Here are some general comments.

• Consider using coding standards. Check your code against them. This will make your coding style consistent. Our dept, for example, has taken Google's coding standards (found here: http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml) and modified them. Everyone in our dept. follows those conventions. The entire codebase has now started to look similar. Makes it much easier to read code.

This will help you avoid inconsistencies like RabbitNode* next and RabbitNode * next (notice the position of * in the two cases).

• Avoid using friend declarations. Use them only if you must. http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml#Friends

• Consider using nullptr instead of NULL.

  stackoverflow.com/questions/1282295/what-exactly-is-nullptr (prefix http : //, the stackexchange software doesn't allow me to add more than 2 links in my reply). This suggestion is not valid if you're using an older compiler that doesn't support nullptr but since you're learning C++ you should know the newer facilities in it. nullptr is something that has been introduced in the latest standard of C++.

• Consider using a namespace. google-styleguide.googlecode.com/svn/trunk/cppguide.xml#Namespaces

• Functions that return a bool should be named starting with a verb, for example, motherCheck() should probably be hasMother(). In your code, there are two functions:

  void sizeCheck(bool& terminate); bool motherCheck(RabbitNode * rabbit);

  One returns a void and another a bool but they're both named similarly.

• Consider using a smart pointer instead of bare pointer. You have this in your code: RabbitList * colony = new RabbitList; The answer to "What is a smart pointer and why must you use it" can be found here: stackoverflow.com/questions/106508/what-is-a-smart-pointer-and-when-should-i-use-one