Linked List exercise, what am I doing wrong?

Question

Hey all. I'm doing a linked list exercise that involves dynamic memory allocation, pointers, classes, and exceptions. Would someone be willing to critique it and tell me what I did wrong and what I should have done better both with regards to style and to those subjects I listed above?

/*

Linked List exercise

*/

#include <iostream>
#include <exception>
#include <string>
using namespace std;

class node{
public:
    node * next;
    int * data;
    node(const int i){
        data = new int;
        *data = i;
    }
    node& operator=(node n){
        *data = *(n.data);
    }
    ~node(){
        delete data;
    }
};

class linkedList{

public:

    node * head;
    node * tail;
    int nodeCount;

    linkedList(){
        head = NULL;
        tail = NULL;
    }

    ~linkedList(){
        while (head){
            node* t = head->next;
            delete head;
            if (t) head = t;
        }
    }

    void add(node * n){
        if (!head) {
            head = n;
            head->next = NULL;
            tail = head;
            nodeCount = 0;
        }else {
            node * t = head;
            while (t->next) t = t->next;
            t->next = n;
            n->next = NULL;
            nodeCount++;
        }
    }

    node * operator[](const int &i){
        if ((i >= 0) && (i < nodeCount)) throw new exception("ERROR:  Invalid index on linked list.", -1);
        node *t = head;
        for (int x = i; x < nodeCount; x++) t = t->next;
        return t;
    }

    void print(){
        if (!head) return;
        node * t = head;
        string collection;
        cout << "[";
        int c = 0;
        if (!t->next) cout << *(t->data);
        else while (t->next){
            cout << *(t->data);
            c++;
            if (t->next) t = t->next;
            if (c < nodeCount) cout << ", ";
        }
        cout << "]" << endl;
    }

};

int main (const int & argc, const char * argv[]){

    try{
        linkedList * myList = new linkedList;
        for (int x = 0; x < 10; x++) myList->add(new node(x));
        myList->print();
    }catch(exception &ex){
        cout << ex.what() << endl;
        return -1;
    }   
    return 0;
}

Answer 1

There's no need for data to be a pointer.

Use the ctor-initializer list, it's better for const-correctness and exception safety. None of your constructors need to have any code inside the body.

Your linkedList constructor didn't initialize nodeCount.

You aren't using your list's tail pointer for anything. It would save you scanning through the entire list in the non-empty case of add -- if you kept it up to date.

Indexing (operator[]) is an unusual thing to support on a linked list. OTOH you haven't made a remove function.

operator[] shouldn't take its parameter by reference. Only large structures need to be passed by const reference, small type like int should just be passed by value.

Right now, if add fails, the pointer to new node() leaks. (But I don't actually see a way for add to fail unless the list links got corrupted.)

You should define a private copy-constructor on node to prevent double-free of the data. Any time you define operator= and destructor you should also be defining or deleting the copy constructor (rule of three). You should also define private copy constructor and assignment operator on linkedList to prevent double-free.

The variable string collection in your print function isn't used. The variable t in print() should be a pointer to const. print itself should be a const member function.

Answer 2

if ((i >= 0) && (i < nodeCount)) throw new exception("ERROR:  Invalid index on linked list.", -1);

That line should read:

if( i < 0 || i >= nodeCount ) throw...

The add method also has issues:

void add(node * n){
    if (!head) {
        head = n;
        head->next = NULL;
        tail = head;
        nodeCount = 0;
    }else {
        node * t = head;
        while (t->next) t = t->next;
        t->next = n;
        n->next = NULL;
        nodeCount++;
    }
}

For one after you add the first node count will be 0, for another you're doing a search to insert into a linked list... an operation people would expect to be O(1).

A more typical implementation would be:

void add( node* n ) {
   node* old_head = head;
   head = n;
   head->next = old_head;
   ++nodeCount;
   if( old_head == NULL )
      tail = head
}

Answer 3

1) You can use data = new int(i) to initialize field.

2) You've created a wrong condition in operator[] if ((i >= 0) && (i < nodeCount)), it should be inverted, like if ((i < 0) || (i >= nodeCount))

Answer 4

/*
Linked List exercise
*/

class node {
public:
    node * next;
    int * data;

data doesn't really need to be a pointer (unless your classroom assignment says it has to be). You can change this to an int, and then change your references from *(t->data) to just t->data. Likewise, you won't need to use new and delete in the ctor/dtor.

    node(const int i) {
        data = new int;
        *data = i;
    } 
    node& operator=(node n) {
        *data = *(n.data);
    } 
    ~node() {
        delete data;
    } 
};

class linkedList {

public:
    node * head;
    node * tail;
    int nodeCount;

    linkedList() {
        head = NULL;
        tail = NULL;

You should initialize all or your data members here. nodeCount will have some random value unless you set it to zero here.

    } 

    ~linkedList() {
        while (head) {
            node* t = head->next;
            delete head;
            if (t)
                head = t;

This looks like a bug. You need to always assign head = t, even when t is NULL, otherwise your loop won't terminate (but deleting the same node multiple times will probably cause an exception).

        } 
    } 

    void add(node * n) {
        if (!head) {
            head = n;
            head->next = NULL;
            tail = head;
            nodeCount = 0;

I think this whole if statement is unnecessary. Both branches do the same thing when the linked list is empty, so you can just always use the second (else) branch.

Also, setting nodeCount to 0 at the end seems like a bug; shouldn't it be 1?

        } else {
            node * t = head;

            while (t->next)
                t = t->next;

            t->next = n;
            n->next = NULL;
            nodeCount++;
        } 
    } 

    node * operator[](const int &i) {

A minor nit, but a const int & argument doesn't really make any sense. You're not gaining anything over just passing an int type.

        if ((i >= 0) && (i < nodeCount))
            throw new exception("ERROR:  Invalid index on linked list.", -1);

The condition above looks backwards to me; you'll always throw the exception with valid parameters.

        node *t = head;

        for (int x = i; x < nodeCount; x++)
            t = t->next;

The loop above seems a little suspect to me. If i is the zero-based index of the node you want, shouldn't your counter go from 0 to i-1?

        return t;
    } 

    void print() {
        if (!head)
            return;

Again, you should make this method work without having to guard against an empty list. I would expect an empty list to print something like [], but with the guard code above, you'll print nothing.

        node * t = head;
        string collection;
        int c = 0;

        cout << "[";

        if (!t->next) {
            cout << *(t->data);

Like the other condition above, I think the branch above is unnecessary. The second (else) branch should handle the NULL case just fine.

        } else {
            while (t->next) {

I think you want while (t) above and not while (t->next)

                cout << *(t->data);
                c++;

                if (t->next)
                    t = t->next;

I think this is a bug like the one earlier on. You should always be assigning `t = t->next', otherwise your loop won't terminate.

                if (c < nodeCount)
                    cout << ", ";
            } 
        } 

        cout << "]" << endl;
    } 
};

int main (const int & argc, const char * argv[]) { // const int& ?

const int & again...

    try {
        linkedList * myList = new linkedList;
        for (int x = 0; x < 10; x++)
            myList->add(new node(x));
        myList->print();
    } catch(exception &ex) {
        cout << ex.what() << endl;
        return -1;
    }  

Probably fine for a homework assignment, but catching every possible exception (as you're doing above) probably doesn't add much value here, and is generally regarded as poor practice.

If you omit this try/catch stuff above, I suspect that whenever your program terminates with an exception, the default, top-level exception handler provided by the compiler will dump out the exception and stack trace info anyway (depends on your compiler).

    return 0;
}