Btukfyl

I have a constructor, destructor, a function that returns to the head of the Linked list. I am not sure about the createNode function and couldn't figure out how to do the addNode function.

//constructor

LinkedList::LinkedList()

{

head = NULL;

}

//destructor

LinkedList::~LinkedList()

{

struct Node *temp = head;

int nodeCount = 0;

struct Node *nextNode;

while (temp != NULL)

{

    nextNode = temp->next;

    delete temp;

    nodeCount++;

    temp = nextNode;

}

head = NULL;

cout << "The number of deleted nodes is: " << nodeCount << "n";

}

//This function returns the head of the linked list

Node *LinkedList::getHead()  

{

return head;

}

//This function creates a new node with the given parameter info. It returns a pointer that points to the newly created node.

Node * LinkedList::createNode(string name, int winScore, int loseScore)

{



Node *temp = new Node;

temp->name = name;

temp->winScore = winScore;

temp->loseScore = loseScore;

temp->next = NULL;



return new Node; // I think I have done this function right but please correct me if I'm wrong

}

//The function calls createnode first. It then insert the newly created node inside the linked list in alphabetical order. It also returns a pointer that
points to the newly added node.

Node *LinkedList::addNode(string name, int winScore, int loseScore)

{

 //add code here which I couldn't do

}

Linked lists are somewhat generic. With a simple implementation, you create a class instance for the list and the constuctor does nothing more than set the first node (head) of the list to NULL. (you can overload your constructor to take character data and call insert as well)

You start with your data structure (or class, your choice):

struct node_t {     /* simple struct holding char and next pointer */

    char data;

    node_t *next;

};

The insert function always creates and allocates storage for a new node and initializes the next pointer NULL, e.g.

class linkedlist {



    node_t *head, *iter;            /* private members */



  public:

    linkedlist() {                  /* constructor - sets head NULL */

        head = NULL;

    }

    ...

    node_t *insert (char data) {



        node_t *node = new node_t;  /* allocate new node */



        node->data = data;          /* set node data */

        node->next = NULL;

        ...

At this point in insert, all that remains is checking whether head == NULL, and if so, you know this is your first node, so simply set head = node;, e.g.

        if (!head)                  /* if 1st node */

            head = node;

If head != NULL, then you know you need to set iter = head; and iterate to the list-end to set the last->next = node;. You can do this with a simple while loop, e.g.

        else {              /* otherwise */

            iter = head;

            while (iter->next)      /* traditional iterate to find last */

                iter = iter->next;

            iter->next = node;      /* set new last */

        }

That's basically it other than returning a pointer to node. However, if you keep a last pointer, and always set last = node; at the end of your insert function, then there is no need to iterate to find the last node, you simply set last->next = node; instead of iterating and then update last = node;

A short example putting it altogether may help:

#include <iostream>

#include <string>



using namespace std;



struct node_t {     /* simple struct holding char and next pointer */

    char data;

    node_t *next;

};



class linkedlist {



    node_t *head, *iter;            /* private members */



  public:

    linkedlist() {                  /* constructor - sets head NULL */

        head = NULL;

    }

    ~linkedlist() {                 /* destructor - free list memory */

        iter = head;



        while (iter) {

            node_t *victim = iter;

            iter = iter->next;

            delete victim;

        }

    }



    node_t *insert (char data) {



        node_t *node = new node_t;  /* allocate new node */



        node->data = data;          /* set node data */

        node->next = NULL;



        if (!head)                  /* if 1st node */

            head = node;

        else {              /* otherwise */

            iter = head;

            while (iter->next)      /* traditional iterate to find last */

                iter = iter->next;

            iter->next = node;      /* set new last */

        }



        return node;                /* return node */

    }



    void print (void) {             /* simple print function */

        iter = head;

        while (iter) {

            cout << iter->data;

            iter = iter->next;

        }

        cout << 'n';

    }

};



int main (void) {



    string s = "my dog has fleas";

    linkedlist l;



    for (auto& c : s)

        l.insert(c);



    l.print();

}

Example Use/Output

$ ./bin/ll_insert

my dog has fleas

Memory Use/Error Check

Always use a memory/error checking program to verify you haven't done anything bizarre with your allocations and to confirm you have freed all the memory you allocate. For Linux, valgrind is the normal choice. Just run your program through it:

$ valgrind ./bin/ll_insert

==9240== Memcheck, a memory error detector

==9240== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.

==9240== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info

==9240== Command: ./bin/ll_insert

==9240==

my dog has fleas

==9240==

==9240== HEAP SUMMARY:

==9240==     in use at exit: 0 bytes in 0 blocks

==9240==   total heap usage: 18 allocs, 18 frees, 73,001 bytes allocated

==9240==

==9240== All heap blocks were freed -- no leaks are possible

==9240==

==9240== For counts of detected and suppressed errors, rerun with: -v

==9240== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Look things over and let me know if you have further questions. I'll leave the last pointer implementation to you.

Adding a Separate create Node Function

You have the flexibility to decide how you want to factor your code into separate function. A create function normally just handles allocating for the node and setting the data values and initializing next to NULL. I'm not sure how much that makes things easier here, but where you have a complex create function, it does help tidy up the insert function a great deal.

Here you simply move the call to new and assignment to data and next to the new create function and call create at the top of insert, e.g.

    node_t *create (char data) {    /* simply move allocation/initialization

                                       to a create function */

        node_t *node = new node_t;  /* allocate new node */



        node->data = data;          /* set node data */

        node->next = NULL;



        return node;

    }



    node_t *insert (char data) {



        node_t *node = create (data);   /* call create function */



        if (!head)                  /* if 1st node */

            head = node;

        else {              /* otherwise */

            iter = head;

            while (iter->next)      /* traditional iterate to find last */

                iter = iter->next;

            iter->next = node;      /* set new last */

        }



        return node;                /* return node */

    }

It is functionally identical to doing it all in insert (and a smart compiler will probably optimize it identically as well). So it is entirely up to you what makes it easier to understand.