Attempt at Linked List Template Class - C and C++ - Forums at ProgrammersHeaven.com

C and C++

Moderators: None (Apply to moderate this forum)

Number of threads: 28695
Number of posts: 94715

With full replies

Topics only

C and C++

Subforums

Forum Info

This Forum Only

Single Post View Linear View Threaded View f

Printer Friendly

RSS Feed

Attempt at Linked List Template Class Posted by mikfig on 26 Dec 2008 at 4:14 AM

I just coded out a linked list template class, its my first attempt at template coding. It compiles fine; however, I get these 3 linker errors:

error LNK2019: unresolved external symbol "public: __thiscall LinkedList<int,0>::~LinkedList<int,0>(void)" (??1?$LinkedList@H$0A@@@QAE@XZ) referenced in function _main	main.obj
error LNK2019: unresolved external symbol "public: int & __thiscall ListIterator<int,0>::operator()(void)" (??R?$ListIterator@H$0A@@@QAEAAHXZ) referenced in function _main	main.obj
error LNK2019: unresolved external symbol "public: class ListIterator<int,0> & __thiscall LinkedList<int,0>::insertAfter(class ListIterator<int,0>,int const &)" (?insertAfter@?$LinkedList@H$0A@@@QAEAAV?$ListIterator@H$0A@@@V2@ABH@Z) referenced in function _main	main.obj

Here is the code:
main.cpp

//main.cpp
#include "LinkedList.h"

int main()
{
    LinkedList<int, 0> list;
    ListIterator<int, 0> listBegin = list.begin();

    list.insertAfter(listBegin, 10);
    listBegin() = 5;
    return 0;
}

LinkedList.h

//LinkedList.h
#include "ListIterator.h"
#include "ListNode.h"

#ifndef __LINKED_LIST__
#define __LINKED_LIST__

template<class tDataType, tDataType tZeroVal>
class LinkedList
{
public:
    LinkedList() : m_head(0), m_tail(0), m_iNodes(0)
    { }
    LinkedList(const LinkedList<tDataType, tZeroVal> &ll) : m_head(ll.m_head), m_tail(ll.m_tail), m_iNodes(ll.m_iNodes)
    { }
    ~LinkedList();

    ListIterator<tDataType, tZeroVal>   begin() { return ListIterator<tDataType, tZeroVal>(m_head); }
    ListIterator<tDataType, tZeroVal>   end() { return ListIterator<tDataType, tZeroVal>(m_tail); }

    ListIterator<tDataType, tZeroVal>&  insertBefore(ListIterator<tDataType, tZeroVal> p_iter, const tDataType& data);
    ListIterator<tDataType, tZeroVal>&  insertAfter(ListIterator<tDataType, tZeroVal> p_iter, const tDataType& data);
    void                                remove(ListIterator<tDataType, tZeroVal> p_iter);

protected:
    ListNode<tDataType, tZeroVal>*   m_head;
    ListNode<tDataType, tZeroVal>*   m_tail;
    int         m_iNodes;
};

#endif

LinkedList.cpp

//LinkedList.cpp
#include "LinkedList.h"

template<class tDataType, tDataType tZeroVal>
LinkedList<tDataType, tZeroVal>::~LinkedList()
{
    if(m_head != 0)
    {
        ListNode* pPrev = m_head;
        ListNode* pNext;

        while(pPrev != 0)
        {
            pNext = pNext->m_next;
            delete pPrev;
            pPrev = pNext;
        }
    }
}

template<class tDataType, tDataType tZeroVal>
ListIterator<tDataType, tZeroVal>& LinkedList<tDataType, tZeroVal>::insertBefore(ListIterator<tDataType, tZeroVal> p_iter, const tDataType& data)
{
    if(m_iNodes != 0)
    {
        if(&p_iter == m_head || !(&p_iter))
        {
            m_head->prev = new ListNode<tDataType, tZeroVal>(data, &p_iter, 0);
            m_iNodes++;
            return ListIterator<tDataType, tZeroVal>(m_head->m_prev);
        }
        else
        {
            (&(p_iter - 1)).next = new ListNode<tDataType, tZeroVal>(data, &p_iter, &(p_iter - 1));
            (&p_iter).prev = (&(p_iter - 1)).next;
            return ListIterator<tDataType, tZeroVal>((&p_iter).prev);
        }
    }
    else
    {
         m_tail = m_head = new ListNode<tDataType, tZeroVal>(data, &p_iter, 0);
         m_iNodes = 1;
         return ListIterator<tDataType, tZeroVal>(m_head);
    }
}

template<class tDataType, tDataType tZeroVal>
ListIterator<tDataType, tZeroVal>&  LinkedList<tDataType, tZeroVal>::insertAfter(ListIterator<tDataType, tZeroVal> p_iter, const tDataType& data)
{
    if(m_iNodes != 0)
    {
        if(&p_iter == m_tail || !(&p_iter))
        {
            m_tail->next = new ListNode<tDataType, tZeroVal>(data, &p_iter, 0);
            m_iNodes++;
            return ListIterator<tDataType, tZeroVal>(m_tail->next);
        }
        else
        {
            (&(p_iter - 1)).next = new ListNode<tDataType, tZeroVal>(data, &p_iter, &(p_iter - 1));
            (&p_iter).prev = (&(p_iter - 1)).next;
            return ListIterator<tDataType, tZeroVal>((&p_iter).prev);
        }
    }
    else
    {
         m_tail = m_head = new ListNode<tDataType, tZeroVal>(data, &p_iter, 0);
         m_iNodes = 1;
         return ListIterator<tDataType, tZeroVal>(m_head);
    }
}

template<class tDataType, tDataType tZeroVal>
void LinkedList<tDataType, tZeroVal>::remove(ListIterator<tDataType, tZeroVal> p_iter)
{
    if(m_iNodes != 0)
    {
        if(m_iNodes == 1)
        {
            delete m_head;
            m_tail = m_head = 0;
            m_iNodes = 0;
        }
        else
        {
            if(p_iter == m_head)
            {
                ListNode<tDataType, tZeroVal>* pTemp = m_head->m_next;
                delete m_head;
                m_head = pTemp;
                m_head->m_prev = 0;
                m_iNodes--;
            }
            else if(p_iter == m_tail)
            {
                ListNode<tDataType, tZeroVal>* pTemp = m_tail->m_prev;
                delete m_tail;
                m_tail = pTemp;
                m_tail->m_next = 0;
                m_iNodes--;
            }
            else
            {
                ListNode<tDataType, tZeroVal>* prev = (&p_iter)->m_prev;
                ListNode<tDataType, tZeroVal>* next = (&p_iter)->m_next;
                delete (&p_iter);
                prev->m_next = next;
                next->m_prev = prev;
                m_iNodes--;
            }
        }
    }
}

ListNode.h

//ListNode.h
#ifndef __LIST_NODE__
#define __LIST_NODE__

template<class tDataType, tDataType tZeroVal>
class ListNode
{
public:
    ListNode() : m_data(tZeroVal), m_next(0), m_prev(0)
    { }
    ListNode(const ListNode<tDataType, tZeroVal> &ln) : m_data(ln.m_data), m_next(ln.m_next), m_prev(ln.m_prev)
    { }
    ListNode(tDataType& p_data) : m_data(p_data), m_next(0), m_prev(0)
    { }
    ListNode(ListNode<tDataType, tZeroVal>* p_prev, ListNode<tDataType, tZeroVal>* p_next) : m_data(tZeroVal), m_next(p_next), m_prev(p_prev)
    { }
    ListNode(tDataType& p_data, ListNode<tDataType, tZeroVal>* p_next, ListNode<tDataType, tZeroVal>* p_prev) : m_data(p_data), m_next(p_next), m_prev(p_prev)
    { }

    tDataType    m_data;
    ListNode*    m_next;
    ListNode*    m_prev;
};

#endif

ListIterator.h

//ListIterator.h
#include "ListNode.h"

#ifndef __LIST_ITERATOR__
#define __LIST_ITERATOR__

template<class tDataType, tDataType tZeroVal>
class ListIterator
{
public:
    ListIterator() : m_node(0)
    { }
    ListIterator(const ListIterator<tDataType, tZeroVal>& iter) : m_node(iter.m_node)
    { }
    ListIterator(ListNode<tDataType, tZeroVal>* p_node) : m_node(p_node)
    { }

    ListNode<tDataType, tZeroVal>*        operator&() { return m_node; }
    ListIterator<tDataType, tZeroVal>&    operator++();
    ListIterator<tDataType, tZeroVal>&    operator++(int dummy);
    ListIterator<tDataType, tZeroVal>&    operator--();
    ListIterator<tDataType, tZeroVal>&    operator--(int dummy);
    ListIterator<tDataType, tZeroVal>&    operator+(int p_amount);
    ListIterator<tDataType, tZeroVal>&    operator-(int p_amount);
    tDataType&                           operator[](int p_amount);
    tDataType&                           operator()();
private:
    ListNode<tDataType, tZeroVal>*   m_node;
};

#endif

ListIterator.cpp

//ListIterator.cpp
#include "ListIterator.h"

template<class tDataType, tDataType tZeroVal>
ListIterator<tDataType, tZeroVal>&    ListIterator<tDataType, tZeroVal>::operator++()
{
    if(m_node != 0 && m_node->m_next != 0)
    {
        m_node = m_node->m_next;
    }
    return *this;
}

template<class tDataType, tDataType tZeroVal>
ListIterator<tDataType, tZeroVal>&    ListIterator<tDataType, tZeroVal>::operator++(int dummy)
{
    if(m_node != 0 && m_node->m_next != 0)
    {
        ListNode* temp = m_node;
        m_node = m_node->m_next;
        return ListIterator<tDataType, tZeroVal>(temp);
    }
    else
    {
        return *this;
    }
}

template<class tDataType, tDataType tZeroVal>
ListIterator<tDataType, tZeroVal>&    ListIterator<tDataType, tZeroVal>::operator--()
{
    if(m_node != 0 && m_node->m_prev != 0)
    {
        m_node = m_node->m_prev;
    }
    return *this;
}

template<class tDataType, tDataType tZeroVal>
ListIterator<tDataType, tZeroVal>&    ListIterator<tDataType, tZeroVal>::operator--(int dummy)
{
    if(m_node != 0 && m_node->m_prev != 0)
    {
        ListNode* temp = m_node;
        m_node = m_node->m_prev;
        return ListIterator<tDataType, tZeroVal>(temp);
    }
    else
    {
        return *this;
    }
}

template<class tDataType, tDataType tZeroVal>
ListIterator<tDataType, tZeroVal>&    ListIterator<tDataType, tZeroVal>::operator+(int p_amount)
{
    if(m_node != 0 && m_node->m_next != 0)
    {
        ListNode*   newNode = m_node;

        for(int i = 0; (i < p_amount) && (newNode->next != 0); i++)
            newNode = newNode->m_next;
        return ListIterator<tDataType, tZeroVal>(newNode);
    }
    return *this;
}

template<class tDataType, tDataType tZeroVal>
ListIterator<tDataType, tZeroVal>&    ListIterator<tDataType, tZeroVal>::operator-(int p_amount)
{
    if(m_node != 0 && m_node->m_prev != 0)
    {
        ListNode*   newNode = m_node;

        for(int i = 0; (i < p_amount) && (newNode->prev != 0); i++)
            newNode = newNode->m_prev;
        return ListIterator<tDataType, tZeroVal>(newNode);
    }
    return *this;
}

template<class tDataType, tDataType tZeroVal>
tDataType&       ListIterator<tDataType, tZeroVal>::operator[](int p_amount)
{
    if(m_node != 0)
    {
        ListNode*   newNode = m_node;

        for(int i = 0; (i < p_amount) && (newNode->next != 0); i++)
            newNode = newNode->m_next;
        return newNode->m_data;
    }
    return tZeroVal;
}

template<class tDataType, tDataType tZeroVal>
tDataType&       ListIterator<tDataType, tZeroVal>::operator()()
{
    if(m_node != 0)
    {
        return m_node->m_data; 
    }
    return tZeroVal;
}

Any tips will be appreciated as well.

Thanks,
Mikfig

Share By Email

Thread Tree

mikfig Attempt at Linked List Template Class on 26 Dec 2008 at 4:14 AM

mikfig Re: Attempt at Linked List Template Class on 26 Dec 2008 at 4:39 PM

dotman6 Re: Attempt at Linked List Template Class on 30 Jan 2009 at 8:34 AM

mikfig Re: Attempt at Linked List Template Class on 30 Jan 2009 at 4:10 PM

C and C++

Recent Jobs