Psst.. new poll here.
Psst.. new forums here.
Microsoft is blocking us again (TY IP Reputation!) so just use oauth login instead. :)
Paste
Pasted as C++ by Dan ( 7 years ago )
#ifndef CPP_DOUBLY_LINKED_LIST_HPP_
#define CPP_DOUBLY_LINKED_LIST_HPP_
#include <cassert> // assert
/**
* @brief Doubly Linked List. Holds pointers to the beginning, end of the list and size of the list.
* Therefore some operations have constant complexity.
* @tparam T Type of items.
*/
template<typename T>
class CDoublyLinkedList
{
template<typename TItem>
class CDoublyLinkedListItem;
/**
* @brief List item. Each list's value is hold in this class.
* It wraps value by adding pointer to next and previous element.
* @tparam TItem Type of items stored in a list.
*/
template<typename TItem>
class CDoublyLinkedListItem
{
public:
/**
* @brief Constructor.
* @param aValue Value.
*/
explicit CDoublyLinkedListItem(const TItem& aValue)
: mPrevious(nullptr)
, mNext(nullptr)
, mValue(aValue)
{}
/**
* @brief Constructor.
* @param aPrevious Pointer to previous item.
* @param aNext Pointer to next item.
* @param aValue Value.
*/
CDoublyLinkedListItem(CDoublyLinkedListItem<TItem>* aPrevious,
CDoublyLinkedListItem<TItem>* aNext,
const TItem& aValue)
: mPrevious(aPrevious)
, mNext(aNext)
, mValue(aValue)
{}
/**
* @brief Pointer to previous Item.
*/
CDoublyLinkedListItem<TItem>* mPrevious;
/**
* @brief Pointer to next item.
*/
CDoublyLinkedListItem<TItem>* mNext;
/**
* @brief Value.
*/
TItem mValue;
};
public:
// /////////////////////////////////////////////////////////////////////
// /////////////////////////////////////////////////////////////////////
// /////////////////////////////////////////////////////////////////////
/**
* @brief Iterator for DoublyLinked container. It is a random access iterator.
* @tparam T Type of items.
*/
class CDoublyLinkedListIterator
{
/**
* @brief Pointer to data.
*/
CDoublyLinkedListItem<T>* mPtr;
public:
/**
* @brief Constructor.
* @param aPtr Pointer to DoublyLinked's array.
*/
explicit CDoublyLinkedListIterator(CDoublyLinkedListItem<T>* aPtr)
: mPtr(aPtr)
{
}
CDoublyLinkedListIterator operator++() {
this->mPtr = this->mPtr->mNext;
return this;
}
};
// /////////////////////////////////////////////////////////////////////
// /////////////////////////////////////////////////////////////////////
// /////////////////////////////////////////////////////////////////////
/**
* @brief Reverse iterator for DoublyLinked container. It is a random access iterator.
* @tparam T Type of items.
*/
class CReverseDoublyLinkedListIterator
{
/**
* @brief Pointer to data.
*/
CDoublyLinkedListItem<T>* mPtr;
public:
/**
* @brief Constructor.
* @param aPtr Pointer to DoublyLinked's array.
*/
explicit CReverseDoublyLinkedListIterator(CDoublyLinkedListItem<T>* aPtr) : mPtr(aPtr){}
};
// /////////////////////////////////////////////////////////////////////
// /////////////////////////////////////////////////////////////////////
// /////////////////////////////////////////////////////////////////////
using DIterator = CDoublyLinkedListIterator;
using DReverseIterator = CReverseDoublyLinkedListIterator;
/**
* @brief Constructor. Initializes empty list.
*/
CDoublyLinkedList()
: mBegin(nullptr), mEnd(nullptr)
{}
/**
* @brief Copy constructor.
* @param aObj Object to copy.
*/
CDoublyLinkedList(const CDoublyLinkedList<T>& aObj)
{
if (aObj.mBegin == nullptr) {
size = 0;
mBegin = nullptr;
mEnd = nullptr;
}
else {
CDoublyLinkedListItem<T> *item = new CDoublyLinkedListItem<T>(aObj.mBegin->mValue);
CDoublyLinkedListItem<T> *given = aObj.mBegin->mNext;
CDoublyLinkedListIterator buffor;
for (CDoublyLinkedListIterator i = aObj.mBegin; i != aObj.mEnd; )
{
buffor = i.mPtr->mNext;
delete i.mPtr;
i = buffor;
}
}
}
/**
* @brief Assignment operator
* @param aObj Object to copy.
* @return this object with copied content.
*/
CDoublyLinkedList<T>& operator=(const CDoublyLinkedList<T>& aObj)
{
//this.aObj = aObj;
return *this;
}
/**
* @brief Compares vectors.
* @param aObj Object to compare
* @return true if vectors contain equal object; otherwise false
*/
bool operator==(const CDoublyLinkedList<T>& aObj)
{
return false;
}
/**
* @brief Compares vectors.
* @param aObj Object to compare
* @return false if vectors contain equal object; otherwise true
*/
bool operator!=(const CDoublyLinkedList<T>& aObj)
{
return !(*this == aObj);
}
/**
* @brief Destructor. Deallocates memory.
*/
~CDoublyLinkedList()
{
}
/**
* @brief Returns a number of items.
* Complexity: O(n) - because it has to pass for all item.
* @return Number of items.
*/
unsigned int size() const
{
return 0;
}
/**
* @brief Adds value to list.
* Complexity: O(1) - because the list holds pointer to the last item.
* @param aValue Value to add.
*/
void pushBack(const T& aValue)
{
}
/**
* @brief Removes last item from list.
* Complexity: O(n) - because it has to pass through all items
* @return Last item from list.
*/
T popBack()
{
return T();
}
/**
* @brief Puts new item at the beginning of the list.
* Complexity: O(1) - because the list holds pointer to the beginning.
* @param aValue Value.
*/
void pushFront(const T& aValue)
{
}
/**
* @brief Remove the first element from the list.
* Complexity: O(1) - because list has pointer to beginning.
* @return The first item from list.
*/
T popFront()
{
return T();
}
/**
* @brief Checks the list contains object.
* Complexity: O(n) - because it has to check all items. In the worst case entire list will be checked.
* The worst case takes place if there isn't the value in the list or it is on the last position.
* @param aValue Value to check.
* @return true if list contains value, otherwise false.
*/
bool contains(const T& aValue)
{
return false;
}
/**
* @brief Indicates if the list empty.
* Complexity: O(1)
* @return true if list is empty, otherwise false.
*/
bool empty() const
{
return size == 0;
}
/**
* @brief Get pointer to the value at given position. Complexity: O(n) - because it has to check all items in the worst case.
* @param aIndex Position of value.
* @return Pointer to value or null if there isn't value at given position.
*/
const T* get(unsigned int aIndex) const
{
return nullptr;
}
/**
* @brief Inserts value at given position.
* @param aIndex Position of value. Must be lower than size.
* @param aValue Value to insert.
*/
void insert(unsigned int aIndex, const T& aValue)
{
}
/**
* @brief Returns a random access iterator that points to the beginning.
* @return Iterator to the beginning.
*/
DIterator begin()
{
return DIterator(mBegin);
}
/**
* @brief Returns a random access iterator that points to the item after the last one.
* @return Iterator to the item after the last one.
*/
DIterator end()
{
return DIterator(nullptr);
}
/**
* @brief Returns a reverse random access iterator that points to the last item.
* @return Reverse iterator to the last item.
*/
DReverseIterator rbegin()
{
return DReverseIterator(nullptr);
}
/**
* @brief Returns a reverse random access iterator that points to the item before the first one.
* @return Reverse iterator to the item before the first one.
*/
DReverseIterator rend()
{
return DReverseIterator(nullptr);
}
private:
/**
* @brief Pointer to the first item of the list.
*/
CDoublyLinkedListItem<T>* mBegin;
CDoublyLinkedListItem<T>* mEnd;
unsigned int size = 0;
};
#endif //CPP_DOUBLY_LINKED_LIST_HPP_
Revise this Paste