Unit testing with a singly linked list

Question

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:

Write the LinkedList.h header file to define the implementation.
Write the unit tests to test the methods declared in the class.
Write the implementation of the LinkedList class methods, in order to get the previously written unit tests to pass.
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()

Barry · Answer 1 · 2015-07-11 19:48:36Z

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.

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 :) — Steve, Jul 11 at 21:44

o11c · Answer 2 · 2015-07-11 20:04:33Z

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.

asked	1 month ago
viewed	71 times
active	1 month ago

current community

your communities

more stack exchange communities

Unit testing with a singly linked list

2 Answers 2

Your Answer

Not the answer you're looking for? Browse other questions tagged c++ c++11 unit-testing linked-list boost or ask your own question.

Hot Network Questions

current community

your communities

more stack exchange communities

Unit testing with a singly linked list

2 Answers 2

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged c++ c++11 unit-testing linked-list boost or ask your own question.

Related

Hot Network Questions