Circular doubly linked list with templates

I tried to write some code namely "Circular doubly linked list" and I would like to use templates to do this.

This is the first time I use templates and throws some exceptions. I would like to know if sth is badly writen, sth must be changed or I need to rewrite everything.

Last but not least, what is the best framework to unit test in C++ (and mostly without too much effort to implement in IDE, I use CLion) like jUnit in Java?

ListNode class

#ifndef CYCLIC_LIST_LISTNODE_H
#define CYCLIC_LIST_LISTNODE_H

template<typename DT>
class List;

template<typename DT>
class ListNode{
private:
DT dataItem;
ListNode *prior, *next;

ListNode(const DT & data, ListNode *prior = nullptr, ListNode *next = nullptr)
: dataItem(data), prior(prior), next(next) {}

ListNode() : dataItem(), prior(nullptr), next(nullptr) {}

friend class List<DT>;
};

#endif //CYCLIC_LIST_LISTNODE_H


List class

#ifndef CYCLIC_LIST_LIST_H
#define CYCLIC_LIST_LIST_H

#include "ListNode.h"
#include <iostream>
#include <stdexcept>
#include <exception>

template<typename DT>
class ListNode;

template<typename DT>
class List{
private:
ListNode<DT> *cursor;
public:
~List();

void remove() throw(std::logic_error);
void replace(const DT & newDataItem) throw(std::logic_error);
void clear();

bool isEmpty() const;

void gotoBeginning() throw(std::logic_error);
void gotoEnd() throw(std::logic_error);
void gotoNext() throw(std::logic_error);
void gotoPrior() throw(std::logic_error);

DT getCursor() const throw(std::logic_error);

void showStructure() const;
};

template<typename  DT>
void List<DT>::replace(const DT & newDataItem) throw(std::logic_error){
if(cursor == nullptr || isEmpty())
throw std::logic_error("Empty list!");

cursor->dataItem = newDataItem;
}

template<typename DT>
void List<DT>::clear() {
if(!isEmpty())
{
ListNode<DT>* cursor2;
cursor = cursor2->prior;

{
delete cursor2;
cursor2 = cursor;
cursor = cursor->next;
}
delete cursor;
}
cursor = nullptr;
}

template<typename DT>
void List<DT>::remove() throw(std::logic_error) {
if (isEmpty())
throw std::logic_error("Empty list!");

ListNode<DT> * temp;

temp = cursor->prior;
(cursor->prior)->next = cursor->next;
(cursor->next)->prior = cursor->prior;

{
else
}

delete cursor;

cursor = temp;
}

template<typename DT>
void List<DT>::insert(const DT &newDataItem) throw(std::bad_alloc) {
try {
ListNode<DT> *newNode = new ListNode<DT>(newDataItem);

if (isEmpty()) {
cursor = newNode;
} else {

newNode->next = cursor->next;
newNode->prior = cursor;

cursor->next = newNode;
(newNode->next)->prior = newNode;

gotoNext();
}
}
}

}

template<typename DT>
bool List<DT>::isEmpty() const {
}

template<typename DT>
void List<DT>::gotoBeginning() throw(std::logic_error) {
if (isEmpty())
throw std::logic_error("Empty list!");

}

template<typename DT>
void List<DT>::gotoEnd() throw(std::logic_error){
if (isEmpty())
throw std::logic_error("Empty list!");

}

template<typename DT>
void List<DT>::gotoNext() throw(std::logic_error) {
if (isEmpty())
throw std::logic_error("Empty list");

cursor = cursor->next;
}

template<typename DT>
void List<DT>::gotoPrior() throw(std::logic_error) {
if (isEmpty())
throw std::logic_error("Empty list");

cursor = cursor->prior;
}

template<typename DT>
DT List<DT>::getCursor() const throw(std::logic_error) {
if (isEmpty())
throw std::logic_error("Empty list");

return cursor->dataItem;
}

template< class DT>
void List<DT>::showStructure () const
{
ListNode<DT> *temp;
std::cout << temp->dataItem << " ";

std::cout<< temp->dataItem << std::endl;
}

template <typename DT >
List<DT>::~List()
{
clear();
}

#endif //CYCLIC_LIST_LIST_H

• Does this code work, or should the parts that are throwing exceptions not be doing that? – user34073 Dec 24 '16 at 17:42
• This code works, I try to use exceptions when we have nullptr and when some functions try to do sth with nullptr. If exceptions are not expected in this situation what should be instead? – Newbie Dec 24 '16 at 17:48
• Cool. Just making sure because non-working code is off-topic. – user34073 Dec 24 '16 at 17:55
• One thing right of the bat that I don't like is the use of dynamic exception specification on your functions. They are deprecated since C++11 and are specified to be removed in C++17. – Blazo Dec 25 '16 at 7:23
• @Newbie: Write your code to be exception safe. This primarily means implementing either a non throwing method or a method that throws but provides the strong exception guarantee. The strong exception guarantee means that if a method throws an exception then the state of the object remains unchanged. – Martin York Dec 27 '16 at 21:07

Review

ListNode:

Are you sure you want this constructor?

ListNode() : dataItem(), prior(nullptr), next(nullptr) {}


The problem I see is that it default constructs the data object. Not all data objects can be default constructed. The other question I would ask is: Can you create a node with no item in it?

In C++11 we introduced move semantics so I would expect to see a move constructor on this class.

In C++11 we introduced perfect forwarding. So though not required it is sometimes nice to build an item (of type DT) in place with the constructors parameters. You can achieve this using perfect forwarding. If you look at std::vector you can see this in practive in the emplace_back() method.

List

You don't need to forward declare a class if you have already included the header file:

#include "ListNode.h"

// This is not needed.
template<typename DT>
class ListNode;

Design

The cursor concept. I see your logic.

ListNode<DT> *cursor;
void gotoBeginning() throw(std::logic_error);
void gotoEnd() throw(std::logic_error);
void gotoNext() throw(std::logic_error);
void gotoPrior() throw(std::logic_error);

DT getCursor() const throw(std::logic_error);


But this means all code is using the same cursor. This makes threaded code impossible and even single threaded code hard if you are using the list in more than one place.

In C++ we end to use the concept of an iterator. The iterator is an object itself that tracks the current position in the list. Can be copied so you can save a position; incremented and decremented to move along the container; de-referenced to get the element value. It is then used in conjunction with the methods of the container for insertion/deletion. But the important point; it is a separate object.

Exception Specifications

Most languages have decided that exception specifications are a bad idea. In Java they devolve (over time) to throw Exception and in C++ the only useful one we found was the specification that said this function does not throw.

void insert(const DT &newDataItem) throw(std::bad_alloc);
void remove() throw(std::logic_error);
void replace(const DT & newDataItem) throw(std::logic_error);
void gotoBeginning() throw(std::logic_error);
void gotoEnd() throw(std::logic_error);
void gotoNext() throw(std::logic_error);
void gotoPrior() throw(std::logic_error);
DT getCursor() const throw(std::logic_error);


As a result. C++11 deprecated the throw specifier on functions/methods and introduced the noexcept specifier. So either your function is exception safe and throws nothing or it can potentially throw.

Sentinel

Your code uses a nullptr head to specify an empty list. The problem is that your code basically has two versions of every function. Code to handle the empty list situation and code to handle the non empty list.

There is a technique that uses a sentinel object. This is a fake ListNode object (with no data). That is always in the list (the sentinel). This simplifies the code tremendously as you no longer need to check for the empty list when removing or adding elements.

Move Semantics

Your list does not support move semantics or emplace semantics. This can make the code very inefficient.

// COPY (current implementation)
template<typename  DT>
void List<DT>::replace(const DT & newDataItem) throw(std::logic_error)
{
if(cursor == nullptr || isEmpty())
throw std::logic_error("Empty list!");

cursor->dataItem = newDataItem;
}

// Move
template<typename  DT>
void List<DT>::replace(const DT&& newDataItem) throw(std::logic_error)
{
if(cursor == nullptr || isEmpty())
throw std::logic_error("Empty list!");

// Uses the objects move assignment operator
// to move the object over the current object.
// For large objects this can be significantly more efficient).
cursor->dataItem = std::move(newDataItem);
}

Bug
template<typename DT>
void List<DT>::clear() {
if(!isEmpty())
{
ListNode<DT>* cursor2;
cursor2 = head->prior;   // I believe this is a bug.
// As a result you will probably only
// remove one item from the list.

Bug
template<typename DT>
void List<DT>::remove() throw(std::logic_error) {
// STUFF
delete cursor;

cursor = temp;  This is a bug if head is nullptr.
}


Biggest Bug

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

You class manages resources (hence the destructor). But you have not defined the copy/move semantics of the class. As a result the compiler has provided default implementations of each (which don't work when you are managing resources). Hence the rule.

{
List<int>   l1;
l1.insert(5);
List<int>   l2(l1);  // Makes a copy of l1
}
// Both objects are destroyed.
// But because you don't not implement copy semantics the
// compiler generated version is used which does a shallow copy
// and thus both objects have the same pointer. This may not seem
// like a problem but both destructors are going to use that pointer
// to head to delete the list and as a result the list will be
// deleted twice.