C++ Linked List Implementation

Question

I'm learning C++ and also about data structures, so I am trying to implement some. This is my linked list. I've included two different ways of getting the length of the list, with a length variable and also a function (getLength2) that goes through the list until it finds a NULL pointer. I suspect that there could be memory leaks in it, though I'm not sure.

    #include "stdafx.h"
    #include <iostream>
    using namespace std;

    template <class val>
    class linked_list{
        struct node{
            val value;
            node *next;
        };
        node *start;
        unsigned int length;
    public:
        linked_list() { length = 0; start = NULL; }
        unsigned int getLength() { return length; }
        val getFirst() { return (*start).value; }
        unsigned int getLength2();
        void add(val value);
        val getVal(unsigned int pos);
        val pop();
    };

    int _tmain(int argc, _TCHAR* argv[])
    {
        linked_list<int> gary;
        for (int i = 0; i < 10; ++i){
            gary.add(pow(2, i));
        }
        for (int k = 0; gary.getLength() > 0; ++k){
            cout << gary.pop() << ' ' << gary.getLength() << endl;
        }
        return 0;
    }

    template <class val>
    void linked_list<val>::add(val value){
        node *second = start;
        start = new node;
        (*start).value = value;     
        (*start).next = second;
        length += 1;
    }

    template <class val>
    val linked_list<val>::getVal(unsigned int pos){
        node current = *start;
        for (unsigned int depth = 0; depth < pos; ++depth){
            current = *(current.next);
        }
        return current.value;
    }

    template <class val>
    val linked_list<val>::pop(){
        val ret = start->value;
        node *new_address = start->next;
        delete start;
        start = new_address;
        length -= 1;
        return ret;
    }

    template <class val>
    unsigned int linked_list<val>::getLength2() {
        if (start == NULL){
            return 0;
        }
        node current = *start;
        unsigned int len = 1;
        while (current.next != NULL){
            current = *(current.next);
            len += 1;
        }
        // should this have a 'delete current'?
        return len;
    }

Answer 1

You do have a memory leak. In your add(val value) function, you allocate a start = new node, but never delete it. To plug the leak, you need to either delete start; in add() OR add a destructor and delete start; there.

Another issue is including the math header so you can use the pow() function. You need to include the <tgmath.h> header.

You don't need a delete current where the comment is. You do not dynamically allocate current with new in the function, so there is nothing to delete.

Answer 2

• Your "getters" should be const since they don't modify any data members. This will also protect you against any accidental modifications in those functions.

  unsigned int getLength() const { return length; }
  

• The constructor can instead be an initializer list:

  linked_list() : length(0), start(NULL) {}
  

• Be aware of the issues regarding using namespace std.

• If you have a C++11-compliant compiler, use nullptr instead of NULL.

• Be aware that _tmain() and _TCHAR* are non-portable, so anyone using this code outside of Visual Studio will not be able to compile it. In order to make this portable, change them to main() and char* respectively.

• Since you're using std::pow(), you should include <cmath>. Although <iostream> is already covering it, you should add this library anyway.

• There's not really a need for getLength2(). You just need to increment or decrement length, depending on the list operation. Your inline "getter" will, of course, return this updated length.

  Regarding incrementing/decrementing, length += 1 and length -= 1 can respectively be length++ and length--.

• The val argument for add() should be passed by const&, especially if it happens to be of a non-primitive type.

• You should consider error-checking (empty list) in pop() if you'd still like it to return the popped value. Otherwise, you can make it void and simply return if the list is already empty.

• Instead of (*start).value, use the -> operator for readability: start->value.