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 (
_<varname>)
- Avoid anything with 2 trailing underscores (
<varname>__)
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<T> *first = new Node<T>(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<T>* 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<int>:
LinkedList<int> a;
// Do some operations on a, such as adding nodes
LinkedList<int> b;
// Some operations on b
b = a; // Calls the copy assignment operator, operator=
LinkedList<int> 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<T>* 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<T>* 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<T> *first = new Node<T>(key, value);
first->next_ = first_;
first_ = first;
count_++;
}
I've also removed the return of the Node<T> *. You generally don't want to let the users of your class have direct access to a Node<T> *.
Your remove function also leaks memory, you again need to have a delete in there.
Node<T>* 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 use an actual function to select what you're looking for. As an example, if you have a Student struct:
struct Student
{
std::string name;
int age;
int year;
};
Then you had a list of Students:
std::list<Student> students;
You might want to search for a student who has the name "John": this would look like:
std::find_if(students.begin(), students.end(), [](const Student& s)
{ return s.name == "John"; });
In fact, this will actually return an iterator into the container.
This also gives you more flexibility, as you can use the same function to find a student who is, say, 17 years old:
std::find_if(students.begin(), students.end(), [](const Student& s)
{ return s.age == 17; });
