HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppModerate

C++ Linked List Implementation

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
listimplementationlinked

Problem

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 
    using namespace std;

    template 
    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 gary;
        for (int i = 0; i  0; ++k){
            cout 
    void linked_list::add(val value){
        node *second = start;
        start = new node;
        (*start).value = value;     
        (*start).next = second;
        length += 1;
    }

    template 
    val linked_list::getVal(unsigned int pos){
        node current = *start;
        for (unsigned int depth = 0; depth 
    val linked_list::pop(){
        val ret = start->value;
        node *new_address = start->next;
        delete start;
        start = new_address;
        length -= 1;
        return ret;
    }

    template 
    unsigned int linked_list::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;
    }

Solution

-
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 `. Although 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`.

Code Snippets

unsigned int getLength() const { return length; }
linked_list() : length(0), start(NULL) {}

Context

StackExchange Code Review Q#82770, answer score: 10

Revisions (0)

No revisions yet.