11
\$\begingroup\$

To hone my skills with C++11, I'm implementing a singly-linked list based on the requirements I found at this link.

I've implemented code that supports the following subset of requirements from the link above. I would like feedback on what I have so far. The requirements implemented on the posted code are:

  • Generic datatyping
  • Add data:
    • Add at beginning
    • Add at the end
    • Add at a specific position
    • Add another list's data at beginning/end/position

I'm not interested in performance issues in my code, but more interested in maintainability, code readability, and unit test coverage. I have implemented unit tests using Boost's unit test framework, and I'm specifically interested in code coverage and whether I've overdone or underdone my unit tests (have I missed anything, and have I tested something "too much"), as well as feedback over my "development process".

My development process so far has been:

  1. Write the LinkedList.h header file to define the implementation.
  2. Write the unit tests to test the methods declared in the class.
  3. Write the implementation of the LinkedList class methods, in order to get the previously written unit tests to pass.
  4. There was a bit of iteration after step 3 because my unit tests weren't quite correct.

Here is the implementation of the linked list (LinkedList.h):

#pragma once

#include <memory>

template <typename T>
class LinkedList
{
    static_assert(std::is_copy_assignable<T>::value, "T must be copy assignable.");

private:
    struct Node
    {
        Node(const T& value) : _value{ value }, _next{ nullptr } {};
        T _value;
        std::shared_ptr<Node> _next;
    };

public:
    LinkedList();

    void push_front(const T& value);
    void push_front(const LinkedList<T>& other);
    void push_back(const T& value);
    void push_back(const LinkedList<T>& other);
    void insert_at(size_t index, const T& value);
    void insert_at(size_t index, const LinkedList<T>& other);

    T get_value_at(size_t index) const;

    size_t size() const;

private:
    // The first node in the list, nullptr if the list is empty.
    std::shared_ptr<Node> _head;

    // Gets a pointer to the last node.
    // Precondition: List is not empty.
    std::shared_ptr<Node> get_tail_node();

    // Gets the node at the specified index.
    // Precondition: List is not empty.
    std::shared_ptr<Node> get_node_at(size_t index);
};

template <typename T>
LinkedList<T>::LinkedList()
{
}

template <typename T>
void LinkedList<T>::push_front(const T& value)
{
    auto new_head = std::make_shared<Node>(value);
    new_head->_next = _head;
    _head = new_head;
}

template <typename T>
void LinkedList<T>::push_front(const LinkedList<T>& other)
{
    for (size_t i = 0; i < other.size(); i++)
        insert_at(i, other.get_value_at(i));
}

template <typename T>
void LinkedList<T>::push_back(const T& value)
{
    auto new_node = std::make_shared<Node>(value);
    if (size() == 0)
        _head = new_node;
    else
    {
        auto tail = get_tail_node();
        tail->_next = new_node;
    }
}

template <typename T>
void LinkedList<T>::push_back(const LinkedList<T>& other)
{
    for (size_t i = 0; i < other.size(); i++)
        push_back(other.get_value_at(i));
}

template <typename T>
void LinkedList<T>::insert_at(size_t index, const T& value)
{
    if (index == 0)
    {
        push_front(value);
        return;
    }

    if (index == size())
    {
        push_back(value);
        return;
    }

    auto new_node = std::make_shared<Node>(value);
    auto insert_after_node = get_node_at(index - 1);
    auto insert_before_node = get_node_at(index);
    insert_after_node->_next = new_node;
    new_node->_next = insert_before_node;
}

template <typename T>
void LinkedList<T>::insert_at(size_t index, const LinkedList<T>& other)
{
    if (index == 0)
    {
        push_front(other);
        return;
    }

    if (index == size())
    {
        push_back(other);
        return;
    }

    for (size_t i = 0; i < other.size(); i++)
        insert_at(index + i, other.get_value_at(i));
}

template <typename T>
T LinkedList<T>::get_value_at(size_t index) const
{
    auto node = _head;
    for (size_t i = 0; i < index; i++)
        node = node->_next;
    return node->_value;
}

template <typename T>
size_t LinkedList<T>::size() const
{
    if (_head == nullptr)
        return 0;

    int size = 1;
    auto node = _head;
    while (node->_next != nullptr)
    {
        node = node->_next;
        size++;
    }
    return size;
}

template <typename T>
std::shared_ptr<typename LinkedList<T>::Node> LinkedList<T>::get_tail_node()
{
    assert(_head != nullptr);
    auto node = _head;
    while (node->_next != nullptr)
        node = node->_next;
    return node;
}

template <typename T>
std::shared_ptr<typename LinkedList<T>::Node> LinkedList<T>::get_node_at(size_t index)
{
    assert(_head != nullptr);
    assert(size() > index);
    auto node = _head;
    for (size_t i = 0; i < index; i++)
        node = node->_next;
    return node;
}

And here are my unit tests:

#include <boost/test/unit_test.hpp>
#include "LinkedList.h"

BOOST_AUTO_TEST_SUITE(Unit_Test_Suite)

// Also covers get_value_at().
BOOST_AUTO_TEST_CASE(Test_push_front)
{
    LinkedList<int> int_list;
    BOOST_CHECK(int_list.size() == 0);

    int_list.push_front(1);
    BOOST_CHECK(int_list.size() == 1);
    BOOST_CHECK(int_list.get_value_at(0) == 1);

    int_list.push_front(2);
    BOOST_CHECK(int_list.size() == 2);
    BOOST_CHECK(int_list.get_value_at(0) == 2);
    BOOST_CHECK(int_list.get_value_at(1) == 1);

    int_list.push_front(3);
    BOOST_CHECK(int_list.size() == 3);
    BOOST_CHECK(int_list.get_value_at(0) == 3);
    BOOST_CHECK(int_list.get_value_at(1) == 2);
    BOOST_CHECK(int_list.get_value_at(2) == 1);
}

BOOST_AUTO_TEST_CASE(Test_push_back)
{
    LinkedList<int> int_list;

    int_list.push_back(1);
    BOOST_CHECK(int_list.size() == 1);
    BOOST_CHECK(int_list.get_value_at(0) == 1);

    int_list.push_back(2);
    BOOST_CHECK(int_list.size() == 2);
    BOOST_CHECK(int_list.get_value_at(0) == 1);
    BOOST_CHECK(int_list.get_value_at(1) == 2);

    int_list.push_back(3);
    BOOST_CHECK(int_list.size() == 3);
    BOOST_CHECK(int_list.get_value_at(0) == 1);
    BOOST_CHECK(int_list.get_value_at(1) == 2);
    BOOST_CHECK(int_list.get_value_at(2) == 3);
}

BOOST_AUTO_TEST_CASE(Test_insert_at_head)
{
    LinkedList<int> int_list;
    int_list.push_back(1);
    int_list.push_back(2);
    int_list.push_back(3);

    // Insert at the head of the list (list before is "1 2 3", after is "0 1 2 3").
    int_list.insert_at(0, 0);
    BOOST_CHECK(int_list.size() == 4);
    BOOST_CHECK(int_list.get_value_at(0) == 0);
    BOOST_CHECK(int_list.get_value_at(1) == 1);
}

BOOST_AUTO_TEST_CASE(Test_insert_at_middle)
{
    LinkedList<int> int_list;
    int_list.push_back(1);
    int_list.push_back(2);
    int_list.push_back(3);

    // Insert at the head of the list (list before is "1 2 3", after is "1 0 2 3").
    int_list.insert_at(1, 0);
    BOOST_CHECK(int_list.size() == 4);
    BOOST_CHECK(int_list.get_value_at(0) == 1);
    BOOST_CHECK(int_list.get_value_at(1) == 0);
    BOOST_CHECK(int_list.get_value_at(2) == 2);
}

BOOST_AUTO_TEST_CASE(Test_insert_at_one_before_tail)
{
    LinkedList<int> int_list;
    int_list.push_back(1);
    int_list.push_back(2);
    int_list.push_back(3);

    // Insert at the head of the list (list before is "1 2 3", after is "1 2 0 3").
    int_list.insert_at(2, 0);
    BOOST_CHECK(int_list.size() == 4);
    BOOST_CHECK(int_list.get_value_at(1) == 2);
    BOOST_CHECK(int_list.get_value_at(2) == 0);
    BOOST_CHECK(int_list.get_value_at(3) == 3);
}

BOOST_AUTO_TEST_CASE(Test_insert_at_tail)
{
    LinkedList<int> int_list;
    int_list.push_back(1);
    int_list.push_back(2);
    int_list.push_back(3);

    // Insert at the head of the list (list before is "1 2 3", after is "1 2 3 0").
    int_list.insert_at(3, 0);
    BOOST_CHECK(int_list.size() == 4);
    BOOST_CHECK(int_list.get_value_at(2) == 3);
    BOOST_CHECK(int_list.get_value_at(3) == 0);
}

BOOST_AUTO_TEST_CASE(Testp_push_front_another_list)
{
    LinkedList<int> dest;
    dest.push_back(1);
    dest.push_back(2);
    dest.push_back(3);
    LinkedList<int> source;
    source.push_back(7);
    source.push_back(8);
    source.push_back(9);
    dest.push_front(source);

    BOOST_CHECK(dest.size() == 6);
    BOOST_CHECK(dest.get_value_at(0) == 7);
    BOOST_CHECK(dest.get_value_at(1) == 8);
    BOOST_CHECK(dest.get_value_at(2) == 9);
    BOOST_CHECK(dest.get_value_at(3) == 1);
}

BOOST_AUTO_TEST_CASE(Testp_push_back_another_list)
{
    LinkedList<int> dest;
    dest.push_back(1);
    dest.push_back(2);
    dest.push_back(3);
    LinkedList<int> source;
    source.push_back(7);
    source.push_back(8);
    source.push_back(9);
    dest.push_back(source);

    BOOST_CHECK(dest.size() == 6);
    BOOST_CHECK(dest.get_value_at(2) == 3);
    BOOST_CHECK(dest.get_value_at(3) == 7);
    BOOST_CHECK(dest.get_value_at(4) == 8);
    BOOST_CHECK(dest.get_value_at(5) == 9);
}

BOOST_AUTO_TEST_CASE(Test_insert_another_list_at_head)
{
    LinkedList<int> dest;
    dest.push_back(1);
    dest.push_back(2);
    dest.push_back(3);
    LinkedList<int> source;
    source.push_back(7);
    source.push_back(8);
    source.push_back(9);
    dest.insert_at(0, source);

    BOOST_CHECK(dest.size() == 6);
    BOOST_CHECK(dest.get_value_at(0) == 7);
    BOOST_CHECK(dest.get_value_at(1) == 8);
    BOOST_CHECK(dest.get_value_at(2) == 9);
    BOOST_CHECK(dest.get_value_at(3) == 1);
}

BOOST_AUTO_TEST_CASE(Test_insert_another_list_at_position)
{
    LinkedList<int> dest;
    dest.push_back(1);
    dest.push_back(2);
    dest.push_back(3);
    LinkedList<int> source;
    source.push_back(7);
    source.push_back(8);
    source.push_back(9);
    dest.insert_at(1, source);

    BOOST_CHECK(dest.size() == 6);
    BOOST_CHECK(dest.get_value_at(0) == 1);
    BOOST_CHECK(dest.get_value_at(1) == 7);
    BOOST_CHECK(dest.get_value_at(2) == 8);
    BOOST_CHECK(dest.get_value_at(3) == 9);
    BOOST_CHECK(dest.get_value_at(4) == 2);
}

BOOST_AUTO_TEST_CASE(Test_insert_another_list_at_tail)
{
    LinkedList<int> dest;
    dest.push_back(1);
    dest.push_back(2);
    dest.push_back(3);
    LinkedList<int> source;
    source.push_back(7);
    source.push_back(8);
    source.push_back(9);
    dest.insert_at(3, source);

    BOOST_CHECK(dest.size() == 6);
    BOOST_CHECK(dest.get_value_at(2) == 3);
    BOOST_CHECK(dest.get_value_at(3) == 7);
    BOOST_CHECK(dest.get_value_at(4) == 8);
    BOOST_CHECK(dest.get_value_at(5) == 9);
}

BOOST_AUTO_TEST_SUITE_END()
\$\endgroup\$
5
\$\begingroup\$

There's a few design issues with your code I think.

Copying

Copying your LinkedList performs a shallow copy. I think that would be counter-intuitive to anybody using your data structure. Typically in C++, copies are deep copies. On the one hand, using shared_ptr<Node> means you don't have to write any of the special member functions, so well done there (although you wrote the default constructor? Unnecessary, use =default). But now you're missing functionality.

Also on the copying front, you're enforcing that T is copy-assignable. Why? There is nothing inherent in LinkedList that requires this. You're artificially constraining the usability of your container. Don't.

Ultimately, I would use raw pointers (yep!) in both places where you have shared_ptr, and write out all the special member functions.

Perfect Forwarding

The reason that you required copy-assignment is because you wrote Node this way:

struct Node
{
    Node(const T& value) : _value{ value }, _next{ nullptr } {};
    T _value;
    std::shared_ptr<Node> _next;
};

But you should really write Node this way:

struct Node
{
    template <typename... Args>
    Node(Args&&... args) 
    : _value(std::forward<Args>(args)...)
    , _next(nullptr)
    { }

    ~Node()
    {
        delete _next;
    }

    // because you will never need to do this
    // let's be explicit
    Node(const Node&) = delete;
    Node(Node&& ) = delete;
    Node& operator=(const Node&) = delete;
    Node& operator=(Node&&) = delete;

    T _value;
    Node* _next; // you're not sharing Nodes...
};

This will let you then implement other very useful functions like emplace_back and emplace_front.

Indexing

You have these three member functions:

void insert_at(size_t index, const T& value);
void insert_at(size_t index, const LinkedList<T>& other);
T get_value_at(size_t index) const;

But it's a LinkedList. Indexing is inefficient. These functions should probably not be part of the interface at all. If somebody wants to do something like this, they can do it external to your class, which brings me to...

Access

The typical way to write containers in C++ is to provide iterators into them. For LinkedList, an iterator is basically a very light wrapper around Node. You'll need to add begin() and end() member functions, and you should add an insert() that takes an iterator to insert behind.

Erase

I notice you're missing erase(). That's a useful function! Also pop and clear(). Potentially splice().

Miscellaneous

In push_back, you have:

if (size() == 0)

Why do you need to walk the whole list to check if your list is empty? That reminds me, you should add empty(). But secondly, you have access to your private data. When is size() == 0? When !_head. That's a much faster check. When your size() is O(N), be very wary of using it. I would try to use it... never.

\$\endgroup\$
  • \$\begingroup\$ Thank you for the feedback. I'll need time to process all of this. The reason I don't have some of the functionality you mentioned was because I wanted to get some feedback before fully implementing everything... So I could use some best practices rather than best guess practices :) \$\endgroup\$ – Steve Jul 11 '15 at 21:44
3
\$\begingroup\$

I am ignoring your request to ignore performance. Algorithmic complexity matters! Though micro-optimizations such as avoiding templates in the internals can be ignored.

@Barry said most of what I thought, and I would reemphasize to simply not supply any operation (such as .size()) that cannot be performed efficiently. Note that C++11 (doubly-linked) std::list.size() is required to be \$O(1)\$ but this is widely considered to be a mistake since it disallows certain forms of splicing. Singly-linked std::forward_list.size(), being newer, avoids this design flaw.

It is quite easy to implement an \$O(1)\$ push_back (but not pop_back), simply by adding a (non-owning) Node *_tail member and keeping it updated. You probably want to implement "insert before iterator" first though. (Yes, it has to be before (think about begin() and end()), which has major implications for what an iterator looks like!). Also implement "erase element pointed-to by this iterator"; it is significant that that operation returns an iterator, not void.

\$\endgroup\$
2
\$\begingroup\$

I would like to give some feedback on your unit-tests.

First, and most important, I congratulate you to your choice to do this exercise together with unit-testing!

Now some ideas that you might find valuable. Looking at your test function Test_push_front, it contains the following individual tests:

  1. After construction the list is empty.
  2. Pushing to the front of an empty list results in a list of that one element.
  3. Two more tests about pushing to the front of a non-empty list.

The first test is certainly a good test, but one that has nothing to do with push_front and therefore should not be put into a function with a name that indicates to test push_front. A better choice would be a separate test function for this test.

The other tests within Test_push_front all deal with push_front. However, it is considered a good testing practice to implement tests such that each test only tests one single aspect. If you have such 'atomic' tests which are independent of each other, then, in case of a bug, the pattern of passing and failing tests will make it easier to quickly identify the problem. Otherwise, as in your case, the combination of several tests within one test function makes these tests dependent on each other, such that a failure in one of them (which can, btw., also be a bug in the test code) will make the latter ones fail as well.

Once you split your test functions such that each of them only contains one test, you can better apply the following improvements:

For one thing, you can then make better use of some recommended naming conventions for tests, for example the convention to name tests as <method-called>_<scenario>_<expected-result>. Such naming conventions make it easy to understand what went wrong just from the output of the test runner. For Test_push_front, the respective new test functions could be named:

  • 'defaultConstructor_whenSuccessful_listHasZeroElements'
  • 'pushFront_valueXtoEmptyList_listWithOneElementX'
  • 'pushFront_valueXtoListWithFrontY_listIsLongerByOneAndStartsWithXY'

Another benefit from testing only one aspect per test function is, that each test function can then be structured according to the pattern 'setup,exercise,verify,teardown' (four phase test, SEVT), which makes it easier to understand the test code. Note that there is also the AAA pattern (arrange, act, assert), which just gives different names to the first three phases but leaves out the teardown part.

As a further observation regarding the function Test_push_front, the last two tests basically cover the case that an element is pushed to the front of a non-empty list. To me it seems that one of these two tests would be sufficient, because I can't think of a bug that the extra test case might find. This may just because of my lack of phantasy, and thus I only mention it to convey this as a rule of thumb: If you are unsure whether you need more tests, ask yourself if they could really catch more bugs.

In any case, there is one final note about the last test in Test_push_front: The test checks whether the new element is pushed correctly to the front. You are, however, checking the whole list content rather than only the front element (and, possibly, the second element). It seems to be a good idea just to test everything that could be tested. The problem is that it leads to additional maintenance effort for your test code, and can also lead to 'overspecified tests', that is, tests that become fragile because they test too much detail.

I hope you find some of these hints helpful - there are some very good books and online resources available that much better explain the best practices for writing unit-tests, for example from Gerard Meszaros, Roy Osherove and Michael Feathers, just to name a few.

\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! Good job on your first answer. \$\endgroup\$ – SirPython Feb 11 '16 at 1:48
  • \$\begingroup\$ I had forgotten about this. Your answer has a good many takeaways! I appreciate the time you put into this answer. \$\endgroup\$ – Steve Feb 11 '16 at 2:56

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.