C++ Implementation of Linked List

Question

I have been trying to teach myself C++ recently and would like to have some general feedback and comments on how to improve my code so far. Furthermore, since I am more experienced with other (garbage-collected) languages like Python and Java, I would like to know if I am handling memory correctly or making any fundamental rookie mistakes.

I have attempted to make an implementation of a linked list, given below in LinkedList.h.

#pragma once
#include <stdexcept>
#include <ostream>
/*
 This is a generic-type linked list implemented without using the C++ STL.
 Member functions:
 void append(const T&)
 bool contains(const T&) const
 const T& get(int) const
 void insert(int, const T&)
 int length() const
 void prepend(const T&)
 T remove(int)
 bool removeValue(const T&)
*/
template <typename T>
class LinkedList {
 public:
 // Appends element to the end of the list
 void append(const T& data) {
 insert(len, data);
 }
 // Returns data element at given index
 // Throws std::out_of_range if index is invalid
 const T& get(int index) const {
 if (index < 0 || index >= len)
 throw std::out_of_range("Invalid index in LinkedList::get(int)");
 Node *ptr = Head;
 // Traverse up to the matching node
 for (; index-- ;)
 ptr = ptr -> next;
 return ptr -> data;
 }
 // Prepends element to the start of the list
 void prepend(const T& data) {
 insert(0, data);
 }
 // Removes element at a given index, if possible, and returns it
 // Throws std::out_of_range if index is invalid
 T remove(int index) {
 if (index < 0 || index >= len)
 throw std::out_of_range("Invalid index in LinkedList::remove(int)");
 Node *old;
 if (index == 0) { // Deleting the head
 old = Head; // Save the removed node to free later
 Head = Head -> next; // Skip over the node
 }
 else {
 Node *ptr = Head;
 for (; --index ;) // Traverse up to just before the matching node
 ptr = ptr -> next;
 old = ptr -> next; // Save the removed node to free later
 ptr -> next = old -> next; // Skip over the node
 }
 T ret = old -> data; // Save the removed data to return later
 delete old; // Delete the node from memory
 len--;
 return ret;
 }
 // Removes element by value, if found, and return whether or not it was successful
 bool removeValue(const T& data) {
 Node *ptr = Head;
 if (!ptr) // Empty list
 return false;
 Node *old;
 if (ptr -> data == data) { // Deleting the head
 old = Head; // Save the removed node to free later
 Head = old -> next; // Skip over the node
 }
 else {
 // Advance until the end of the list, or just before the object is found
 while (ptr -> next && ptr -> next -> data != data)
 ptr = ptr -> next;
 if (!ptr -> next) // End of the list
 return false;
 // Object was found
 Node *old = ptr -> next; // Save the removed node to free later
 ptr -> next = old -> next; // Skip over the node
 }
 delete old; // Delete the node from memory
 len--;
 return true;
 }
 // Inserts element at a given index
 // Throws std::out_of_range if index is invalid
 void insert(int index, const T& data) {
 if (index < 0 || index > len)
 throw std::out_of_range("Invalid index in LinkedList::insert(int, const T&)");
 if (index == 0)
 Head = new Node(data, Head);
 else {
 Node *ptr = Head;
 // Traverse up to one node prior to the insertion
 for (; --index ;)
 ptr = ptr -> next;
 ptr -> next = new Node(data, ptr -> next);
 }
 len++;
 }
 // Returns whether or not the list contains a given element
 bool contains(const T& data) const {
 Node *ptr = Head;
 while (ptr != nullptr) {
 if (ptr -> data == data)
 return true;
 ptr = ptr -> next;
 }
 return false;
 }
 // Returns the length of the list
 int length() const {
 return len;
 }
 // Deletes all Nodes in the list
 ~LinkedList() {
 Node *ptr = Head, *next;
 // Iterate through the list
 while (ptr) {
 next = ptr -> next;
 delete ptr;
 ptr = next;
 }
 }
 private:
 class Node { public:
 const T data;
 Node *next;
 Node(const T& data, Node* next = nullptr) : data(data), next(next) { }
 };
 int len = 0;
 Node *Head = nullptr;
 template <typename S>
 friend std::ostream& operator<<(std::ostream&, const LinkedList<S>&);
};
template <typename S>
std::ostream& operator<<(std::ostream& os, const LinkedList<S>& ls) {
 os << "[ ";
 typename LinkedList<S>::Node *ptr = ls.Head, *next;
 // Iterate through the list
 while (ptr) {
 os << ptr -> data;
 next = ptr -> next;
 if (next) // If not at the end of the list
 os << ", ";
 ptr = next;
 }
 os << " ]";
 return os;
}

Additionally, I have written some code for testing most of the features, which I called LinkedList.cpp.

#include <iostream>
#include <iterator>
#include "LinkedList.h"
// Note that this file uses features from the C++17 standard, namely std::size.
int main() {
 LinkedList<int> *L = new LinkedList<int>;
 // This can be done without pointers, too:
 // LinkedList<int> L2;
 // Test append head
 int x = 3;
 L -> append(x);
 // L2.append(x);
 std::cout << "Expected: 3 \tActual: " << L -> get(0) << std::endl << std::endl;
 // std::cout << "Expected: 3\tActual: " << *(L2.get(0)) << std::endl << std::endl;
 // Test repeated append
 int arr[] = {45, 10, 32, 12, 11, 12, 1, -1, 0, 56};
 for (unsigned int i = 0; i < std::size(arr); i++)
 L -> append(arr[i]);
 for (unsigned int i = 0; i < std::size(arr); i++)
 std::cout << "Expected: " << arr[i] << " \tActual: " << L -> get(i + 1) << std::endl;
 std::cout << std::endl;
 // Test remove and length
 x = L -> remove(3);
 std:: cout << "Expected: 32\tActual: " << x << std::endl;
 int newArr[] = {3, 45, 10, 12, 11, 12, 1, -1, 0, 56};
 for (int i = 0; i < L -> length(); i++)
 std::cout << "Expected: " << newArr[i] << " \tActual: " << L -> get(i) << std::endl;
 std::cout << std::endl;
 // Test insert and prepend
 L -> prepend(arr[0]);
 L -> insert(1, arr[1]);
 for (int i = 0; i < 2; i++)
 std::cout << "Expected: " << arr[i] << " \tActual: " << L -> get(i) << std::endl;
 // Test contains
 std::cout << "Expected: 1 \tActual: " << L -> contains(arr[1]) << std::endl;
 std::cout << "Expected: 0 \tActual: " << L -> contains(arr[2]) << std::endl;
 std::cout << "Expected: 1 \tActual: " << L -> contains(arr[3]) << std::endl;
 std::cout << std::endl;
 // Test output operator
 std::cout << "Actual: \t[ 45, 10, 3, 45, 10, 12, 11, 12, 1, -1, 0, 56 ]" << std::endl;
 std::cout << "Expected:\t" << *L << std::endl;
 std::cout << std::endl;
 // Test removeValue
 std::cout << "Expected: 1\tActual: " << L -> removeValue(0) << std::endl;
 std::cout << "Expected: 0\tActual: " << L -> removeValue(9000) << std::endl;
 std::cout << "Expected: 1\tActual: " << L -> removeValue(45) << std::endl;
 std::cout << "Expected: 1\tActual: " << L -> removeValue(45) << std::endl;
 std::cout << "Expected: 1\tActual: " << L -> removeValue(3) << std::endl;
 std::cout << "Expected: 0\tActual: " << L -> removeValue(3) << std::endl;
 std::cout << "Expected: 1\tActual: " << L -> removeValue(56) << std::endl;
 std::cout << "Actual: \t[ 10, 10, 12, 11, 12, 1, -1 ]" << std::endl;
 std::cout << "Expected:\t" << *L << std::endl;
 std::cout << std::endl;
 delete L;
 return 0;
}

Thank you very much! I appreciate any advice or comments.

• 1201ProgramAlarm: Why is data const in Node? That places some unnecessary restrictions on how your class can be used.
• StardustGogeta: @1201ProgramAlarm I made data a const member variable because it allows me to put objects of type const T& into the list, which should catch both lvalue and rvalue expressions in one go (without overloading). Also, the list theoretically should never need to modify one of the Nodes it contains, when you can instead remove it and insert a new value in its place. (If any of the terminology I use is incorrect, please let me know for future reference.)
• Toby Speight: It's probably worth reading the interface of std::list and trying to be compatible with that. For instance, there's no reason to write int length() const instead of std::size_t size() const.
• Loki Astari: Why are you doing this new? LinkedList<int> *L = new LinkedList<int>; A basic rule is that if you call new you are probably doing something wrong. C++ has other techniques that make its memory management automatic. We have what is called fine grained deterministic garbage collection built into the language (smart pointers and containers). You can of course do it manually with new but there is very little need to do this apart from in very specialized cases.
• Loki Astari: Simply use: LinkedList<int> L;

Answer 1

Memory check

Running the provided test program under Valgrind reveals quite a few problems:

valgrind --leak-check=full ./221317 
==9150== Memcheck, a memory error detector
==9150== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==9150== Using Valgrind-3.14.0 and LibVEX; rerun with -h for copyright info
==9150== Command: ./221317
==9150== 
Expected: 3 Actual: 3
Expected: 45 Actual: 45
Expected: 10 Actual: 10
Expected: 32 Actual: 32
Expected: 12 Actual: 12
Expected: 11 Actual: 11
Expected: 12 Actual: 12
Expected: 1 Actual: 1
Expected: -1 Actual: -1
Expected: 0 Actual: 0
Expected: 56 Actual: 56
Expected: 32 Actual: 32
Expected: 3 Actual: 3
Expected: 45 Actual: 45
Expected: 10 Actual: 10
Expected: 12 Actual: 12
Expected: 11 Actual: 11
Expected: 12 Actual: 12
Expected: 1 Actual: 1
Expected: -1 Actual: -1
Expected: 0 Actual: 0
Expected: 56 Actual: 56
Expected: 45 Actual: 45
Expected: 10 Actual: 10
Expected: 1 Actual: 1
Expected: 0 Actual: 0
Expected: 1 Actual: 1
Actual: [ 45, 10, 3, 45, 10, 12, 11, 12, 1, -1, 0, 56 ]
Expected: [ 45, 10, 3, 45, 10, 12, 11, 12, 1, -1, 0, 56 ]
==9150== Conditional jump or move depends on uninitialised value(s)
==9150== at 0x4837041: operator delete(void*, unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==9150== by 0x109FE6: LinkedList<int>::removeValue(int const&) (221317.cpp:84)
==9150== by 0x1097A2: main (221317.cpp:212)
==9150== 
==9150== Invalid free() / delete / delete[] / realloc()
==9150== at 0x483708B: operator delete(void*, unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==9150== by 0x109FE6: LinkedList<int>::removeValue(int const&) (221317.cpp:84)
==9150== by 0x1097A2: main (221317.cpp:212)
==9150== Address 0x1fff0006d0 is on thread 1's stack
==9150== in frame #2, created by main (221317.cpp:166)
==9150== 
Expected: 1 Actual: 1
Expected: 0 Actual: 0
Expected: 1 Actual: 1
==9150== Conditional jump or move depends on uninitialised value(s)
==9150== at 0x4837041: operator delete(void*, unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==9150== by 0x109FE6: LinkedList<int>::removeValue(int const&) (221317.cpp:84)
==9150== by 0x1098A1: main (221317.cpp:215)
==9150== 
==9150== Invalid free() / delete / delete[] / realloc()
==9150== at 0x483708B: operator delete(void*, unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==9150== by 0x109FE6: LinkedList<int>::removeValue(int const&) (221317.cpp:84)
==9150== by 0x1098A1: main (221317.cpp:215)
==9150== Address 0x1fff0006d0 is on thread 1's stack
==9150== in frame #2, created by main (221317.cpp:166)
==9150== 
Expected: 1 Actual: 1
==9150== Conditional jump or move depends on uninitialised value(s)
==9150== at 0x4837041: operator delete(void*, unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==9150== by 0x109FE6: LinkedList<int>::removeValue(int const&) (221317.cpp:84)
==9150== by 0x1098F6: main (221317.cpp:216)
==9150== 
==9150== Invalid free() / delete / delete[] / realloc()
==9150== at 0x483708B: operator delete(void*, unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==9150== by 0x109FE6: LinkedList<int>::removeValue(int const&) (221317.cpp:84)
==9150== by 0x1098F6: main (221317.cpp:216)
==9150== Address 0x1fff0006d0 is on thread 1's stack
==9150== in frame #2, created by main (221317.cpp:166)
==9150== 
Expected: 1 Actual: 1
Expected: 0 Actual: 0
==9150== Conditional jump or move depends on uninitialised value(s)
==9150== at 0x4837041: operator delete(void*, unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==9150== by 0x109FE6: LinkedList<int>::removeValue(int const&) (221317.cpp:84)
==9150== by 0x1099A0: main (221317.cpp:218)
==9150== 
==9150== Invalid free() / delete / delete[] / realloc()
==9150== at 0x483708B: operator delete(void*, unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==9150== by 0x109FE6: LinkedList<int>::removeValue(int const&) (221317.cpp:84)
==9150== by 0x1099A0: main (221317.cpp:218)
==9150== Address 0x1fff0006d0 is on thread 1's stack
==9150== in frame #2, created by main (221317.cpp:166)
==9150== 
Expected: 1 Actual: 1
Actual: [ 10, 10, 12, 11, 12, 1, -1 ]
Expected: [ 10, 10, 12, 11, 12, 1, -1 ]
==9150== 
==9150== HEAP SUMMARY:
==9150== in use at exit: 64 bytes in 4 blocks
==9150== total heap usage: 16 allocs, 16 frees, 73,952 bytes allocated
==9150=わ=わ 
=わ=わ9150=わ=わ 16 bytes in 1 blocks are definitely lost in loss record 2 of 3
==9150== at 0x4835DEF: operator new(unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==9150== by 0x109D94: LinkedList<int>::insert(int, int const&) (221317.cpp:95)
==9150== by 0x109B27: LinkedList<int>::append(int const&) (221317.cpp:21)
==9150== by 0x109233: main (221317.cpp:173)
==9150=わ=わ 
=わ=わ9150=わ=わ 48 (32 direct, 16 indirect) bytes in 2 blocks are definitely lost in loss record 3 of 3
==9150== at 0x4835DEF: operator new(unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==9150== by 0x109DEB: LinkedList<int>::insert(int, int const&) (221317.cpp:101)
==9150== by 0x109B27: LinkedList<int>::append(int const&) (221317.cpp:21)
==9150== by 0x109316: main (221317.cpp:181)
==9150== 
==9150== LEAK SUMMARY:
==9150== definitely lost: 48 bytes in 3 blocks
==9150== indirectly lost: 16 bytes in 1 blocks
==9150== possibly lost: 0 bytes in 0 blocks
==9150== still reachable: 0 bytes in 0 blocks
==9150== suppressed: 0 bytes in 0 blocks
==9150== 
==9150== For counts of detected and suppressed errors, rerun with: -v
==9150== Use --track-origins=yes to see where uninitialised values come from
==9150== ERROR SUMMARY: 10 errors from 10 contexts (suppressed: 0 from 0)

All these problems are caused by shadowing old here:

 Node *old;
 if (ptr -> data == data) {
 old = Head;
 ...
 }
 else {
 ...
 Node *old = ptr -> next;
 ...
 }
 delete old; // Delete the node from memory

Changing to else { ... old = ptr -> next; ... } fixes them.

Rule of Five

The class has a non-trivial destructor and an owning raw pointer member. Those are both signs that we need to proved user-defined copy/move constructors and assignment operators.

Without those, consider what happens when a LinkedList is copied. Both lists now share the same Head. If we delete one of the lists, it cleans up its memory, so the other one now has a dangling pointer. That's a recipe for Undefined Behaviour (in its destructor, if not earlier).

A small amendment to the test program will soon expose the problem:

{
 LinkedList<char> s;
 s.append('a');
 auto s2 = s;
}

It's worth running the new test under Valgrind (or other memory checker) so that you learn to recognise the symptoms there (which will help if you come across similar bugs in future):

 Invalid read of size 8
 at 0x10A0F9: LinkedList<char>::~LinkedList() (221317.cpp:127)
 by 0x109AD0: main (221317.cpp:226)
 Address 0x4d75528 is 8 bytes inside a block of size 16 free'd
 at 0x483708B: operator delete(void*, unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
 by 0x10A111: LinkedList<char>::~LinkedList() (221317.cpp:128)
 by 0x109AC1: main (221317.cpp:228)
 Block was alloc'd at
 at 0x4835DEF: operator new(unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
 by 0x10A1E6: LinkedList<char>::insert(int, char const&) (221317.cpp:95)
 by 0x10A147: LinkedList<char>::append(char const&) (221317.cpp:21)
 by 0x109A96: main (221317.cpp:227)
 Invalid free() / delete / delete[] / realloc()
 at 0x483708B: operator delete(void*, unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
 by 0x10A111: LinkedList<char>::~LinkedList() (221317.cpp:128)
 by 0x109AD0: main (221317.cpp:226)
 Address 0x4d75520 is 0 bytes inside a block of size 16 free'd
 at 0x483708B: operator delete(void*, unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
 by 0x10A111: LinkedList<char>::~LinkedList() (221317.cpp:128)
 by 0x109AC1: main (221317.cpp:228)
 Block was alloc'd at
 at 0x4835DEF: operator new(unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
 by 0x10A1E6: LinkedList<char>::insert(int, char const&) (221317.cpp:95)
 by 0x10A147: LinkedList<char>::append(char const&) (221317.cpp:21)
 by 0x109A96: main (221317.cpp:227)

The thing to pick up here is that the second memory block in the report was deleted in ~LinkedList() and again in ~LinkedList(), at the same line. That suggests that two objects have deleted the same memory (unless we knew that some code was explicitly calling destructors, but that's rare, and we tend to inspect such code very carefully). The first block is also relevant - that's us attempting to access ptr->next from s2's destructor after s was deleted.

At a minimum, we could write:

LinkedList(const LinkedList&) = delete;
LinkedList& operator=(const LinkedList&) = delete;

A more useful fix would be to actually implement these, and probably also the versions that accept rvalue references (because we can simply move the contents much more efficiently than copying would be):

LinkedList(const LinkedList&);
LinkedList(LinkedList&&);
LinkedList& operator=(const LinkedList&);
LinkedList& operator=(LinkedList&&);

• StardustGogeta: Thank you so much! I had not heard of Valgrind before, so I will look into that to help me diagnose problems with my code in the future. I had not heard of the "Rule of Five," either, but that also looks like something that will definitely come in handy.
• Toby Speight: Yes, Valgrind is a really useful tool, and it helps me often. It is (unavoidably) resource hungry, as the cost of recording every allocation "just in case" means that your code runs very slowly and eats memory - it's best applied to unit tests where possible, rather than full applications. I primarily use it on Linux; not sure what the alternatives are on non-Unix platforms, but I expect that comparable tools exist.
• Toby Speight: You'll find some good reading if you search for "Rule of Zero" - or try CPPReference's rule of three/five/zero page.