Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
OOP-344 Doubly Linked List
#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;
}
}
#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_
#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_
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment