The answer is no. This does not work.
I also do not see a double linked list. Looks more like you wanted to implement a singly linked list.
There is no linked list at all somewhere in the code. Maybe you mix up "Node" and "Linked List". The "Node" is usually a part of the linked list. So it is contained in the Linked List class. And the whole functionality of the "Node" is usually not exposed to the outside world.
Then, you would add iterator functionality to the linked list class.
And last but not least, there is a wrapper class for reverse iterators. And with that, you can easily implement what you want. Please read here
But for that you need to create a --operator for your iterator. This is difficult for singly linked list and simple for double linked list.
C++ has already what you need. You can simply use it.
But, if we want to practice a little bit, then check some list implementations in the net and try to implement step by step. You can find a somehow OK starting point in the code example below.
Please note: Reverse can be done in several ways. Either you reverse the list by swapping values. That may be inefficient with complex data (but OK for simple data). std::reverese from the algorithm library is available for that.
Or, the pointer in the nodes can be swapped. With that data would not be touched at all. For this purpose, the list in the standard library has a special reversefunction. I also added such a function in the below example code.
And third, you can create a revers_iterator with the help of some build in C++ functions. Please look in the example code at the bottom on how to do that.
Anyway: Please read a book about data structures. This thing which consists of real paper :-). Then you will understand, that there is no naive implementation with a head and a tail pointer. For that a sentinel, a special noe is used. This makes life extremely simple for inserting and erasing values. No comparison with head and teail is needed.
Please find an example with Double Linked list and reverse iterator in the function main at the bottom.
#include <iostream>
#include <iterator>
#include <vector>
#include <type_traits>
#include <initializer_list>
#include <algorithm>
// ------------------------------------------------------------------------------------------------
// This would be in a header file -----------------------------------------------------------------
// Type trait helper to identify iterators --------------------------------------------------------
template<typename T, typename = void>
struct is_iterator { static constexpr bool value = false; };
template<typename T>
struct is_iterator<T, typename std::enable_if<!std::is_same<typename std::iterator_traits<T>::value_type, void>::value>::type> {
static constexpr bool value = true;
};
// The List class ---------------------------------------------------------------------------------
template <typename T>
class List {
// Sub class for a Node -----------
struct Node {
Node* next{};
Node* previous{};
T data{};
Node(Node* const n, Node* const p, const T& d) : next(n), previous(p), data(d) {}
Node(Node* const n, Node* const p) : next(n), previous(p) {}
Node() {}
};
// Private list data and functions --------
size_t numberOfElements{};
Node* head{};
void init() { head = new Node(); head->next = head; head->previous = head; numberOfElements = 0; }
public:
struct iterator; // Forward declaration
// Constructor --------------------
List() { init(); }
explicit List(const size_t count, const T& value) { init(); insert(begin(), count, value); };
explicit List(const size_t count) { init(); insert(begin(), count); }
template <typename Iter>
List(const Iter& first, const Iter& last) { init(); insert(begin(),first, last); }
List(const List& other) { init(), insert(begin(), other.begin(), other.end()); };
List(List&& other) : head(other.head), numberOfElements(other.numberOfElements) { other.init(); }
List(const std::initializer_list<T>& il) { init(); insert(begin(), il.begin(), il.end()); }
// Assignment ---------------------
List& operator =(const List& other) { clear(); insert(begin(), other.begin(), other.end()); return *this; }
List& operator =(List&& other) { clear(); head = other.head; numberOfElements = other.numberOfElements; other.init(); return *this; }
List& operator =(const std::initializer_list<T>& il) { clear(); insert(begin(),il.begin(),il.end()); return *this; }
void assign(const size_t count, const T& value) { clear(); insert(begin(), count, value); }
template <typename Iter>
void assign(const Iter& first, const Iter& last) { clear(); insert(begin(), first, last);}
void assign(const std::initializer_list<T>& il) { clear(); insert(begin(), il.begin(), il.end()); }
// Destructor ---------------------
~List() { clear(); }
// Element Access -----------------
T& front() { return *begin(); }
T& back() { return *(--end()); }
// Iterators ----------------------
iterator begin() const { return iterator(head->next, head); }
iterator end() const { return iterator(head, head); }
// Capacity -----------------------
size_t size() const { return numberOfElements; }
bool empty() { return size() == 0; }
// Modifiers ----------------------
void clear();
iterator insert(const iterator& insertBeforePosition, const T& value);
iterator insert(const iterator& insertBeforePosition);
template <class Iter, std::enable_if_t<is_iterator<Iter>::value, bool> = true>
iterator insert(const iterator& insertBeforePosition, const Iter& first, const Iter& last);
iterator insert(const iterator& insertBeforePosition, const size_t& count, const T& value);
iterator insert(const iterator& insertBeforePosition, const std::initializer_list<T>& il);
iterator erase(const iterator& posToDelete);
iterator erase(const iterator& first, const iterator& last);
void push_back(const T& d) { insert(end(), d); }
void pop_back() { erase(--end()); };
void push_front(const T& d) { insert(begin(), d); }
void pop_front() { erase(begin()); };
void resize(size_t count);
void resize(size_t count, const T& value);
void swap(List& other) { std::swap(head, other.head); std::swap(numberOfElements, other.numberOfElements); }
// Operations --------------------
void reverse();
// Non standard inefficient functions --------------------------
T& operator[](const size_t index) const { return begin()[index]; }
// ------------------------------------------------------------------------
// Define iterator capability ---------------------------------------------
struct iterator {
// Definitions ----------------
using iterator_category = std::bidirectional_iterator_tag;
using difference_type = std::ptrdiff_t;
using value_type = T;
using pointer = T*;
using reference = T&;
// Data -----------------------
Node* iter{};
Node* head{};
// Constructor ----------------
iterator(Node*const node, Node* const h) : iter(node), head(h) {};
iterator() {};
// Dereferencing --------------
reference operator*() const { return iter->data; }
reference operator->() const { return &**this; }
// Arithmetic operations ------
iterator operator++() { iter = iter->next; return *this; }
iterator operator++(int) { iterator tmp = *this; ++* this; return tmp; }
iterator operator--() { iter = iter->previous; return *this; }
iterator operator--(int) { iterator tmp = *this; --* this; return tmp; }
iterator operator +(const difference_type& n) const {
iterator temp{ *this }; difference_type k{ n }; if (k > 0) while (k--)++temp; else while (k++)--temp; return temp;
}
iterator operator +=(const difference_type& n) {
difference_type k{ n }; if (k > 0) while (k--)++* this; else while (k++)--* this; return *this;
};
iterator operator -(const difference_type& n) const {
iterator temp{ *this }; difference_type k{ n }; if (k > 0) while (k--)--temp; else while (k++)++temp; return temp;
}
iterator operator -=(const difference_type& n) {
difference_type k{ n }; if (k > 0) while (k--)--* this; else while (k++)++* this; return *this;
};
// Comparison -----------------
bool operator ==(const iterator& other) const { return iter == other.iter; };
bool operator !=(const iterator& other) const { return iter != other.iter; };
bool operator < (const iterator& other) const { return other.iter - iter < 0; };
bool operator <= (const iterator& other) const { return other.iter - iter <= 0; };
bool operator > (const iterator& other) const { return other.iter - iter > 0; };
bool operator >= (const iterator& other) const { return other.iter - iter >= 0; };
// Special non standard functions -----------------
difference_type operator-(const iterator& other) const;
reference operator[] (const size_t index);
};
};
// ------------------------------------------------------------------------------------------------
// Implementation of list functions. This would normally go into a TCC file -----------------------
// List class functions ---------------
template <typename T>
void List<T>::clear() {
for (Node* nextNode{}, * currentNode(head->next); currentNode != head; currentNode = nextNode) {
nextNode = currentNode->next;
delete currentNode;
}
init();
}
template <typename T>
typename List<T>::iterator List<T>::insert(const List<T>::iterator& insertBeforePosition, const T& value)
{
Node* nodeInsertBeforePosition = insertBeforePosition.iter;
Node* newNode = new Node(nodeInsertBeforePosition, nodeInsertBeforePosition->previous, value);
nodeInsertBeforePosition->previous = newNode;
(newNode->previous)->next = newNode;
++numberOfElements;
return iterator(newNode, head);
}
template <typename T>
typename List<T>::iterator List<T>::insert(const List<T>::iterator& insertBeforePosition)
{
Node* nodeInsertBeforePosition = insertBeforePosition.iter;
Node* newNode = new Node(nodeInsertBeforePosition, nodeInsertBeforePosition->previous);
nodeInsertBeforePosition->previous = newNode;
(newNode->previous)->next = newNode;
++numberOfElements;
return iterator(newNode, head);
}
template <typename T>
template <class Iter, std::enable_if_t<is_iterator<Iter>::value, bool>>
typename List<T>::iterator List<T>::insert(const List<T>::iterator& insertBeforePosition, const Iter& first, const Iter& last) {
iterator result(insertBeforePosition.iter, head);
if (first != last) {
result = insert(insertBeforePosition, *first);
Iter i(first);
for (++i; i != last; ++i)
insert(insertBeforePosition, *i);
}
return result;
}
template <typename T>
typename List<T>::iterator List<T>::insert(const List<T>::iterator& insertBeforePosition, const size_t& count, const T& value) {
iterator result(insertBeforePosition.iter, head);
if (count != 0u) {
result = insert(insertBeforePosition, value);
for (size_t i{ 1u }; i < count; ++i)
insert(insertBeforePosition, value);
}
return result;
}
template <typename T>
typename List<T>::iterator List<T>::insert(const List<T>::iterator& insertBeforePosition, const std::initializer_list<T>& il) {
return insert(insertBeforePosition, il.begin(), il.end());
}
template <typename T>
typename List<T>::iterator List<T>::erase(const List<T>::iterator& posToDelete) {
iterator result = posToDelete;
++result;
Node* nodeToDelete = posToDelete.iter;
if (nodeToDelete != head) {
nodeToDelete->previous->next = nodeToDelete->next;
nodeToDelete->next->previous = nodeToDelete->previous;
delete nodeToDelete;
--numberOfElements;
}
return result;
}
template <typename T>
typename List<T>::iterator List<T>::erase(const List<T>::iterator& first, const List<T>::iterator& last) {
iterator result{ end() };
if (first == begin() && last == end())
clear();
else {
while (first != last)
first = erase(first);
result = last;
}
return result;
}
template <typename T>
void List<T>::resize(size_t count) {
if (numberOfElements < count)
for (size_t i{ numberOfElements }; i < count; ++i)
insert(end());
else
while (count--)
pop_back();
}
template <typename T>
void List<T>::resize(size_t count, const T& value) {
if (numberOfElements < count)
for (size_t i{ numberOfElements }; i < count; ++i)
insert(end(),value);
else
while (count--)
pop_back();
}
template <typename T>
void List<T>::reverse() {
const Node* oldHead = head;
for (Node* nptr = head; ; nptr = nptr->previous) {
std::swap(nptr->next, nptr->previous);
if (nptr->previous == oldHead) // Previous was the original next
break;
}
}
// ------------------------------------
// Iterator functions -----------------
template <typename T>
typename List<T>::iterator::difference_type List<T>::iterator::operator-(const iterator& other) const {
difference_type result{};
Node* nptr = head;
int indexThis{ -1 }, indexOther{ -1 }, index{};
do {
nptr = nptr->next;
if (nptr == iter)
indexThis = index;
if (nptr == other.iter)
indexOther = index;
++index;
} while (nptr != head);
if (indexThis >= 0 and indexOther >= 0)
result = indexThis - indexOther;
return result;
}
template <typename T>
typename List<T>::iterator::reference List<T>::iterator::operator[] (const size_t index) {
Node* nptr = head->next;
for (size_t i{}; i < index and nptr != head; ++i, nptr = nptr->next)
;
return nptr->data;
}
// ------------------------------------------------------------------------------------------------
// This would be in a cpp file --------------------------------------------------------------------
int main() {
List<int> list{ 1,2,3,4,5 };
std::cout << "Original List\n";
for (int i : list) std::cout << i << ' '; std::cout << '\n';
std::cout << "\nInternal reverse function. Kust swap ointers in Node\n";
list.reverse();
for (int i : list) std::cout << i << ' '; std::cout << '\n';
std::cout << "\nReverse function from algorithm library. Reverse values with copy\n";
std::reverse(list.begin(), list.end());
for (int i : list) std::cout << i << ' '; std::cout << '\n';
// Use reverse iterators
std::cout << "\nBuild and use revers iterators\n";
std::reverse_iterator<List<int>::iterator> riter = std::make_reverse_iterator(list.end());
std::reverse_iterator<List<int>::iterator> riterEnd = std::make_reverse_iterator(list.begin());
for (; riter != riterEnd; ++riter)
std::cout << *riter << ' '; std::cout << '\n';
return 0;
}
Please note. The above is a very simplified implementation. Not very efficient and not using allocaters.
Attention. This code is only partially tested. It may not even compile be instantiating templates . . .
