current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Sign up ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 5 down vote favorite
1

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";
}
share|improve this question
    
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! – Daniel Kamil Kozar yesterday
    
@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. – Jerry Coffin 23 hours ago
    
@JerryCoffin : and here was I thinking that there is some kind of a difference. Thanks. – Daniel Kamil Kozar 12 hours ago

2 Answers 2

up vote 3 down vote accepted

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;
}
share|improve this answer
1  
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. – Deduplicator yesterday
    
@Deduplicator That's a good point – Barry yesterday
up vote 4 down vote

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. 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.

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

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

  5. 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.

  6. 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;
}
share|improve this answer
    
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. – Zulan 5 hours ago
    
@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. – Deduplicator 1 hour ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.