Unit testing with a singly linked list

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

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

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

public:
LinkedList();

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

T get_value_at(size_t index) const;

size_t size() const;

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 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 _next;
};

But you should really write Node this way:

struct Node
{
    template 
    Node(Args&&... args) 
    : _value(std::forward(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& 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.

StackExchange Code Review Q#96555, answer score: 6