Simple Single Linked List

Question

I'm currently studying data structures, I have implemented simple single linked list as shown below.

I would like to know how can I improve it?

#include <iostream>
#include <memory>
#include <cassert>
template <typename T>
class List 
{
 struct node 
 {
 T value;
 std::unique_ptr<node> next;
 };
public:
 List();
 void add(T value);
 T first() const;
 T value(std::size_t position) const;
 std::size_t length() const;
 void clear();
private:
 std::unique_ptr<node> mFirst;
 std::size_t mLength;
};
template <class T>
List<T>::List()
 : mFirst(nullptr)
 , mLength()
{
}
template <typename T>
std::size_t List<T>::length() const
{
 return mLength;
}
template <typename T>
T List<T>::first() const
{
 assert(mFirst != nullptr);
 return mFirst->value;
}
template <typename T>
void List<T>::add(T value)
{
 auto next = std::move(mFirst);
 mFirst = std::make_unique<node>();
 mFirst->value = value;
 mFirst->next = std::move(next);
 mLength++;
}
template <class T>
T List<T>::value(std::size_t position) const
{
 assert(mFirst != nullptr);
 auto current = mFirst.get();
 for (auto i = 0u; i < position; ++i)
 {
 current = current->next.get();
 }
 return current->value;
}
template <class T>
void List<T>::clear()
{
 assert(mFirst != nullptr);
 auto length = mLength;
 for (auto i = 0u; i < length; ++i)
 {
 mFirst = std::move(mFirst->next);
 mLength--;
 }
}
int main()
{
 List<int> list;
 for (int i = 0; i < 10; ++i)
 list.add(i);
 for (auto i = 0u; i < list.length(); ++i)
 std::cout << list.value(i) << ' ';
 list.clear();
 std::cout << "\n\n" << list.length() << "\n\n";
}

• Daniel Kamil Kozar: Small suggestion : using class T is not an error by itself, but what you really mean here is typename T. This way, you do not enforce that T needs to be a class - it just has to be a type. I haven't heard of any compilers that would give you hell if you tried to use int in place of a class T, but still. And kudos for using size_t!
• Jerry Coffin: @DanielKamilKozar: template <class T> and template <typename T> mean precisely the same things to any conforming compiler. In this case, class does not mean that the type needs to be an actual class. Some people like to use typename here to indicate that any type can be passed--and that's fine, but unnecessary and irrelevant to the compiler.
• Daniel Kamil Kozar: @JerryCoffin : and here was I thinking that there is some kind of a difference. Thanks.

Answer 1

Choice of Members

You currently keep a head pointer and a length. The result of this is that add is a linear operation. It would be much better to additionaly keep a tail pointer, so that add is constant time.

Since linked lists do not support random access, it's questionable to have a method like T value(size_t ). If you need to index into a container, you probably don't want to use a linked list. Better to not provide it.

Unfortunately, this is your only way to get anything other than the first value - which makes iteration take quadratic time! What you need to do is to do as the standard library do and add something like:

struct iterator {
 // basically a wrapper around node* that works as a ForwardIterator
};
iterator begin() { return iterator{mFirst.get()}; }
iterator end() { return iterator{mLast}; }

This will additionally allow everybody to use the standard library algorithms with your class. You will want a const_iterator as well, to allow for iteration over a const List<T>.

Use References

Right now add() takes a T and first() returns a T. For something like int, the former is OK, but the latter is still questionable. What if you want to modify the list elements? That seems like a useful operation. To that end, you should add:

void add(T const& );
void add(T&& );
T& first();
T const& first();

You may also want to add an emplace, to construct values in-place:

template <typename... Args>
void emplace(Args&&...);

You may want to rename first to front for convention. Similarly length to size.

Clearing

Since you are using smart pointers for your list, clearing is very simple. You don't need a loop at all:

template <class T>
void List<T>::clear()
{
 mFirst.clear();
 mLast = nullptr;
 mLength = 0;
}

• Deduplicator: Yes, clearing is that simple. But doing it that way is still substandard, because there's no reason to use recursion and thus more stack-space and time.
• Barry: @Deduplicator That's a good point

Answer 2

Well, there's already a good review by Barry, but I'll take a different tack:

1. In general, it's a good idea to use existing types (like smart-pointers) as building-blocks.
   Still, you should not deform your code, causing loss of efficiency or clarity, just so you can use one, especially not in library-code (and such a basic container is that).

   So, no smart-pointers for you, sometimes one really should get down to it.

2. As an aside, your clear has a bug: It tries to assign the deleter after already having deleted the source. See std::unique_ptr::operator=(std::unique_ptr&&).

3. There's a reason a node is generally a wholly-owned passive and dumb aggregate without any behavior: It would just get in the way of the List defining it properly.

4. You should use the same names for members all the containers in the standard-library use, so you can use standard algorithms.

5. For that same reason, and so you can efficiently iterate over all elements, you should provide iterators.

6. Sacrificing some space in the class itself for a size can be a reaonable idea. Similar arguments can be made for including a pointer (node**) to the end, so you can speed up push_back/emplace_back.

7. Consider putting the next-pointer first, that might allow the compiler to merge code for different template-arguments more often.

---

This is how you clear a list:

void List::clear() {
 for(node *head = this->head, *temp; head; head = temp) {
 temp = head->next;
 delete head;
 }
 this->head = nullptr;
}

• Zulan: I have to disagree on the rejection of smartpointers. IMHO this is a good use of smart pointers. I do not see how their use in this example negatively impacts clarity or performance. I see no reason not to use zero-overhead stl primitives in library code. Consider that for instance std::stack also builds on other stl containers.
• Deduplicator: @Zulan: Using a smart-pointer here make List::clear less efficient. Especially, it means that it uses recursion, and thus O(n) space instead of O(1) space, or at least it gets more complicated and a constant factor slower.
• Zulan: That is plain wrong. MORTALs initial List::clear does not use recursion, as you correctly commented in the other answer. A well implemented clear with unique_ptr produces exactly the same assembler code and is shorter (see gist.github.com/Zulan/1d80b795afb357e94b73)
• Deduplicator: @Zulan: Yes, it's just Undefined Behavior, so much better: mFirst = std::move(mFirst->next); en.cppreference.com/w/cpp/memory/unique_ptr/operator%3D What you are also consistently ignoring is that that's basic library-code, so even a constant factor matters, if you can reasonably help it.
• Zulan: The constant factor is 1 [both in terms of speed and size, for my compiler with default options]. The quoted line is problematic, and should be fixed. But IMHO that doesn't warrant rejecting smart pointers. If you really wanted to, you could make a point about compilation speed and -O0 speed.