Doubly linked std::list simple implementation

Question

I've implemented a simple doubly linked list structure. I would appreciate all criticism relevant to code, style, flow, and so forth.

How to implement end iterator and pop_back/pop_front properly? Where memory may leak?

P.S.I didn't make it template, because this is simple version version.

#include <cstddef>
#include <iterator>
using T = int;
class List {
/// Nodes
public:
 class Node {
 public:
 T data;
 Node *next;
 Node *prev;
 public:
 explicit Node(Node *next_, Node *prev_) : next(next_), prev(prev_) {}
 explicit Node(const T &_data, Node *next_, Node *prev_) :
 data(_data), next(next_), prev(prev_) {}
 ~Node() {}
 };
///
/// Iterators
public:
 class Iterator : public std::iterator<std::bidirectional_iterator_tag, T> {
 public:
 Node *position;
 Node *tail;
 public:
 Iterator(Node *node) : position(node) {}
 Iterator(Node *node, Node *_tail) : position(node), tail(_tail) {
 }
 Iterator &operator++() noexcept {
 position = position->next;
 return *this;
 }
 Iterator operator++(int) noexcept {
 auto old = *this;
 position = position->next;
 return old;
 }
 Iterator &operator--() noexcept {
 if (position == nullptr) position = tail;
 else
 position = position->prev;
 return *this;
 }
 Iterator operator--(int) noexcept {
 auto old = *this;
 if (position == nullptr) position = tail;
 else
 position = position->prev;
 return old;
 }
 T &operator*() const noexcept {
 return (position->data);
 }
 bool operator!=(Iterator other) noexcept {
 return position != other.position;
 }
 bool operator==(Iterator other) noexcept {
 return position == other.position;
 }
 ~Iterator() {}
 };
///
/// list
private:
 Node *head = nullptr;
 Node *tail = nullptr;
 size_t size_ = 0;
public:
 List() {}
 void push_back(const T &_data) {
 Node *node = new Node(_data, nullptr, tail);
 if (tail != nullptr) {
 node->prev = tail;
 tail->next = node;
 tail = node;
 } else {
 head = tail = node;
 }
 ++size_;
 }
 void push_front(const T &_data) {
 Node *node = new Node(_data, head, nullptr);
 if (head != nullptr) {
 head->prev = node;
 node->next = head;
 head = node;
 } else {
 head = tail = node;
 }
 ++size_;
 }
 void pop_back() {
 tail = tail->prev;
 if (tail != nullptr) {
 tail->next = nullptr;
 }
 --size_;
 }
 void pop_front() {
 head = head->next;
 if (head != nullptr) {
 head->prev = nullptr;
 }
 --size_;
 }
 size_t size() {
 return size_;
 }
 size_t size() const {
 return size_;
 }
 Iterator begin() {
 return Iterator(head, tail);
 }
 Iterator begin() const {
 return Iterator(head, tail);
 }
 Iterator end() {
 Iterator iter(nullptr, tail);
 return iter;
 }
 Iterator end() const {
 Iterator iter(nullptr, tail);
 return iter;
 }
 bool empty() const {
 return head == nullptr;
 }
 ~List() {
 Node * tmp = nullptr;
 while (head)
 {
 tmp = head;
 head = head->next;
 delete tmp;
 }
 head = tail = nullptr;
 }
};

• Deduplicator: pop_front() leaks.
• πάντα ῥεῖ: @Alexander In fact I think there are more than one possible cases your code is prone for leaking, hence I proposed using smart pointers.
• Deduplicator: every case, just like pop_back()
• Incomputable: @Alexander, C++ doesn't have garbage collection. Assigning nullptr won't release the memory. You need to call delete. Current code looks like freelist, not a list.
• Incomputable: @Alexander, pop_xxx need to delete as well, otherwise you're leaking memory. When you assign nullptr to non deleted chunk of memory, you're basically saying "lets waste memory". I believe I gave enough information, good luck.

Answer 1

My favorite container the list. Even doubly linked to make it more fun.

Issues in your current code.

You don't implement the rule of three/five.

Any class that manages resources needs to correctly implement the rule of three (optionally the rule of five). Otherwise you will have issues because of the compiler generated methods.

If you do not define them the compiler will generate the following methods:

• Default Constructor
• Copy Constructor
• Copy Assignment operator

Under some situations it will also generate

• Move Constructor
• Move Assignment operator

Because of the default implementation of these methods a class that "Owns" a pointer will not work as you expect. Note: Owns means that the destructor will delete it. But the general rule is if you define the destructor or any of the above operators you must define them all.

If we look at your current implementation:

{
 List data; // List one
 data.push_back(5);
 List data2(data); // This is not a copy of data.
 // Internally this has the same pointers
 // as data.
}
// Here you get a double delete
// Both destructors will delete the same pointer.

There are simple implementations for most of these.

List& operator=(List const& rhs)
{
 List copy(rhs); // use the copy and swap idiom
 copy.swap(*this);
 return *this;
}
List(List&& rhs) noexcept
 : head(nullptr)
 , tail(nullptr)
 , size_(0)
{
 rhs.swap(*this); // Move construct: Simply swap the data
}
List& operator=(List&& rhs) noexcept
{
 rhs.swap(*this); // Move assignment: Simply swap the data
 return *this; // the return.
}
void swap(List& other) noexcept
{
 using std::swap;
 swap(head, other.head);
 swap(tail, other.tail);
 swap(size_, other.size_);
}
// The only one that is hard is the copy constructor.
List(List const& rhs)
 : head(nullptr)
 , tail(nullptr)
 , size_(0)
{
 // But since you have iterators defined.
 // that makes it relatively easy.
 for(T const& value: rhs) {
 push_back(value);
 }
}
 

Your implementation is fine. But there is another technique. If you list is circular (head joined to tail) and you add a sentinel node (a marker node at the head/tail that is always there). Then the actual implementation becomes a lot easier because there is no longer any need to check for null (because there is always a sentinel).

void push_back(const T &_data)
{
 new Node(_data, sent, sent->prev);
 ++size_;
}
void push_front(const T &_data)
{
 new Node(_data, sent->next, sent);
 ++size_;
}
Node::Node(T const& data, Node* next, Node* prev)
 : data(data)
 , next(next)
 , prev(prev)
{
 prev->next = this;
 next->prev = this;
}
void pop_back()
{
 if (size > 0) {
 delete sent->prev;
 --size_;
 }
}
void pop_front()
{
 if (size > 0) {
 delete sent->next;
 --size_;
 }
}
Node::~Node()
{
 prev->next = next;
 next->prev = prev;
}

Next you always copy the objects into the list. That's fine but you should also think about moving objects into the list and emplacing them (building them in place).

void push_back(T const& copy); // You have this.
void push_back(T&& move); // Move into the list
template<typename... Args>
void emplace_back(Args...&& args); // Build in-place

You don't need two version of size.

// This version is not necessary.
// The const version will work in all situations.
size_t size() { 
 return size_;
}
size_t size() const {
 return size_;
}

Youre const methods for getting iterators does not return the correct type.

Iterator begin() const {
 return Iterator(head, tail);
}
Iterator end() const {
 Iterator iter(nullptr, tail);
 return iter;
}

Technically you can still use the iterators returned to modify the object. So these should not really callable from a const version of the object. From the const version of begin() and end you should return a const version of the iterator that allows you to read the container but not write to it.

While we are on iterators you should also add cbegin() and cend() that always return const iterators.

• Alexander: It is a very good approach, but how implement end iterator there?
• Loki Astari: @Alexander. The end iterator just points at the sentinel.
• Alexander: but what is sentinel?
• Incomputable: @Alexander, it is a technique from old times. It's not a surprise that you and me haven't seen it widely used. Sentinel has a wiki page, which I believe explains in a comprehensive way. Basically it is a special value that can't be in a sequence and signals that the sequence ended.
• Loki Astari: @Alexander: I have written a lot of reviews on Doubly linked list. Here is another review in which I also provide an implementation with a sentinel: codereview.stackexchange.com/a/126007/507 (scroll to the bottom)

Answer 2

Take care to be explicit about compiler generated functions

Effectively your List class violates the Rule of Three/Five/Zero, thus the compiler generated copy/move constructors will create unexpected side effects by implementing a shallow copy mechanism.

Let's suppose you have code like

int main() {
 List l1;
 List l2;
 l1.push_back(5);
 l1.push_back(42);
 l1.push_back(21);
 l2 = l1; // Copy the list
 *l1.begin() = 80; // Change the original list
 for(auto value : l2) {
 std::cout << value << std::endl;
 }
}

The output is

80
42
21

I doubt you really intended that. See the Live Demo please.

Why not making your class a template?

using T = int;

looks strange.

Why not making the List class a template like

template<typename T>
class List {
 // ...
};

Compiles and works the same way here

Prefer smart pointers instead of raw pointers

You should prefer using smart pointers instead of managing new and delete yourself.

I have evolved the demo from above with changing the relevant parts

class Node;
class Node {
public:
 T data;
 std::shared_ptr<Node> next;
 std::shared_ptr<Node> prev;
public:
 explicit Node(std::shared_ptr<Node> next_, std::shared_ptr<Node> prev_) : next(next_), prev(prev_) {}
 explicit Node(const T &_data, std::shared_ptr<Node> next_, std::shared_ptr<Node> prev_) :
 data(_data), next(next_), prev(prev_) {}
 ~Node() {}
};

---

class Iterator : public std::iterator<std::bidirectional_iterator_tag, T> {
public:
 std::weak_ptr<Node> position;
 std::weak_ptr<Node> tail;
public:
 Iterator(std::shared_ptr<Node> node) : position(node) {}
 Iterator(std::shared_ptr<Node>node, std::shared_ptr<Node>_tail) : position(node), tail(_tail) {
 }
 Iterator &operator++() noexcept {
 position = position.lock()->next;
 return *this;
 }
 Iterator operator++(int) noexcept {
 auto old = *this;
 position = position->next;
 return old;
 }
 Iterator &operator--() noexcept {
 if (position == nullptr) position = tail;
 else
 position = position->prev;
 return *this;
 }
 Iterator operator--(int) noexcept {
 auto old = *this;
 if (position == nullptr) position = tail;
 else
 position = position->prev;
 return old;
 }
 T &operator*() const noexcept {
 return (position.lock()->data);
 }
 bool operator!=(Iterator other) noexcept {
 return position.lock().get() != other.position.lock().get();
 }
 bool operator==(Iterator other) noexcept {
 return position.lock().get() == other.position.lock().get();
 }
 ~Iterator() {}
};

Solve the shallow copy problem

As mentioned in my 1st point you have a problem with The Rule of Three/Five. Your List class will be shallow copied. So you should provide the relevant operations.
This will be a lot easier using smart pointers as mentioned in my previous point

List(const List<T>& rhs) {
 copy(rhs);
}
List(List<T>&& rhs) {
 move(std::move(rhs));
}
List& operator=(const List<T>& rhs) {
 copy(rhs);
 return *this;
}
List& operator=(List<T>&& rhs) {
 move(std::move(rhs));
 return *this;
}
void copy(const List<T>& rhs) {
 clear();
 for(auto value : rhs) {
 push_back(value);
 }
}
void move(List<T>&& rhs) {
 head = std::move(rhs.head);
 tail = std::move(rhs.tail);
}
void clear() {
 std::shared_ptr<Node> temp = head;
 std::shared_ptr<Node> next;
 do {
 if(temp) {
 next = temp->next;
 }
 temp = nullptr;
 } while(next);
}
~List() {
}

Output is as expected for the example mentioned in the 1st paragraph:

5
42
21

Again you can check the improved code here.

• Alexander: I didn't want to think about exceptions. So, it is the reason why i didn't make it template.
• Alexander: The work with smart pointers is really good way? Smart pointers is expensive.
• πάντα ῥεῖ: @Alexander I added another section related to the use of smart pointers. And no, there's not really much overhead using smart pointers or managing new and delete yourself poperly.
• Incomputable: @Alexander, I believe I've seen a presentation where std::unique_ptr<> totally compiled away, i.e. it is the same as if manual new and delete were used. It might have overhead in more complex cases, but I don't think that overhead will overcome the overhead from data being scattered all around. About shared_ptr<>, I don't think it will be a problem unless you're running something like at the scale of Facebook data centers.
• Loki Astari: @πάνταῥεῖ Your move is going to copy. Remember named values can not be r-value references so will not bind to &&. So this line move(rhs); is not doing what you think, which is why you have have a const in this declaration void move(const List<T>&& rhs). Whcih means you don't reset the source and thus code is broken and you still get a double delete. Your call to move should have been move(std::move(rhs)); Then you can swap the pointers.