Linked list implementation correctness

I've started learning C++ and I wanted to ask you to take a look at my linked list implementation and give comments what's wrong with. It compiles and runs fine, but I am curious about const correctness, proper use of pointers/references, etc., so feel free to go super tough on me!

I've read about these concepts online but this doesn't get me far without an experienced C++ programmer's opinion.

Node:

#include 

#pragma once
template 
class Node
{
const char * const _key;
Node *_next;
T _value;

public:
Node(const char * const key, const T &value) : _key(key), _value(value), _next(nullptr) {}

const char * const getKey()
{
    return _key;
}

Node *getNext()
{
    return _next;
}

void setNext(Node *next)
{
    _next = next;
}

T &getValue()
{
    return _value;
}
};

Linked List:

#include 
#include "Node.h"

#pragma once

template 

class LinkedList
{
int _count;
Node *_first;

public:
LinkedList() : _count(0), _first(nullptr) {}

Node *add(const char * const key, const T &value)
{
    Node *first = new Node(key, value);
    first->setNext(_first);
    _first = first;
    _count++;
    return _first;
}

void remove(const char * const key)
{
    Node *next = _first;
    Node *previous = nullptr;

    while (next)
    {
        if (next->getKey() == key)
        {
            if (next == _first)
                _first = next->getNext();
            else
                previous->setNext(next->getNext());
            _count--;
            return;
        }
        previous = next;
        next = next->getNext();
    }
}

int getCount() 
{ 
    return _count;
}

Node * const getFirst()
{
    return _first;
}
};

I am not too certain how to properly define value inside Node class, because I want to support both primitive types and objects.

This actually worked for me, although this is probably not correct?

if (next->getKey() == key)

There are quite a few issues with your code as it stands. I know you've said to go "super tough" on you, but the amount of knowledge required to write a relatively complete linked list implementation in C++ is more than just about any other language.

As a minor point up-front, I'm going to change anything that has a prefixed _ (like _first or _key) to using a postfix underscore (so first_ and key_). The reason for this is that certain symbols are reserved for compiler usage; the rules are arcane, but the simplest thing to do is:

• Avoid anything with a leading underscore (_)

• Avoid anything with 2 trailing underscores (__)

Edit: As pointed out by @JerryCoffin, you should avoid __ just about anywhere (prefix, postfix, and so on).

The first (and largest) problem is that this never frees any of the heap allocated memory (that is, memory allocated with new). Every time you do:

Node *first = new Node(key, value);

This will allocate memory from the heap. Unlike garbage collected languages (most languages except C and C++), it is up to you, the programmer, to free this memory when you are done with it. Here, this means manually writing the destructor:

~LinkedList()
{
    Node* next = _first;
    while(next != nullptr) {
        first_ = first_->next;
        delete next;
        next = first_;
    }
}

This will make sure that memory is reclaimed.

To go along with this, there are a few methods that are implicitly generated for you when you write a class in C++. These are the copy assignment operator, and the copy constructor. They have the forms:

LinkedList& operator=(const LinkedList& rhs); // Copy assignment
LinkedList(const LinkedList& rhs);  // Copy constructor

When are these called? Say you define a LinkedList:

LinkedList a;
// Do some operations on a, such as adding nodes
LinkedList b;
// Some operations on b
b = a;  // Calls the copy assignment operator, operator=
LinkedList c(a);   // Calls the copy constructor

The methods that C++ implements for you here will do something that you do not want them to do: the b.first_ pointer will be equal to a.first_. What this means is that, if the destructor for a is called, then b will be pointing to memory locations that have been reclaimed using delete (which is very, very bad).

To fix this, they need to be implemented to do the correct thing. So, what is the correct thing to do? Let's look at them each in turn:

The copy constructor just needs to copy each element of the passed in LinkedList in turn:

LinkedList(const LinkedList& rhs)
{
    Node* tmp = rhs.first_;
    while(tmp != nullptr) {
        add(tmp->key_, tmp->value_);
    }
}

The copy assignment operator needs to:

• Free the current memory held by this

• Copy each value in the list rhs

So, the implementation looks something like:

LinkedList& operator=(const LinkedList& rhs)
{
    // Stop self assignment, like: a = a;
    if(&rhs != this) {
        // Step 1: Free current memory
        Node* tmp = first_;
        while(tmp->next != nullptr) {
            first_ = first_->next;
            delete tmp;
            tmp = first_;
        }
        count_ = 0;

        // Step 2: Create a copy of rhs
        temp = rhs.first_;
        while(tmp != nullptr) {
            add(tmp->key_, tmp->value_);
        }
    }
    return *this;
}

This is actually a very well known thing in C++: it is called the rule of three (or in more modern C++, the rule of five - but ignore this for the moment). What it says is:

If you need to manually write any one of the destructor/copy constructor/copy assignment operator, then you need to manually define all three of them.

For a full treatment of this, you might want to read this post.

Using a const char * const as a key in a linked list is unusual, and doesn't really fit with the basic idea of the data structure. If you want to look something up by key, you're generally looking for a data structure called a map (or hashmap, or dictionary; there are multiple names for it). I'd remove the complication there, and just get rid of the key member entirely.

void add(const T &value)
{
    Node *first = new Node(key, value);
    first->next_ = first_;
    first_ = first;
    count_++;
}

I've also removed the return of the Node . You generally don't want to let the users of your class have direct access to a Node .

Your remove function also leaks memory, you again need to have a delete in there.

Node* tmp = next;
 if (next == _first) {
     _first = next->getNext();
     delete tmp;   // Need a delete here
 }
 else {
     previous->setNext(next->getNext());
     delete tmp;  // Or here
 }
 _count--;

Edit: How you've written a search is much more dictionary-like. For the standard library list, you'd often use something like std::find_if, which takes a predicate (which is just a fancy word for a function that returns a bool). This allows you to

StackExchange Code Review Q#55655, answer score: 11