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.

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

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