Implementation of doubly linked list

Question

List.h

#pragma once
#ifndef GUARD_LIST_H
#define GUARD_LIST_H
#include "List.h"
#include <stdexcept>
#include <iostream>
template<typename T>
class List
{
 struct Node
 {
 Node* prev;
 T key;
 Node* next;
 Node(Node* p, T k, Node* n): prev{p}, key{k}, next{n} {}
 };
public:
 //default constructor creates a sentinal object
 List() : sz{ 0 }, head{ new Node(nullptr, T(), nullptr) }, tail{ head } { }
 explicit List(std::istream& is):sz{ 0 }, head{ new Node(nullptr, T(), nullptr) }, tail{ head } { read_in(is); }
 ~List();
 //types
 using iterator = Node*;
 using const_iterator = const Node*;
 using value_type = T;
 using reference = T&;
 using const_reference = const T&;
 using size_type = size_t;
 //functions
 iterator begin() { return head; }
 const_iterator begin() const { return head; }
 iterator end() { return tail; }
 const_iterator end() const { return tail; }
 reference front() { return head->key; }
 const_reference front() const { return head->key; }
 reference back() { return tail->prev->key; }
 const_reference back() const { return tail->prev->key; }
 bool empty() const { return head == tail ; }
 size_type size() const { return sz; }
 iterator operator++() { return this->next; }
 iterator operator--() { return this->prev; }
 //std::ostream& operator<<(std::ostream& os) { os << }
 //modifier function
 void push_back(value_type);
 void erase(iterator);
 void pop_back();
 void push_front(value_type);
 void pop_front();
 iterator search(const value_type key) const
 {
 iterator x = head;
 while (x != end() && x->key != key)
 {
 x = x->next;
 }
 return x;
 }
 void insert(iterator pos, const value_type key)
 {
 if (empty())
 {
 iterator x = new Node(nullptr, key, tail);
 head = x;
 tail->prev = x;
 }
 else //if not empty
 {
 if (pos == head)
 {
 iterator x = new Node(nullptr, key, head);
 head->prev = x;
 head = x;
 }
 else
 {
 if (pos == tail)
 {
 iterator x = new Node(tail->prev, key, tail);
 tail->prev->next = x;
 tail->prev = x;
 }
 else
 {
 iterator x = new Node(pos, key, pos->next);
 pos->next->prev = x;
 pos->next = x;
 }
 }
 }
 ++sz;
 }
private:
 std::istream& read_in(std::istream& is)
 {
 if (is)
 {
 for (value_type x; is >> x; )
 push_back(x);
 }
 is.clear();
 return is;
 }
 size_type sz;
 iterator head;
 iterator tail;
};
template<typename T>
List<T>::~List()
{
 iterator tmp;
 for (;head;head = tmp) {
 tmp = head->next;
 delete head;
 }
}
template<typename T>
inline void List<T>::push_back(value_type key)
{
 insert(tail, key);
}
template<typename T>
inline void List<T>::erase(iterator pos)
{
 if (empty())
 throw std::domain_error("list is empty.");
 else
 {
 if (pos == head)
 {
 iterator x = head;
 head = head->next;
 head->prev = nullptr;
 delete x;
 }
 else
 {
 iterator x = pos;
 pos->prev->next = pos->next;
 pos->next->prev = pos->prev;
 delete x;
 }
 --sz;
 }
}
template<typename T>
inline void List<T>::pop_back()
{
 erase(tail->prev);
}
template<typename T>
inline void List<T>::push_front(value_type key)
{
 insert(head, key);
}
template<typename T>
inline void List<T>::pop_front()
{
 erase(head);
}
#endif // !GUARD_LIST_H

The above code compiled and worked fine.

I was getting the following errors when I tried to separate interface and implementation into header and source files respectively.

Error

Any sugguestions? I am just learning C++, data structures and algorithms. Thank you.

• jacwah: To be clear: is your code currently compiling or not?
• aig: @jacwah the first block of codes "List.h" compiles and runs without errors.
• aig: No compilation error when I have interface and definition (implementation) in the header file. Problem arises when i separate them
• Phrancis: Please clarify if the entirety of the code works, or remove the parts that do not work. All code posted on Code Review must be working as intended. See the on-topic page for details.
• John Franklin: As it's a template class the definitions should be in the header file anyway, you don't need a .cpp file. The class is only compiled when it gets used somewhere and given a specific type. Therefore the compiler needs to see the entire implementation to generate a class for that type.

Answer 1

Iterator and nodes

I would decouple the linked list nodes from the iterators. As of now, in order to iterate over your list, a person must write

for (auto i = lst.begin(); i != lst.end(); i = i ->next)
{
 cout << i->key << " ";
}

which is not quite idiomatic C++. So. What you could do is to manipulate the data in terms of Node s and leave the iterators what they are supposed to do. Also, what comes to the iterators, you could declare something like

struct Node_iterator {
 Node_iterator(Node* node) : current_node(node) {}
 Node* current_node;
 void operator++() { current_node = current_node->next; }
 void operator--() { current_node = current_node->prev; }
 T operator*() { return current_node->key; }
 bool operator!=(Node_iterator&& other)
 {
 return current_node != other.current_node;
 }
};

Taking the above, and rewriting the list algorithms in terms of nodes and not iterators, may lead to a more idiomatic iteration construct:

for (auto i = lst2.begin(); i != lst2.end(); ++i)
{
 cout << *i << " ";
}

Answer 2

#include <stdexcept>
#include <iostream>
#include "Lish.h"
template<typename T>
class List
{
 struct Node
 {
 Node* prev;
 T key;
 Node* next;
 Node(Node* p, T k, Node* n) : prev{ p }, key{ k }, next{ n } {}
 };
 struct Node_iterator {
 Node* current_node;
 Node_iterator(Node* node) : current_node{ node } {};
 void operator++() { current_node = current_node->next; }
 void operator--() { current_node = current_node->prev; }
 T operator*() { return current_node->key; }
 bool operator!=(const Node_iterator& other) {
 return current_node != other.current_node;
 }
 bool operator==(const Node_iterator& other) {
 return current_node == other.current_node;
 }
 };
public:
 //default constructor creates a sentinal object
 List();
 explicit List(std::istream& is);
 ~List();
 //copy, move constructors and assignments
 List(const List<T>& rhs);
 List<T>& operator=(const List<T>& rhs);
 List(List<T>&& rhs);
 List<T>& operator=(List<T>&& rhs);
 //member types
 using iterator = Node_iterator;
 using const_iterator = const Node_iterator;
 using value_type = T;
 using reference = T&;
 using const_reference = const T&;
 using size_type = size_t;
 //Iterators
 iterator begin() {
 iterator node(head);
 return node;
 }
 const_iterator begin() const {
 iterator node(head);
 return node;
 }
 iterator end() {
 iterator node(tail);
 return node;
 }
 const_iterator end() const {
 iterator node(tail);
 return node;
 }
 //Element access
 reference front() { return *begin(); }
 const_reference front() const { return *begin(); }
 reference back() { return *end()-- }
 const_reference back() const { return *end()--; }
 bool empty() const { return begin().current_node == end().current_node; }
 size_type size() const { return sz; }
 //modifier function
 void insert(iterator, const value_type); //insert an element to a given position
 void erase(iterator); //delete a node in a given iterator
 void push_back(const value_type); //inserts an element to the end
 void pop_back(); //removes the last element
 void push_front(const value_type); //inserts an element to the beginnning
 void pop_front(); //removes the first element
 iterator search(const value_type) const; //searches for the position of an element
private:
 size_type sz;
 Node* tail;
 Node* head;
 std::istream& read_in(std::istream& is);
};
#endif // !GUARD_LIST_H
template<typename T>
List<T>::List() : sz{ 0 }, tail{ new Node(nullptr, T(), nullptr) }, head{ tail }
{
}
template<typename T>
List<T>::List(std::istream & is) : sz{ 0 }, tail{ new Node(nullptr, T(), nullptr) }, head{ tail }
{
 read_in(is);
}
template<typename T>
List<T>::~List()
{
 auto x = head;
 auto y = x;
 while (x != nullptr)
 {
 y = x->next;
 delete x;
 x = y;
 }
}
template<typename T>
std::istream& List<T>::read_in(std::istream& is)
{
 if (is)
 {
 for (value_type x; is >> x; )
 push_back(x);
 }
 is.clear();
 return is;
}
template<typename T>
void List<T>::insert(iterator pos, const value_type key)
{
 if (empty())
 {
 auto x = new Node(nullptr, key, tail);
 head = x;
 tail->prev = x;
 }
 else //if not empty
 {
 if (pos == begin())
 {
 auto x = new Node(nullptr, key, head);
 head->prev = x;
 head = x;
 }
 else
 {
 if (pos == end())
 {
 auto x = new Node(tail->prev, key, tail);
 tail->prev->next = x;
 tail->prev = x;
 }
 else
 {
 auto x = new Node(pos.current_node, key, pos.current_node->next);
 pos.current_node->next->prev = x;
 pos.current_node->next = x;
 }
 }
 }
 ++sz;
}
template<typename T>
void List<T>::erase(iterator pos)
{
 if (empty())
 throw std::domain_error("list is empty.");
 else
 {
 if (pos == begin())
 {
 auto x = head;
 head = head->next;
 head->prev = nullptr;
 delete x;
 }
 else
 {
 auto x = pos;
 pos.current_node->prev->next = pos->next;
 pos.current_node->next->prev = pos->prev;
 delete x;
 }
 --sz;
 }
}
template<typename T>
void List<T>::push_back(const value_type key)
{
 iterator node(tail->prev);
 insert(node, key);
}
template<typename T>
inline void List<T>::pop_back()
{
 iterator node(tail->prev);
 erase(node);
}
template<typename T>
void List<T>::push_front(const value_type key)
{
 insert(begin(), key);
}
template<typename T>
void List<T>::pop_front()
{
 erase(begin());
}
template<typename T>
typename List<T>::iterator List<T>::search(const value_type key) const
{
 iterator x(head);
 while (x != end() && x->key != key)
 {
 x = x++;
 }
 return x;
}
template<typename T>
inline List<T>::List(const List<T>& rhs) : sz{ 0 }, tail{ new Node(nullptr, T(), nullptr) }, head{ tail }
{
 if (!rhs.empty())
 {
 head = new Node(nullptr, rhs.head->key, nullptr);
 iterator x(rhs.head->next);
 iterator y(head);
 auto counter = 1;
 while (x != rhs.end())
 {
 Node* z = new Node(y.current_node, x.current_node->key, nullptr);
 y.current_node->next = z;
 x = x.current_node->next;
 y = z;
 ++counter;
 }
 tail->prev = y.current_node;
 tail->prev->next = tail;
 sz = counter; //number of objects copied
 }
}
template<typename T>
inline List<T>& List<T>::operator=(const List<T>& rhs)
{
 if (this == &rhs)
 return *this;
 //delete old members
 auto a = head;
 auto b = a;
 while (a != nullptr)
 {
 b = a->next;
 delete a;
 a = b;
 }
 //assign new members from rhs
 head = new Node(nullptr, rhs.head->key, nullptr);
 iterator x(rhs.head->next);
 iterator y(head);
 auto counter = 1;
 while (x != rhs.end())
 {
 Node* z = new Node(y.current_node, x.current_node->key, nullptr);
 y.current_node->next = z;
 x = x.current_node->next;
 y = z;
 ++counter;
 }
 tail = new Node(nullptr, T(), nullptr); //because older tail would have been deleted.
 tail->prev = y.current_node;
 tail->prev->next = tail;
 sz = counter; //number of objects copied
 return *this;
}
template<typename T>
inline List<T>::List(List<T>&& rhs) : sz{ rhs.sz }, tail{ rhs.tail }, head{ rhs.head }
{
 rhs.sz = 0;
 rhs.tail = nullptr;
 rhs.head = nullptr;
}
template<typename T>
inline List<T>& List<T>::operator=(List<T>&& rhs)
{
 if (this == &rhs)
 return *this;
 //delete old members
 auto a = head;
 auto b = a;
 while (a != nullptr)
 {
 b = a->next;
 delete a;
 a = b;
 }
 sz = rhs.sz;
 tail = rhs.tail;
 head = rhs.head;
 rhs.sz = 0;
 rhs.tail = nullptr;
 rhs.head = nullptr;
 return *this;
}

Here is an improvement to my above question with a few improvements.

• separated nodes from iterators
• added copy and move constructors