My Double Linked List

[Halsafar]

Just curious, how'd I do?

I wrapped it up in a class even though ever document on the basic's of a linked list showed a simple struct then functions to manage the struct. I choose to wrap it up which may have prooved a few complications but will aid in what I need it for.

I think some of it is redundant and I may be taking an extra step in some places but it works, at least what you see here.

I am working on Insertion at any point given a node, but haven't got that working well yet.

#ifndef __HAL_DOUBLELINKEDLIST
#define __HAL_DOUBLELINKEDLIST


/*
A list node
*/
template <typename _TY>
struct listNode {
    listNode() {
        pPrev = NULL;
        pNext = NULL;
    }
    listNode(_TY tData) {
        tItem = tData;
        pPrev = NULL;
        pNext = NULL;
    }
    listNode *pPrev;
    listNode *pNext;
    _TY          tItem;
};    

/*
A double linked list
*/
template <typename _TY>
class cDoubleList 
{
private:
    listNode<_TY>    *m_pHead;
    listNode<_TY>    *m_pTail;
public:
    cDoubleList<_TY>();
    ~cDoubleList();

    void Destroy();

    void InsertFront(_TY tData);
    void InsertEnd(_TY tData);
    void Insert(_TY tData, listNode<_TY> *pListNode);

    _TY  RemoveFront();
    _TY  RemoveEnd();
        _TY  Remove(listNode<_TY> *pListNode);

    bool Empty();

    listNode<_TY> *Head() {
        return m_pHead;
    }
    listNode<_TY> *Tail() {
        return m_pTail;
    }
}; 

/*
Construct the list
*/
template <typename _TY>
cDoubleList<_TY>::cDoubleList()
{

}

template <typename _TY>
cDoubleList<_TY>::~cDoubleList()
{
    Destroy();
}


/*
Destroy the lsit
*/
template <typename _TY>
void cDoubleList<_TY>::Destroy()
{
    if (Empty()) {
        return;
    }

    listNode<_TY>    *pCurrentNode = 0;
    listNode<_TY>    *pLastNode = 0;
    for (pCurrentNode = m_pHead; pCurrentNode != NULL;) {
        pLastNode = pCurrentNode;
        pCurrentNode = pCurrentNode->pNext;
        
        //Protect against circular deletion
        if (pCurrentNode == pLastNode) {
            pCurrentNode = NULL;
        }

        delete pLastNode;
    }
}


/*
Checks if the list is empty
*/
template <typename _TY>
bool cDoubleList<_TY>::Empty()
{
    if (!m_pHead) {
        return true;
    }

    return false;
}

/*
Inserts a list at the front (head)
*/
template <typename _TY>
void cDoubleList<_TY>::InsertFront(_TY tData)
{
    //No Nodes
    if (Empty()) {
        m_pHead = new listNode<_TY>(tData);
        m_pHead->pPrev = NULL;
        m_pHead->pNext = m_pTail;
        return;
    }

    //One Node
    if (!m_pTail) {
        listNode<_TY> *pNewNode = new listNode<_TY>(tData);    
        m_pTail = m_pHead;
        m_pHead = pNewNode;
        m_pHead->pNext = m_pTail;
        m_pHead->pPrev = NULL;
        m_pTail->pNext = NULL;
        m_pTail->pPrev = m_pHead;
        return;
    }

    //All inbetween
    listNode<_TY> *pNewNode = new listNode<_TY>(tData);
    m_pHead->pPrev = pNewNode;
    pNewNode->pNext = m_pHead;
    pNewNode->pPrev = NULL;
    m_pHead = pNewNode;
}


template <typename _TY>
void cDoubleList<_TY>::InsertEnd(_TY tData)
{
    //No Nodes
    if (Empty()) {
        m_pHead = new listNode<_TY>(tData);
        m_pHead->pPrev = NULL;
        m_pHead->pNext = m_pTail;
        return;
    }

    //One Node
    if (!m_pTail) {
        listNode<_TY> *pNewNode = new listNode<_TY>(tData);    
        m_pTail = pNewNode;
        m_pTail->pNext = NULL;
        m_pTail->pPrev = m_pHead;
        m_pHead->pNext = m_pTail;
        m_pHead->pPrev = NULL;
        return;
    }

    //All inbetween
    listNode<_TY> *pNewNode = new listNode<_TY>(tData);
    m_pTail->pNext = pNewNode;
    pNewNode->pPrev = m_pTail;
    pNewNode->pNext = NULL;
    m_pTail = pNewNode;
}


/*
Insert an item in front of a given node
*/
template <typename _TY>
void cDoubleList<_TY>::Insert(_TY tData, listNode<_TY> *pGivenNode)
{
    if (pGivenNode == m_pTail) {
        InsertEnd(tData);
        return;
    }

    listNode<_TY> *pNewNode = new listNode<_TY>(tData);
    pNewNode->pNext = pGivenNode->pNext;
    pNewNode->pPrev = pGivenNode;
    pGivenNode->pNext->pPrev = pNewNode;
    pGivenNode->pNext = pNewNode;
}


/*
Remove the head
*/
template <typename _TY>
_TY cDoubleList<_TY>::RemoveFront()
{
    //On empty return a 0based version of _TY
    if (Empty()) {
        _TY tTemp;
        memset(&tTemp, 0, sizeof(_TY));
        return tTemp;
    }

    //If the head has no next then it is the only one, the list dead
    if (!m_pHead->pNext) {
        _TY tTemp = m_pHead->tItem;
        delete m_pHead;
        m_pHead = NULL;
        m_pTail = NULL;

        return tTemp;
    }

    listNode<_TY> *pOldHead = m_pHead;
    m_pHead = m_pHead->pNext;
    m_pHead->pPrev = NULL;

    //If the tails end up as the head we NULL out the tail
    if (m_pTail == m_pHead) {
        m_pTail = NULL;
    }

    _TY tTemp = pOldHead->tItem;
    delete pOldHead;

    return tTemp;
}


/*
Remove an item from the end
*/
template <typename _TY>
_TY cDoubleList<_TY>::RemoveEnd()
{
    //On empty return a 0based version of _TY
    if (Empty()) {
        _TY tTemp;
        memset(&tTemp, 0, sizeof(_TY));
        return tTemp;
    }
    
    listNode<_TY> *pOld = 0; 

    //If tail doesn't exist, pop bottom else store the tail pointer
    if (!m_pTail) {
        return RemoveFront();
    } else {
        pOld = m_pTail;
    }

    //If the tails previous is the head, after the pop the tail will be the head, adjust here
    if (m_pTail->pPrev == m_pHead) {
        m_pTail = NULL;
        m_pHead->pNext = NULL;
    } else {
        m_pTail = m_pTail->pPrev;
        m_pTail->pNext = NULL;
    }

    _TY tTemp = pOld->tItem;
    delete pOld;

    return tTemp;
}


/*
Remove an item
*/
template <typename _TY>
_TY cDoubleList<_TY>::Remove(listNode<_TY> *pGivenNode)
{
    if (m_pHead == pGivenNode) {
        return RemoveFront();
    }

    pGivenNode->pPrev->pNext = pGivenNode->pNext;
    pGivenNode->pNext->pPrev = pGivenNode->pPrev;

    if (m_pTail == m_pHead) {
        m_pTail = NULL;
    }

    _TY tTemp = pGivenNode->tItem;
    delete pGivenNode;

    return tTemp;
} 

Edit: I added my working insert function.

Another Edit: I debugged it tons and found many bugs. So each function has had some minor modifications to it.