patterncppMinor
Simple Single Linked List
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?
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
-
There's a reason a
-
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
-
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:
-
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.