In order to learn C++11, I propose to myself implement a simple single linked list using smart pointers. The idea was to cover the basic operations without leave any memory leak.
I came up with a solution but I'm sure that it could be improved in many ways. So, I would like to receive feedback of any kind: format, readability, implementation, etc.
Also, I would like to hear your opinion about which is the correct way of iterate over a sequence of objects using smart pointers. After reading and looking for examples, I believe that it should be done using the get method (from the smart pointer) to obtain a raw pointer, which can be used to go through the sequence. Is there another way of doing it?.
And finally, what else could I add to the class or what do you think that is missing that I should add? I will use the answer for this question as an opportunity to keep improving/learning, so every answer is welcome.
#ifndef LINKED_LIST_H
#define LINKED_LIST_H
#include <iostream>
#include <memory>
template <typename T>
class LinkedList
{
private:
/* Node definition */
class Node
{
friend class LinkedList<T>;
private:
const T key_;
std::unique_ptr<Node> next_;
public:
Node(const T k): key_{k}, next_{nullptr} {}
~Node() = default;
// Commented lines: just for debuging purposes.
// Node(const T k): key_{k}, next_{nullptr} { std::cout << "[DEBUG] Node created! (" << key_ << ")" << std::endl; }
// ~Node(){ std::cout << "[DEBUG] Node destroyed! (" << key_ << ")" << std::endl; }
};
/* End node definition */
int size_;
std::unique_ptr<Node> head_;
public:
LinkedList() = default;
~LinkedList() = default;
//~LinkedList(){ std::cout << "[DEBUG] List destroyed!" << std::endl; }
// Returns the key of the node at the back of the list.
T back();
// Returns the key of the node at index position.
T at(unsigned int index);
// Returns the key of the node at the front of the list.
T front();
// Check if the list is empty. Returns true or false.
bool is_empty() const;
// Removes the node of the back of the list and returns its key.
T pop_back();
// Removes the node of the front of the list and returns its key.
T pop_front();
// Returns and ostream with the keys of everynode (use with cout to print them all).
std::ostream & print(std::ostream &os);
// Insert a node at the front of the list.
void push_front(const T &key);
// Insert a node at the end of the list.
void push_back(const T &key);
};
template<typename T>
T LinkedList<T>::at(unsigned int index)
{
auto ptr = head_.get();
while (--index)
ptr = ptr->next_.get();
return ptr->key_;
}
template<typename T>
bool LinkedList<T>::is_empty() const
{
return head_ == nullptr;
}
template<typename T>
T LinkedList<T>::pop_back()
{
// This method does not handle the empty list case.
auto prev_ptr = head_.get();
auto curr_ptr = prev_ptr;
while (curr_ptr->next_)
{
prev_ptr = curr_ptr;
curr_ptr = curr_ptr->next_.get();
}
size_--;
if (prev_ptr == curr_ptr) // head_ points to the last item.
{
auto tmp = std::move(head_);
return tmp->key_;
}
else
{
auto tmp = std::move(prev_ptr->next_);
return tmp->key_;
}
}
template<typename T>
T LinkedList<T>::pop_front()
{
// This method does not handle the empty list case.
auto ptr = std::move(head_);
head_ = std::move(ptr->next_);
size_--;
return ptr->key_;
}
template<typename T>
void LinkedList<T>::push_back(const T &key)
{
if (!head_)
head_.reset(new Node(key));
else
{
auto ptr = head_.get();
while (ptr->next_)
ptr = ptr->next_.get();
ptr->next_.reset(new Node(key));
}
size_++;
}
template<typename T>
void LinkedList<T>::push_front(const T &key)
{
std::unique_ptr<Node> p(new Node(key));
p->next_ = std::move(head_);
head_ = std::move(p);
size_++;
}
template<typename T>
std::ostream & LinkedList<T>::print(std::ostream &os = std::cout)
{
auto current = head_.get();
while (current)
{
os << current->key_ << " ";
current = current->next_.get();
}
return os << std::endl;
}
#endif
Nodein there, or expose the fact that such things even exist. \$\endgroup\$