5
\$\begingroup\$

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.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Why is data const in Node? That places some unnecessary restrictions on how your class can be used. \$\endgroup\$ May 30 '19 at 3:23
  • \$\begingroup\$ @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.) \$\endgroup\$ May 30 '19 at 4:01
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ May 30 '19 at 11:17
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ May 30 '19 at 16:11
  • \$\begingroup\$ Simply use: LinkedList<int> L; \$\endgroup\$ May 30 '19 at 16:15
6
\$\begingroup\$

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&&);
\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$ May 31 '19 at 2:19
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ May 31 '19 at 7:31
  • 1
    \$\begingroup\$ You'll find some good reading if you search for "Rule of Zero" - or try CPPReference's rule of three/five/zero page. \$\endgroup\$ May 31 '19 at 7:31

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.