Doubly linked list using C++ and templates

Question

Working doubly linked list using C++ and templates, I tried to make it by myself. I tried to use head and tail as buffers and make a simple implementation. Please help me understand what I have done wrong, done good and could have done worse.

#pragma once
#include <iostream>
template <typename T>
struct node
{
 T value;
 node* prev = nullptr;
 node* next = nullptr;
};
template <typename T>
class LList
{
public:
 LList<T>();
 ~LList();
 T& get(const int& pos) const;
 void insert(const T& value, const int& pos);
 T& remove(const int& pos);
private:
 int n_elements;
 node<T> *head = new node<T>;
 node<T> *tail = new node<T>;
};
template<typename T>
LList<T>::LList()
{
 n_elements = 0;
 head->next = tail;
 tail->prev = head;
}
template<typename T>
LList<T>::~LList()
{
}
template<typename T>
T& LList<T>::get(const int & pos) const
{
 node<T> *temp = head;
 for (int i = 0; i <= pos; i++)
 temp = temp->next;
 return temp->value;
}
template<typename T>
void LList<T>::insert(const T & value, const int & pos)
{
 node<T> *temp = new node<T>;
 temp->value = value;
 node<T> *prev = head;
 node<T> *next = head->next;
 for (int i = 0; i < pos; i++)
 {
 prev = prev->next;
 next = next->next;
 }
 prev->next = temp;
 next->prev = temp;
 temp->prev = prev;
 temp->next = next;
 ++n_elements;
}
template<typename T>
T & LList<T>::remove(const int & pos)
{
 node<T> *prev = head;
 node<T> *curr = head->next;
 node<T> *next = curr->next;
 for (int i = 0; i < pos; i++)
 {
 prev = prev->next;
 curr = curr->next;
 next = next->next;
 }
 prev->next = next;
 next->prev = prev;
 T value = curr->value;
 delete curr;
 --n_elements;
 return value;
}

---

#include <iostream>
#include "LList.h"
int main()
{
 LList <double> mylist;
 mylist.insert(20, 0);
 mylist.insert(30, 1);
 mylist.insert(40, 2);
 mylist.insert(30, 2);
 mylist.insert(10, 0);
 std::cout << "removing: " << mylist.remove(0) << std::endl;
 mylist.insert(10, 0);
 mylist.insert(10, 0);
 mylist.insert(10, 0);
 std::cout << "removing: " << mylist.remove(3) << std::endl;
 std::cout << "removing: " << mylist.remove(2) << std::endl;
 std::cout << "removing: " << mylist.remove(1) << std::endl;
 std::cout << mylist.get(0) << std::endl;
 std::cout << mylist.get(1) << std::endl;
 std::cout << mylist.get(2) << std::endl;
 std::cout << mylist.get(3) << std::endl;
 system("pause");
 return 0;
}

• Mast: Welcome to Code Review! Does the current code work the way you want it to?
• lucarlig: yes it does, there is no main function but seems obvious.
• Mast: If you have tests, it would be preferred you add those to your question.
• lucarlig: ok I added the main function with my little tests, everything seems to work properly

Answer 1

Includes

<iostream> isn't needed by the header, so don't include it there.

Null pointer

When I try to run the code, I get an attempt to dereference a null pointer at the first remove(0), which crashes the program. This is because remove() returns a reference to local variable value, which is no longer in scope. Return it by value instead:

 T remove(int pos);
 //^^^ not T&

Memory leak

If I add return 0; before the crash (or fix the bug), I do see a memory leak:

==29576== 168 (24 direct, 144 indirect) bytes in 1 blocks are definitely lost in loss record 7 of 7
==29576== at 0x4835E2F: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==29576== by 0x109362: LList<double>::LList() (205728.cpp:27)
==29576== by 0x10917F: main (205728.cpp:92)

I think ~LList() needs to do more cleanup:

template<typename T>
LList<T>::~LList()
{
 for (auto p = head->next; p != tail; ) {
 auto next = p->next;
 delete p;
 p = next;
 }
 delete head;
 delete tail;
}

Copy construction

205728.cpp:11:7: warning: ‘class LList<double>’ has pointer data members [-Weffc++]
205728.cpp:11:7: warning: but does not override ‘LList<double>(const LList<double>&)’ [-Weffc++]
205728.cpp:11:7: warning: or ‘operator=(const LList<double>&)’ [-Weffc++]

We need to fix this, and either make the list safely copyable, or totally uncopyable.

Prefer initialization to assignment

LList<T>::LList() : n_elements{0}
 /^^^^^^^^^^^^^

Or just provide a default initializer, as with prev and next.

Don't pass primitive types by reference

T& get(const int& pos) const;
// ^^^

Built-in types such as int are best passed by value rather than by const reference (and prefer size type to int for counting objects). Also, in this case, we probably want to return a reference to const T from a const list, and a reference to mutable T from a mutable list (do as the standard containers do):

T const& get(std::size_t pos) const;
T& get(std::size_t pos);

Copying

Prefer to std::move() values where possible. It's not hard to make the list able to accept move-only types:

template <typename T>
struct node
{
 T value;
 node* prev;
 node* next;
 node(T value, node *prev = nullptr, node *next = nullptr)
 : value{std::move(value)}, prev{prev}, next{next}
 {}
};

template<typename T>
void LList<T>::insert(T value, const int pos)
{
 node<T> *temp = new node<T>(std::move(value), prev, next);

Exception safety

Constructing a linked list requires memory to be allocated for head and tail. If the first new succeeds, but the second fails, we end up leaking memory when the std::bad_alloc is thrown.

There's no reason not to make head and tail be plain sub-objects:

private:
 int n_elements = 0;
 node<T> head = { T{}, nullptr, &tail };
 node<T> tail = { T{}, &head, nullptr };

(adjust all head-> to head. and other head to &head; the same for tail).

Remove doesn't need to track prev and next

Once we've found the target for remove, we can easily access its neighbours:

template<typename T>
T LList<T>::remove(const int pos)
{
 node<T> *curr = head.next;
 for (int i = 0; i < pos; i++) {
 curr = curr->next;
 }
 curr->prev->next = curr->next;
 curr->next->prev = curr->prev;
 T value = std::move(curr->value);
 delete curr;
 --n_elements;
 return value;
}

The insert method can be simplified in a similar way.

The node type needn't be public

Since node isn't exposed in the public interface, it can be a private type within LList:

template <typename T>
class LList
{
 struct node
 {
 T value;
 node* prev;
 node* next;
 node(T value, node *prev = nullptr, node *next = nullptr)
 : value{std::move(value)}, prev{prev}, next{next}
 {}
 };
 // ...
 node head = { T{}, nullptr, &tail };
 node tail = { T{}, &head, nullptr };
};

---

Modified code

I've made some other minor changes to simplify further.

#include <cstddef>
#include <utility>
template <typename T>
class LList
{
 struct node
 {
 T value;
 node* prev;
 node* next;
 node(T value, node *prev = nullptr, node *next = nullptr)
 : value{std::move(value)}, prev{prev}, next{next}
 {}
 node(const node&) = delete;
 void operator=(const node&) = delete;
 friend void swap(node& a, node& b) {
 using std::swap;
 swap(a.value, b.value);
 swap(a.prev, b.prev);
 swap(a.next, b.next);
 }
 };
public:
 LList() = default;
 LList(const LList<T>&);
 LList(const LList<T>&&);
 LList& operator=(LList<T>);
 ~LList();
 T const& get(std::size_t pos) const;
 T& get(std::size_t pos);
 void insert(T value, std::size_t pos);
 T remove(std::size_t pos);
 template<typename U>
 friend void swap(LList<U>&, LList<U>&);
private:
 std::size_t n_elements = 0;
 node head = { T{}, nullptr, &tail };
 node tail = { T{}, &head, nullptr };
};
template<typename T>
LList<T>::LList(const LList<T>& other)
{
 // work from back to front, so we always insert at position 0
 // (which is the cheapest)
 for (auto i = other.n_elements; i > 0; --i) {
 insert(other.get(i-1), 0);
 }
}
template<typename T>
LList<T>::LList(const LList<T>&& other)
{
 swap(*this, other);
}
template<typename T>
LList<T>& LList<T>::operator=(LList<T> other)
{
 swap(*this, other);
 return *this;
}
template<typename T>
LList<T>::~LList()
{
 for (auto p = head.next; p != &tail; ) {
 auto next = p->next;
 delete p;
 p = next;
 }
}
template<typename T>
void swap(LList<T>& a, LList<T>& b)
{
 using std::swap;
 swap(a.head, b.head);
 swap(a.tail, b.tail);
 swap(a.n_elements, b.n_elements);
}
template<typename T>
const T& LList<T>::get(std::size_t pos) const
{
 auto p = head.next;
 while (pos--)
 p = p->next;
 return p->value;
}
template<typename T>
T& LList<T>::get(std::size_t pos)
{
 auto p = head.next;
 while (pos--)
 p = p->next;
 return p->value;
}
template<typename T>
void LList<T>::insert(T value, std::size_t pos)
{
 auto p = &head;
 while (pos--)
 p = p->next;
 auto next = p->next;
 next->prev = p->next = new node(std::move(value), p, next);
 ++n_elements;
}
template<typename T>
T LList<T>::remove(std::size_t pos)
{
 auto p = head.next;
 while (pos--)
 p = p->next;
 p->prev->next = p->next;
 p->next->prev = p->prev;
 auto value = std::move(p->value);
 delete p;
 --n_elements;
 return value;
}

From this position, you could consider more advanced topics, such as providing iterators. Actually, providing full iterator support is quite a lot of work - 12 methods and a pair of classes - but there are some good reviews here that may give you a metaphorical "leg-up".

Or you might consider your own choice of next steps - don't let me constrain you!

• lucarlig: thanks for your feedback, i will work on fixing it.
• lucarlig: i would like to know which compiler you used?because it didn't crash on vs2017, and also didn't warn me about copy constructors. i checked the first answer and understood and changed the things you suggested. I ll check the rest now. i was thinking of implementing merge-sorting, i ll have look about iterators. thanks very much so much help you gave me.
• Toby Speight: I used GCC 8.2, with my usual set of warnings: -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Weffc++. You may have a compiler with fewer warnings (or perhaps haven't turned them all on). Merge-sort may well be a better first challenge than getting the iterators right (although once you have iterators, you can use them to do merging of all sorts of container - it's swings and roundabouts, really).
• Toby Speight: I did have to find the bug myself, but I shouldn't have had to - I missed the warning for returning a reference to a temporary amongst the other warnings!
• Toby Speight: And I used Valgrind 3.13 to examine the memory leak, if that helps...