7
\$\begingroup\$

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;
    }
\$\endgroup\$
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks. Surely in the add(val value) the dynamically allocated node is the one used to store the new value that is added to the list though, so can't be deleted. (except when the value is to be removed from the list with the pop function or such like) \$\endgroup\$ – user2826750 Feb 27 '15 at 22:03
  • \$\begingroup\$ @user2826750 That's why I suggested a destructor, in which you delete the start node. If you only have it in the pop() function, it might never be deleted, leading to a leak. \$\endgroup\$ – Rhuarc13 Feb 27 '15 at 22:06
  • \$\begingroup\$ Also, using a node instead of a node* for iteration causes many unnecessary copies. \$\endgroup\$ – immibis Feb 28 '15 at 0:17
11
\$\begingroup\$
  • 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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.