OOP-344 Doubly Linked List

LinkedList.cpp

#include "LinkedList.h"

LinkedList::Node::Node(LinkedList::ListType val, Node* next, Node* prev) 
    : val(val), next(next), prev(prev)
{
}

LinkedList::Node::~Node()
{
}


LinkedList::Itterator::Itterator(LinkedList::Node* at)
    :at(at)
{
}

LinkedList::Itterator::~Itterator()
{
}

LinkedList::Itterator& LinkedList::Itterator::next()
{
    this->operator++();
    return *this;
}

LinkedList::Itterator& LinkedList::Itterator::prev()
{
    this->operator--();
    return *this;
}

LinkedList::ListType& LinkedList::Itterator::val()
{
    return at->val;
}


LinkedList::ListType& LinkedList::Itterator::operator*()
{
    return at->val;
}

LinkedList::Itterator& LinkedList::Itterator::operator++()
{
    at = at->next;
    return *this;
}

LinkedList::Itterator LinkedList::Itterator::operator++(int x)
{
    Itterator result(this->at);
    ++(*this);
    return result;
}

LinkedList::Itterator& LinkedList::Itterator::operator--()
{
    at = at->prev;
    return *this;
}

LinkedList::Itterator LinkedList::Itterator::operator--(int x)
{
    Itterator result(this->at);
    --(*this);
    return result;
}

size_t LinkedList::Itterator::getDistance(Itterator& from)
{
    return *this - from;
}

size_t LinkedList::Itterator::operator-(Itterator& from)
{
    Itterator copy = *this;

    size_t dist = 1;

    while (copy.at != from.at && copy.at != nullptr)
    {
        dist++;
        copy--;
    }

    return dist;
}


LinkedList::LinkedList(void) : _start(nullptr), _end(nullptr), _size(0)
{
}

LinkedList::~LinkedList(void)
{
    while (_start)
    {
        Node* next = _start->next;
        delete _start;
        _start = next;
    }
}

void LinkedList::push_back(LinkedList::ListType val)
{
    Node* next = new Node(val, nullptr, _end);
    if (_end)
    {
        _end->next = next;
    }
    _end = next;
    if (_start == nullptr)
    {
        _start = next;
    }
    ++_size;
}

void LinkedList::push_front(LinkedList::ListType val)

{
    Node* next = new Node(val, _start, nullptr);
    if (_start)
    {
        _start-> prev = next;
    }
    _start = next;
    if (!_end)
    {
        _end = next;
    }
    ++_size;
}

LinkedList::ListType LinkedList::pop_front()
{
    Node* oldStart = _start;
    ListType oldVal = _start->val;
    _start = _start->next;

    if (_start == nullptr)
    {
        _end = nullptr;
    }
    delete oldStart;
    --_size;
    return oldVal;
}

LinkedList::ListType LinkedList::pop_back()
{
    Node* oldEnd = _end;
    ListType oldVal = _end->val;
    _end = _end->prev;
    if (_end == nullptr)
    {
        _start = nullptr;
    }
    delete oldEnd;
    --_size;
    return oldVal;
}

size_t LinkedList::size()
{
    return _size;
}

LinkedList::Itterator LinkedList::begin()
{
    return Itterator(_start);
}

LinkedList::Itterator LinkedList::end()
{
    return Itterator(_end);
}

LinkedList::ListType& LinkedList::operator[](unsigned x)
{
    if (x < (_size / 2))
    {
        Itterator i = this->begin();
        while (x--)
            ++i;
        return *i;
    }
    else
    {
        Itterator i = this->begin();
        x = _size - x;
        while(x--)
            ++i;
        return *i;
    }
}

LinkedList.hpp

#pragma once
#ifndef _G_LINKED_LIST_
#define _G_LINKED_LIST_

class LinkedList
{
    /**
     * \typedef int ListType
     *
     * \brief   the type that the list holds
     */

    typedef int ListType;

    /**
     * \class   Node
     *
     * \brief   A list node that contains a value and pointers to next and prev.
     *
     */

    class Node
    {
    public:

        /**
         * \fn  Node::Node(ListType val, Node* next = nullptr, Node* prev = nullptr);
         *
         * \brief   Constructor.
         *
         * \param   val             The value.
         * \param   next    The next node.
         * \param   prev    The previous node
         */

        Node(ListType val, Node* next = nullptr, Node* prev = nullptr);
        ~Node();

        /**
         * \brief   The value held in this node.
         */

        ListType val;

        /**
         * \brief   The next node in the list.
         */

        Node* next;

        /**
         * \brief   The previous node in the list.
         */

        Node* prev;

    };

    /**
     * \class   Itterator
     *
     * \brief   An itterator for the list.
     *
     */
    
    class Itterator
    {
    public:

        /**
         * \fn  Itterator::Itterator(Node* at);
         *
         * \brief   Creates an iterator placed at the node
         *
         * \param Where to place the iterator.
         */

        Itterator(Node* at);

        ~Itterator();

        /**
         * \fn  Itterator& Itterator::next();
         *
         * \brief   Move to the next node.
         *
         * \return  A reference to itself;
         */

        Itterator& next();

        /**
         * \fn  Itterator& Itterator::prev();
         *
         * \brief   Move to the previous node.
         *
         * \return  A reference to itself;
         */

        Itterator& prev();

        /**
         * \fn  ListType& Itterator::val();
         *
         * \brief   A reference to the value at the current position
         *
         * \return  A reference to the value at the current position
         */

        ListType& val();

        /**
         * \fn  ListType& Itterator::operator*();
         *
         * \brief   A reference to the value at the current position
         *
         * \return  A reference to the value at the current position
         */

        ListType& operator*();

        /**
         * \fn  Itterator& Itterator::operator++();
         *
         * \brief   Moves the itterator to the next element in the list
         *
         * \return  The Itterator at the next position
         */

        Itterator& operator++();

        /**
         * \fn  Itterator Itterator::operator++(int x);
         *
         * \brief   Moves the itterator to the next element in the list
         *
         * \return  A copy of the itterator at the old position
         */

        Itterator operator++(int x);

        /**
         * \fn  Itterator& Itterator::operator--();
         *
         * \brief   Moves the itterator to the previous element in the list
         *
         * \return  A referenec to it's self in the new position
         */

        Itterator& operator--();

        /**
         * \fn  Itterator Itterator::operator--(int x);
         *
         * \brief   Moves the itterator to the previous element in the list
         *
         * \return  A copy of the itterator in the old position
         */

        Itterator operator--(int x);

        /**
         * \fn  size_t Itterator::getDistance(Itterator& from);
         *
         * \brief   The number of elements between two itterators
         *          
         * \param from    Where to calculate the distance from
         *
         * \return  The distance to the itterator.
         */

        size_t getDistance(Itterator& from);

        /**
         * \fn  size_t Itterator::operator-(Itterator& from);
         *
         * \brief   The number of elements between two itterators
         *          
         * \param from    Where to calculate the distance from
         *
         * \return  The distance to the itterator.
         */

        size_t operator-(Itterator& from);

    private:

        /**
         * \brief   at Where in the list the itterator is placed.
         */

        Node* at;
    };

public:

    /**
     * \fn  LinkedList::LinkedList();
     *
     * \brief   Creates an empty doublylinkedlist.
     *
     */

    LinkedList();

    ~LinkedList();

    /**
     * \fn  void LinkedList::push_back(ListType val);
     *
     * \brief   Adds a value to the end of the list
     *
     * \param   val The value.
     */

    void push_back(ListType val);

    /**
     * \fn  void LinkedList::push_front(ListType val);
     *
     * \brief   Adds a value to the front of the list
     *
     * \param   val The value.
     */

    void push_front(ListType val);

    /**
     * \fn  ListType LinkedList::pop_front();
     *
     * \brief   Removes the value at the begining of the list
     *
     * \return  The value that was previously at the front
     */

    ListType pop_front();

    /**
     * \fn  ListType LinkedList::pop_back();
     *
     * \brief   Removes the value at the end of the list
     *
     * \return  The value that was previously last
     */

    ListType pop_back();

    /**
     * \fn  size_t LinkedList::size();
     *
     * \brief   Gets the number of elements in the list
     *
     * \return  number of elements in the list
     */

    size_t size();

    /**
     * \fn  Itterator LinkedList::begin();
     *
     * \brief   Gets an Itterator that is placed at the begininng of the list
     *
     * \return  An Itterator at the beging of the list.
     */

    Itterator begin();

    /**
     * \fn  Itterator LinkedList::end();
     *
     * \brief   Gets an Itterator that is placed at the end of the list
     *
     * \return  An Itterator at the end of the list.
     */

    Itterator end();

    /**
     * \fn  ListType& LinkedList::operator[](unsigned x);
     *
     * \brief   Gets the value at the specified position
     *
     * \param   i   The index of the value.
     *
     * \return  The value.
     */

    ListType& operator[](unsigned i);

protected:

private:

    /**
     * \brief   The begining of the list.
     */

    Node* _start;

    /**
     * \brief   The end of the list.
     */

    Node* _end;

    /**
     * \brief   The size of the list.
     */

    size_t _size;

};

#endif //_G_LINKED_LIST_

LinkedList_nodoc.hpp

#pragma once
#ifndef _G_LINKED_LIST_
#define _G_LINKED_LIST_
class LinkedList
{
    typedef int ListType;

    class Node
    {
    public:
        Node(ListType val, Node* next = nullptr, Node* prev = nullptr);
        ~Node();
        ListType val;
        Node* next;
        Node* prev;
    };
    class Itterator
    {
    public:
        Itterator(Node* at);
        ~Itterator();
        Itterator& next();
        Itterator& prev();
        ListType& val();
        ListType& operator*();
        Itterator& operator++();
        Itterator operator++(int x);
        Itterator& operator--();
        Itterator operator--(int x);
        size_t getDistance(Itterator& from);
        size_t operator-(Itterator& from);
    private:
        Node* at;
    };
public:
    LinkedList();
    ~LinkedList();
    void push_back(ListType val);
    void push_front(ListType val);
    ListType pop_front();
    ListType pop_back();
    size_t size();
    Itterator begin();
    Itterator end();
    ListType& operator[](unsigned i);
protected:
private:
    Node* _start;
    Node* _end;
    size_t _size;
};
#endif //_G_LINKED_LIST_