HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMinor

Simple Single Linked List

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
listsimplelinkedsingle

Problem

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 
#include 
#include 

template 
class List 
{
    struct node 
    {
        T value;
        std::unique_ptr 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   mFirst;
    std::size_t             mLength;
};

template 
List::List()
    : mFirst(nullptr)
    , mLength()
{
}

template 
std::size_t List::length() const
{
    return mLength;
}

template 
T List::first() const
{
    assert(mFirst != nullptr);
    return mFirst->value;
}

template 
void List::add(T value)
{
    auto next = std::move(mFirst);
    mFirst = std::make_unique();
    mFirst->value = value;
    mFirst->next = std::move(next);
    mLength++;
}

template 
T List::value(std::size_t position) const
{
    assert(mFirst != nullptr);

    auto current = mFirst.get();

    for (auto i = 0u; i next.get();
    }
    return current->value;
}

template 
void List::clear()
{
    assert(mFirst != nullptr);

    auto length = mLength;

    for (auto i = 0u; i next);
        mLength--;
    }
}

int main()
{
    List 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";
}

Solution

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

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

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

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

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

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

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

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

Code Snippets

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

Context

StackExchange Code Review Q#109280, answer score: 4

Revisions (0)

No revisions yet.